Kỹ năng

1. Các bài liên quan đến giai thừa, hoặc lũy thừa thì lên phân tích hẳn nó ra để tìm ra được quy luật. Nếu là tính toán thì luôn có cách tính toán tối ưu (chứ ko được xây đựng hàm tính lũy thừa hoặc giai thừa để gọi lại, vì mỗi lần như thế lại là một vòng lặp, trong khi ta có thể tính từ giá trị trước đó)
2. Các bài liên quan đến chia hết thì nên sử dụng công thức chia hết.
3. Sai lầm có thể đến từ những thuật toán cơ bản nhất như tìn SNT, UCLN, BCNN,… (Do vậy phải thật chắc chắn phần này)!
4. Những bài sử dụng map khi nó cần truy xuất trực tiếp đến phần tử đó thông qua một chỉ số không phải dạng int, còn các trường hợp khác không nên dùng, đặc biệt khi duyệt map sẽ tốn rất nhiều thời gian!
(NTU : KSMA – K số nhỏ nhất)

5. Một bài ACM luôn có những test hiểm, có 2 loại test hiểm: Đó là test ở cận (nhỏ nhất và lớn nhất) 2 là các giá trị đặc biệt!
6. Nên chuyển sang chế độ vào ra file khi làm việc offline để thực hiện test cho nhanh!
7. Khi gặp 1 bài khó, và ngay lúc đó ko nghĩ ra cách gì ngoài cách duyệt thì phải dừng lại và phân tích mấu chốt của bài toán, chứ làm duyệt sẽ không ăn được bài đó nên đừng mất công!
Đây là các bài toán số học điển hình, chỉ cần ta kiên trì nghiên cứu thật nhiều test là có thể suy ra được công thực và cách làm đúng!
8. Đừng lọ mọ bắt tay vào code khi chưa chạy đúng trên giấy! (Đương nhiên là trừ những bài quá dễ! :v )
9. Với bài nhiều trường hợp điều quan trọng là phải nghĩ ra ĐỦ bộ test cho TẤT CẢ các trường hợp đó!
(Điều này rất quan trọng vì nếu không ta sẽ không biết ta sai ở đâu mà sửa, mặc dù thuật toán đúng!)
10. Việc quan trọng nhất trước khi bắt tay vào nghĩ thuật toán/tìm lời giải đó là hiểu đúng bài toán, hiểu đúng test!
11. Khi làm đệ quy đặc biệt chú ý đến điều kiện dừng của nó nếu ko sẽ bị TLE.
Hôm qua vừa bị 1 thằng Hack vì ko kiểm tra kết = 0, mà chỉ kiểm tra kết quả bằng nhau a==b! 😐
(Nếu sai bước này thì tất cả các phần sau trở thành công cốc!)

12. Những bài như bài cái túi thì nên cài đặt kiểu dữ liệu theo cấu trúc của nó, đề phòng trường hợp cần thao tác như vậy! Và stt cũng có thể dùng như là 2 trường!

13.[QHĐ] Kỹ thuật tính cộng dồn!
Trong trường hợp ta cần tính tổng từ a[i] đến a[j] nào đó, nếu nó cho độ lớn của a[i] đủ nhỏ (<1000)!
Để giảm độ phức tạp tính toán (for(k,i,j)), ngay lúc đầu ta có thể tính cộng dồn vào (a[i] += a[i-1]).
Khi đó tổng a[i] đến a[j] = a[j] – a[i]…
(Ap dụng tương tự với việc tính tổng của khu vực K x K trong 1 ma trận)
(http://laptrinh.ntu.edu.vn/Problem/Details/76)

14.[QHĐ] Với bài sử dụng quy hoạch động thì phải nhìn bài toán một cách tổng quát!
Suy ra công thức 1 cách tổng quát và đệ quy!
Chỉ nên liệt kê ra các trường hợp để thử xem kết quả đúng không chứ ko nên liệt kê ra để tìm công thức, vì như thế sẽ mất rất nhiều thời gian mà lại không phải là cách đúng!
(Nhiều khi đơn giản mà ta lại làm cho nó phức tạp lên!)
(http://laptrinh.ntu.edu.vn/Problem/Details/74)

15.[QHĐ] Với bài quy hoạch động, chỉ số có thể chính là cận của nó!
Như bài cái túi 2! Nhưng nó cũng chỉ làm việc trong độ lớn cho phép!
(http://laptrinh.ntu.edu.vn/Problem/Details/1148)

16. [Graph]Phần này hay sử dụng danh sách kề (BFS,DFS). Và map, pair để lưu độ dài các cạnh
(NTU – SUMTREE)

17. Đối với bài mà lượng input và output lớn thì việc sử dụng scanf và printf sẽ nhanh hơn khá nhiều!
(http://vn.spoj.com/problems/MAXARR1/)

Kỹ thuật

1. Khi sử dụng getline(cin,s) nhớ để cin.ignore(1) phía trước để bỏ dấu enter ngay phía trước nó!
2. Kỹ thuật sắp xếp có điều kiện.
3. Kỹ thuật duyệt map.
4. Kỹ thuật duyệt cây.
5. Bao giờ cũng phải khởi tạo giá trị cho biến đã tạo! Khởi tạo giá trị gì cũng phải nghĩ xem có phù hợp với ngữ cảnh bài toán và tiện cho việc đọc code hay không!
6. Nhiều khi i– đặt ở đâu trong vòng for cũng là một cái cần suy nghĩ!
Vừa dính 1 bài ntn xong!
7. Kỹ thuật tìm kiếm nhị phân cho những bài có yếu tố sắp xếp!

Team

1. Việc đầu tiên là cần chia nhau tìm và lọc ra các bài dễ nhất trước.
2. Với cái bài dễ thì mỗi người xử lý 1 bài.
Người được ngồi code là người ra thuật toán trước.
3. Sau khi xử lý xong các bài dễ.
Đến lượt bài khó thì chia làm 2 đội: Đội 2 người tiếp tục xử lý bài tập tiếp theo, người còn lại tiếp tục đọc đề để tìm bài tiếp theo sẽ xử lý!
(Tuyệt đối phải đọc hết các bài! Không được để xót bài nào!
Nhớ nhé! BẮT BUỘC PHẢI ĐỌC HẾT ĐỀ BÀI!)

Một số lỗi

– Một số lỗi biên dịch như:
+ Sử dụng cin.ignore thì ok nhưng chạy bằng fflush là lỗi
+ Một số máy thì khi khởi tạo 1 mảng nó sẽ có giá trị bằng = 0, nhưng một số máy lại ko, do vậy nếu dùng mảng thì phải memset, còn ko thì dùng vector cho chắc!
+ Nhớ bỏ ONLINE_JUDGE trước khi nộp bài
+ Việc học thuật toán bằng code là rất khó, cần hiểu được thuật toán và chạy được bằng tay (đặc biệt là những bài đồ thị, thì chỉ có thể học bằng cách vẽ hình và chạy bằng tay) từ đó có thể xây dựng lại code!

Tricks trong trường hợp bí quá và sắp hết thời gian
1. Bài YES/NO thì in bừa.
2. Bài số lớn thì dùng java.

Advertisements