# ***Các kiến thức cơ bản cần có khi thi HSG TP vòng 1 cấp 3 ở Hà Nội***

Kì thi học sinh giỏi thành phố là một kì thi lớn và có tính cạnh tranh rất cao đối với nhiều học sinh tại Hà Nội.

Kì thi này sẽ chia ra làm hai vòng, với vòng 1 để xét giải HSG Thành Phố và chọn ra khoảng một nửa thì sinh sẽ có mặt trong vòng tiếp theo, chính là vòng thi để chọn ra đội tuyển tham dự kì thi HSG Quốc Gia.

Tuy nhiên, với môn Tin Học, những kiến thức cần dùng trong kì thi này (lập trình thi đấu) lại rất khác so với chương trình học phổ thông. Bài viết này sẽ cung cấp cho các bạn những mảng kiến thức cần biết để có thể chinh phục kì thi HSG Thành Phố Vòng 1.

## I. Tóm lược thông tin và cấu trúc đề thi

### Thông tin

- Kì thi sẽ bao gồm một buổi, có thời gian làm bài là 180 phút.
- Thí sinh sẽ thực hành code trên máy của đơn vị trường tổ chức.
- Các bài đều yêu cầu nhập Input và xuất Output theo file tương ứng.

### Cấu trúc đề thi

Kì thi sẽ bao gồm $5$ bài, có tổng điểm là $20$ điểm.

Cụ thể:

- Bài $1$: Sẽ dừng ở mức nhận biết, chỉ cần biết một chút tối ưu trong code là có thể AC bài này.
- Bài $2$ : Để AC được bài này, cần áp dụng kiến thức về một vài thuật toán cơ bản (như ```sort``` hay ``` sàng số nguyên tố ```). Đôi khi bài $1$ và $2$ sẽ đổi chỗ cho nhau.
- Bài $3$: Cần áp dụng và kết hợp một vài thuật toán và cấu trúc dữ liệu, cụ thể như ```tìm kiếm nhị phân```, ``` tăng giảm mảng hiệu ```, ```cấu trúc dữ liệu trong thư viện STL```, ...
- Bài $4$: Thường sẽ là bài đồ thị, có độ khó và tính phân loại cao. Lúc này cần nắm rõ các thuật toán trên đồ thị và ứng dụng nâng cao của nó mới có thể AC được.
- Bài $5$: Không giới hạn dạng, có thể là ```tham lam```, ```quy hoạch động ```, ```cấu trúc dữ liệu```, ... Nhìn chung, để làm được bài này cần rất nhiều kiến thức nâng cao ghép lại. Độ khó của bài này có thể ngang với một bài trong kì thi HSG Quốc Gia. Bài $4$ và $5$ cũng có thể đổi chỗ cho nhau.

Các bài thi đều được chia thành các subtask, mỗi subtask đều có giới hạn và điều kiện riêng. Mỗi bài đều gồm nhiều test tương ứng với các subtask và thí sinh sẽ nhận điểm dựa trên số test chạy đúng.

Tùy theo năm, thang điểm của các bài có thể là $5-4-4-4-3$ hoặc $5-5-4-3-3$.

## II. Các kiến thức cơ bản cần có

Để dễ hình dung, chúng ta sẽ chia các thuật toán này ra làm $3$ mức: Dễ, Trung Bình và Khó.

### Mức Dễ:

***1) Tìm kiếm nhị phân***
- Đây có lẽ là một thuật toán kinh điển đối với bất cứ ai học về giải thuật. Độ xuất hiện trong các kì thi của nó là rất lớn, vậy nên bạn cần thành thạo thuật toán này.
- Bạn có thể tìm đọc về Tìm kiếm nhị phân tại [đây](https://vnoi.info/wiki/algo/basic/binary-search.md).

***2) Sàng số nguyên tố***

- Đây là một thuật toán cơ bản và cũng rất quan trọng trong những bài số học, thường sẽ ra ở bài $1$ hoặc bài $2$.
- Các bạn có thể tìm đọc về Sàng số nguyên tố tại [đây](https://vnoi.info/wiki/translate/he/Number-Theory-2.md).

***3) Mảng cộng dồn và mảng hiệu***

- Đây là kiến thức rất quan trọng trong các bài toán về mảng và cập nhật mảng ở mức thi thành phố.
- Các bạn có thể tìm đọc về Mảng cộng dồn và mảng hiệu tại [đây](https://vnoi.info/wiki/algo/data-structures/prefix-sum-and-difference-array.md).

***4) Quay lui***

- Đây là kiến thức thường được mặc định ở mức dễ nhưng không phải ai cũng biết cách cài đặt nó. Hơn nữa, tính ứng dụng của nó là rất lớn trong những bài cần làm subtask nhỏ để kiểm tra hoặc lấy điểm.
- Các bạn có thể tìm đọc về Quay lui tại [đây](https://viblo.asia/p/thuat-toan-quay-lui-backtracking-bJzKmLbD59N).

***5) Tham lam***

- Đây là một thuật toán rất rộng, với tư tưởng khá "gần gũi". Chính vì vậy, nó có thể xuất hiện ở các bài từ dễ tới khó.
- Các bạn có thể tìm đọc về Tham lam tại [đây](https://viblo.asia/p/thuat-toan-tham-lam-greedy-algorithm-XQZGxozlvwA).

### Mức Trung bình:

***1) Các cấu trúc dữ liệu STL***
- Các cấu trúc này được sử dụng khá nhiều tùy theo yêu cầu của bài toán và thuật toán cần sử dụng.
- Các bạn có thể tìm đọc về nó tại [đây](https://vnoi.info/library/56/4958/).

***2) Quy hoạch động cơ bản***

- Đây là một thuật toán rộng và phổ biến không kém gì Tìm kiếm nhị phân.
- Các bạn có thể tìm đọc về phần nhập môn Quy hoạch động tại [đây](https://viblo.asia/p/phan-1thuat-toan-quy-hoach-dong-QpmleJzM5rd). Trước tiên, hãy cố gắng hiểu [những bài toán cổ điển trong Quy hoạch động](https://vnoi.info/wiki/algo/dp/basic-problems.md).
- Quy hoạch động là một trong những phần quan trọng và xuất hiện rất nhiều ở tất cả các kì thi HSG môn Tin Học. Như chúng ta đã nói, độ rộng của nó là rất lớn và độ khó cũng sẽ tăng theo từng mức. Tài liệu và bài tập cho phần này rất nhiều, nếu các bạn muốn tốt hơn về phần này thì có thể lên mạng tìm kiếm thêm.

***3) Hash***

- Đây là thuật toán có tính ứng dụng cao và rất hay được áp dụng ở những bài về xâu.
- Các bạn có thể tìm đọc về Hash tại [đây](https://vnoi.info/wiki/algo/string/hash.md).

***4) DFS/BFS***

- Đây là "bộ đôi" được sử dụng rất nhiều trong các bài đồ thị không có trọng số. Nếu muốn có điểm ở bài đồ thị, các bạn chắc chắn cần biết tới phần này.
- Các bạn có thể tìm đọc về DFS/BFS tại [đây](https://howkteam.vn/course/cau-truc-du-lieu-va-giai-thuat/bfs-va-dfs-4320).

***5) Tree***

- Đây là một nhánh kiến thức quan trọng của đồ thị. Nó rất hay và khá đặc biệt, nên thường được sử dụng để ra đề trong các kì thi HSG.
- Các bạn có thể tìm đọc về Cây tại [đây](https://vnoi.info/wiki/translate/wcipeg/tree).

***6) DSU và MST***

- DSU là một cấu trúc dữ liệu hay sử dụng trên đồ thị (và có thể ứng dụng sang một vài bài toán khác), còn MST (hay cây khung nhỏ nhất) là một bài toán cải tiến bằng DSU và đã từng xuất hiện trong kì thi HSGTP.
- Các bạn có thể tìm đọc về DSU tại [đây](https://vnoi.info/wiki/algo/data-structures/disjoint-set-union.md).

***7) Dijkstra***

- Đây là một thuật toán phổ biến để làm các bài tập liên quan tới đường đi ngắn nhất trong đồ thị có trọng số không âm.
- Ngoài ra, còn một số giải thuật khác để tìm đường đi ngắn nhất, các bạn có thể đọc tại [đây](https://vnoi.info/wiki/algo/graph-theory/shortest-path.md).

### Mức Khó:

***1) Các cấu trúc dữ liệu nâng cao***

- Đôi khi việc sử dụng một vài cấu trúc dữ liệu nâng cao, tuy không đúng theo ý đồ của bài toán, nhưng sẽ giúp việc làm bài của ta trở nên "dễ nghĩ" và "dễ code" hơn.
- Một số cấu trúc dữ liệu bạn nên biết
- [Sparse Table](https://vnoi.info/wiki/algo/data-structures/rmq.md)
- [Segment Tree](https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md)
- [Fenwick Tree](https://vnoi.info/wiki/algo/data-structures/fenwick.md)

***2) Quy hoạch động nâng cao***

- [Quy hoạch động trên cây](https://viblo.asia/p/quy-hoach-dong-tren-cay-LzD5d9B4KjY)
- [Quy hoạch động Bitmask](https://marisaoj.com/resources/bitmask-dp/)
- [Một số kĩ thuật tối ưu hóa quy hoạch động](https://vnoi.info/wiki/algo/dp/Mot-so-ky-thuat-toi-uu-hoa-thuat-toan-Quy-Hoach-Dong.md)

Trên đây là một số thuật toán và kĩ thuật cần thiết cho kì thi HSG Thành Phố Vòng $1$. Khi đi thi, bạn cần vận dụng và kết hợp được chúng lại với nhau để có thể đạt được kết quả tốt nhất.