L? Trnh Luy?n Thi SPOJ

M?t l? trnh c c?u trc ?? gi?i quy?t cc bi ton trn Sphere Online Judge (SPOJ), t? c? b?n ??n nng cao.

Trở về lộ trình
Giai ?o?n Ch? ?? chnh Bi ton Luy?n t?p M?c tiu
1 Ad-Hoc Problems (Getting Started)
  • TEST - Life, the Universe, and Everything
  • ADDREV - Adding Reversed Numbers
  • FCTRL2 - Small factorials
  • ONP - Transform the Expression
  • PALIN - The Next Palindrome
 Lm quen v?i h? th?ng ch?m bi v cc bi ton c? b?n.
2 Ton h?c L thuy?t s?:
  • PRIME1 - Prime Generator
  • FCTRL - Factorial
  • TDPRIMES - Printing some primes
  • DIVSUM - Divisor Summation
T? h?p:
  • NSTEPS - Number Steps
  • PERMUT2 - Ambiguous Permutations
 p d?ng cc khi ni?m ton h?c ?? gi?i quy?t v?n ??.
3 Tm ki?m Nh? phn
  • AGGRCOW - Aggressive cows
  • PIE - Pie
  • BSEARCH - Binary search
  • EKO - Eko
 Thnh th?o k? thu?t tm ki?m nh? phn trn cu tr? l?i.
4 CTDL & C++ STL Standard Template Library (STL):
  • STPAR - Street Parade
  • JNEXT - Just Next !!!
  • ANARC09A - Seinfeld
CTDL Nng cao:
  • GSS1 - Can you answer these queries I
  • HORRIBLE - Horrible Queries
 S? d?ng hi?u qu? th? vi?n chu?n v cc CTDL ph?c t?p.
5 Duy?t ?? th? (DFS/BFS)
  • PT07Z - Longest path in a tree
  • BUGLIFE - A Bugs Life
  • LABYR1 - Labyrinth
  • MICEMAZE - Mice and Maze
 N?m v?ng cc thu?t ton duy?t ?? th? c? b?n.
6 Disjoint Set Union (DSU)
  • FRNDCIRC - FRIEND CIRCLE
  • KOZE - Sheeps
  • CLSLNS - Close Cousins
 Hi?u v p d?ng DSU cho cc bi ton v? t?p h?p.
7 Quay lui (Backtracking)
  • NQUEEN - N-Queens Puzzle
  • SUDOKU - Sudoku
  • TULIPS - Tulips and Roses
 Gi?i quy?t cc bi ton tm ki?m ton c?c b?ng quay lui.

T? duy C?t li cho L?p trnh vin Thi ??u

1. Phn r v Chinh ph?c

Chia nh? m?i v?n ?? ph?c t?p thnh cc bi ton con nh? nh?t, ??n gi?n nh?t. Gi?i cc tr??ng h?p ??n gi?n tr??c (v d?: v?i n=1, n=2) ?? xy d?ng tr?c gic tr??c khi t?ng qut ha.

2. Nh?n d?ng M?u c? b?n

H?u h?t cc v?n ?? l bi?n th? c?a m?t m?u ho?c thu?t ton ? bi?t. Hy t? h?i: "?y c ph?i l bi ton s?p x?p? Duy?t ?? th?? Hay m?t bi ton quy ho?ch ??ng tr hnh?"

3. Rng bu?c l G?i

Cc rng bu?c (v d?: N <= 10^5) l m?t g?i r?t l?n v? ?? ph?c t?p th?i gian c?n thi?t. Chng cho b?n bi?t li?u gi?i php O(N^2) c qu ch?m hay khng v li?u b?n c c?n cch ti?p c?n O(N log N) ho?c O(N).

4. Luy?n t?p c Ch? ?ch (Upsolve)

??ng ch? gi?i nh?ng bi b?n ? bi?t cch gi?i. Sau m?t cu?c thi, hy upsolve: dnh th?i gian ?? hi?u v tri?n khai gi?i php cho nh?ng bi b?n khng th? gi?i ???c.