Bài 42: Lý thuyết trò chơi trong C++ và Python: trạng thái thắng thua, Nim, hàm Grundy, minimax và tổng ôn series Thuật toán chuyên sâu
Lời mở đầu
Đề HSG rất thích những bài dạng “An và Bình chơi một trò chơi… cả hai đều chơi tối ưu, hỏi ai thắng?”. Lần đầu gặp, nhiều bạn thử mô phỏng từng ván và lạc ngay trong hàng triệu khả năng. Thật ra phần lớn các bài này chỉ cần một ý: tô màu thắng/thua cho từng trạng thái, và đó chính là quy hoạch động ở bài 19 mặc một chiếc áo mới. Khi có nhiều trò chơi chạy song song, công cụ lại là phép XOR em đã học ở bài 20. Còn trò “lấy hai đầu dãy” là một bài QHĐ đoạn (bài 27) chính hiệu.
Đây cũng là bài khép lại chặng đầu (bài 33–42) của series Thuật toán chuyên sâu. Sau bốn phần về lý thuyết trò chơi, Phần 5 sẽ xếp toàn bộ kiến thức từ bài 33 tới bài 42 lên một tấm bản đồ, kèm bảng “dấu hiệu trong đề → kỹ thuật” và lời khuyên khi ôn thi HSG quốc gia. Ba bài tập cuối cũng là ba bài tổng ôn trộn trò chơi với cây, Fenwick và số học.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Trạng thái thắng, trạng thái thua
Xét trò chơi quen thuộc: có $n$ viên sỏi, An và Bình lần lượt bốc, An đi trước. Mỗi lượt được bốc từ $1$ tới $k$ viên. Ai đến lượt mà không còn sỏi để bốc thì thua (nói cách khác: ai bốc viên cuối cùng thì thắng). Cả hai đều chơi tối ưu. Hỏi ai thắng?
Các trò chơi trong đề thi thường có chung bốn đặc điểm: hai người luân phiên, thông tin đầy đủ (không giấu bài, không tung xúc xắc), luật đi như nhau cho cả hai người, và trò chơi chắc chắn kết thúc. Khi đó mỗi trạng thái (ở đây là số sỏi còn lại) chỉ có thể là một trong hai loại:
- Thua (L): trạng thái kết thúc, hoặc mọi nước đi đều dẫn tới trạng thái thắng (cho đối thủ).
- Thắng (W): có ít nhất một nước đi dẫn tới trạng thái thua (cho đối thủ).
“Thắng” ở đây luôn hiểu là thắng cho người đang đến lượt. Hai quy tắc trên cho phép tô trạng thái theo thứ tự từ nhỏ tới lớn, giống hệt QHĐ: ô $0$ là L, rồi mỗi ô sau nhìn lại các ô trước. Với $k = 3$:
Hình 1. Bảng thắng thua khi được bốc 1 – 3 viên. Từ ô 6 (ô vàng) có ba nước đi tới 5, 4, 3; ô 4 là L nên 6 là W: bốc 2 viên để Bình còn 4 viên.
Nhìn bảng là thấy quy luật: các ô thua là $0, 4, 8, 12, \ldots$, tức là bội của $k + 1$. Giải thích rất đẹp: nếu $n$ chia hết cho $k + 1$, Bình bốc $x$ viên thì An bốc $k + 1 - x$ viên, số sỏi lại chia hết cho $k + 1$, cứ thế cho tới khi về 0 đúng lượt Bình. Ngược lại nếu $n \bmod (k+1) \ne 0$, An bốc ngay $n \bmod (k+1)$ viên để trao thế đó cho Bình. Đáp án chỉ là một phép chia lấy dư, chạy được với $n$ tới $10^{18}$.
Khi tập nước đi lạ hơn, chẳng hạn chỉ được bốc 1, 3 hoặc 4 viên, công thức không còn hiển nhiên nhưng cách tô bảng vẫn y nguyên. Em tự tô bảng với tập nước đi tuỳ ý trong mô phỏng dưới đây (đổi ô “Được lấy” thành 1 3 4 để thấy chu kỳ khác):
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| với {1, 3, 4} | L | W | L | W | W | W | W | L | W | L | W | W | W | W | L |
Bảng 1. Tập nước đi {1, 3, 4}: các ô thua là 0, 2, 7, 9, 14, …, lặp lại theo chu kỳ 7 (n mod 7 bằng 0 hoặc 2).
Code lập bảng cho tập nước đi bất kỳ: với mỗi $i$, thử từng nước $s_j$, hễ gặp $i - s_j$ là ô thua thì $i$ là ô thắng. Độ phức tạp $O(n \cdot m)$. Em chạy tay từng dòng để thấy vòng lặp break ngay khi tìm được một nước thắng:
Xem code C++ / Python: lập bảng thắng thua với tập nước đi bất kỳ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<int> s(m);
for(int j = 0; j < m; j++) cin >> s[j];
vector<bool> win(n + 1, false);
for(int i = 1; i <= n; i++){
for(int j = 0; j < m; j++){
if(s[j] <= i && !win[i - s[j]]){
win[i] = true;
break;
}
}
}
for(int i = 0; i <= n; i++) cout << (win[i] ? 'W' : 'L');
return 0;
}import sys
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
s = list(map(int, data[2:2 + m]))
win = [False] * (n + 1) # win[0] = False: hết sỏi thì thua
for i in range(1, n + 1):
for x in s:
if x <= i and not win[i - x]: # có nước đẩy đối thủ vào thế thua
win[i] = True
break
print(''.join('W' if w else 'L' for w in win))win[trạng thái kết thúc] = false;
for(trạng thái u theo thứ tự “gần kết thúc” trước)
win[u] = (tồn tại nước đi u → v mà win[v] == false);Phần 2Trò chơi Nim và định lý XOR
Nim là “ông tổ” của lý thuyết trò chơi: có $n$ đống sỏi $a_1, a_2, \ldots, a_n$. Mỗi lượt, người chơi chọn một đống còn sỏi và bốc đi bao nhiêu viên cũng được (ít nhất 1). Ai không bốc được thì thua. Trạng thái giờ là cả bộ $(a_1, \ldots, a_n)$, số trạng thái quá lớn để lập bảng. May mắn là có một định lý cực gọn:
Chứng minh chỉ cần kiểm tra đúng hai quy tắc W/L ở Phần 1, với “L” là “XOR bằng 0”:
- Trạng thái kết thúc (mọi đống bằng 0) có $X = 0$. Đúng là L.
- Từ $X = 0$, mọi nước đi đều làm $X \ne 0$. Nước đi đổi một đống $a_i$ thành $a_i' \ne a_i$, nên XOR mới là $X \oplus a_i \oplus a_i' = a_i \oplus a_i' \ne 0$.
- Từ $X \ne 0$, luôn có nước đi về $X = 0$. Gọi $d$ là bit cao nhất của $X$. Phải có một đống $a_i$ mang bit $d$ (vì XOR của cột bit $d$ bằng 1). Đổi $a_i$ thành $a_i \oplus X$: bit $d$ của nó từ 1 thành 0, các bit cao hơn giữ nguyên, nên $a_i \oplus X < a_i$, tức là một nước bốc hợp lệ. XOR mới là $X \oplus a_i \oplus (a_i \oplus X) = 0$.
Ví dụ ba đống $3, 4, 5$. Viết dưới dạng nhị phân rồi XOR từng cột (nhắc lại bài 20: XOR là “cộng không nhớ”, cột có số chữ số 1 lẻ thì ra 1):
| Đống | Số sỏi | Bit 2 | Bit 1 | Bit 0 |
|---|---|---|---|---|
| 1 | 3 | 0 | 1 | 1 |
| 2 | 4 | 1 | 0 | 0 |
| 3 | 5 | 1 | 0 | 1 |
| XOR | 2 | 0 | 1 | 0 |
Bảng 2. $3 \oplus 4 \oplus 5 = 2 \ne 0$: An thắng. Bit cao nhất của $X$ là bit 1, đống 1 (số 3) mang bit này, đổi $3$ thành $3 \oplus 2 = 1$, tức bốc 2 viên. Còn lại $1, 4, 5$ có XOR bằng 0.
Xem code C++ / Python: nim: xác định người thắng và một nước đi thắng (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<long long> a(n);
long long X = 0;
for(int i = 0; i < n; i++){ cin >> a[i]; X ^= a[i]; }
if(X == 0){ // mọi nước đi đều làm XOR khác 0
cout << "THUA";
return 0;
}
for(int i = 0; i < n; i++)
if((a[i] ^ X) < a[i]){ // đống có bit cao nhất của X
cout << "THANG\n" << i + 1 << " " << a[i] - (a[i] ^ X);
return 0;
}
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
X = 0
for x in a:
X ^= x
if X == 0: # mọi nước đi đều làm XOR khác 0
print("THUA")
else:
for i, x in enumerate(a):
if x ^ X < x: # đống có bit cao nhất của X
print("THANG")
print(i + 1, x - (x ^ X)) # lấy bớt để đống còn x ^ X
breakĐọc thì dễ, nhưng chỉ khi tự chơi em mới thấy sức mạnh của định lý: máy dưới đây luôn đưa XOR về 0 sau lượt của nó. Em nhập các đống, chọn ai đi trước và ghi sẵn vài nước đi của mình (dạng “đống số_viên”, cách nhau bởi dấu phẩy). Thử thắng máy khi em đi trước với $3, 4, 5$ xem:
Phần 3Hàm Grundy (mex) và tổng nhiều trò chơi
Câu hỏi tự nhiên: nếu có nhiều đống, nhưng mỗi đống chơi theo luật của trò bốc sỏi ở Phần 1 (chỉ được bốc 1, 3 hoặc 4 viên) thì sao? Biết từng đống là W hay L không đủ: hai đống cùng là W, gộp lại có thể thành L. Ta cần một con số giàu thông tin hơn W/L, đó là số Grundy.
Với một tập số tự nhiên $A$, ký hiệu $\operatorname{mex}(A)$ (minimum excludant) là số tự nhiên nhỏ nhất không thuộc $A$: $\operatorname{mex}\{0, 1, 3\} = 2$, $\operatorname{mex}\{1, 2\} = 0$, $\operatorname{mex}\{\} = 0$. Số Grundy của trạng thái $u$ định nghĩa đệ quy:
$g(u) = \operatorname{mex}\{\, g(v) : u \to v \text{ là một nước đi} \,\}$
Hai tính chất quan trọng:
- $g(u) = 0$ khi và chỉ khi $u$ là trạng thái thua. (Mex bằng 0 nghĩa là không có $v$ nào có $g(v) = 0$, đúng quy tắc L.) Vậy Grundy là bản “nâng cấp” của W/L.
- Một đống Nim có $x$ viên đi được tới mọi $0, 1, \ldots, x - 1$, nên $g(x) = x$. Trạng thái có Grundy $g$ “giống hệt” một đống Nim $g$ viên.
Lý do: mỗi trò con “đóng vai” một đống Nim có $g(G_i)$ viên. Đi một nước trong trò con giống như đổi kích thước đống đó (có thể tăng lên, nhưng nước tăng luôn bị đối thủ “trả lại” được nên không ảnh hưởng kết quả). Vậy cả trò tổng là Nim, áp định lý XOR của Phần 2. Bảng Grundy của trò bốc {1, 3, 4}:
| $x$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $g(x)$ | 0 | 1 | 0 | 1 | 2 | 3 | 2 | 0 | 1 | 0 | 1 | 2 | 3 | 2 | 0 |
Bảng 3. Grundy của trò bốc 1, 3 hoặc 4 viên: 0 1 0 1 2 3 2 rồi lặp lại chu kỳ 7. Ô có Grundy 0 đúng là các ô L ở Bảng 1.
Ví dụ: hai đống 4 và 6 viên. Đứng riêng thì cả hai đều là W ($g = 2$), nhưng $2 \oplus 2 = 0$ nên người đi trước thua! Em xem mô phỏng tính từng số Grundy bằng mex, rồi XOR các đống ở cuối. Hàng “mex” tô vàng các giá trị có trong tập, ô xanh lá là số nhỏ nhất bị thiếu:
Xem code C++ / Python: hàm grundy và tổng nhiều đống sỏi (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int m, n;
cin >> m;
vector<int> s(m);
for(auto &x : s) cin >> x;
cin >> n;
vector<int> p(n);
int mx = 0;
for(auto &x : p){ cin >> x; mx = max(mx, x); }
vector<int> g(mx + 1, 0); // g[0] = 0
for(int x = 1; x <= mx; x++){
vector<bool> seen(m + 2, false); // Grundy không vượt quá m
for(int t : s) if(t <= x) seen[g[x - t]] = true;
int v = 0;
while(seen[v]) v++; // mex
g[x] = v;
}
int X = 0;
for(int x : p){ cout << g[x] << " "; X ^= g[x]; }
cout << "\n" << (X ? "THANG" : "THUA");
return 0;
}import sys
data = sys.stdin.read().split()
m = int(data[0])
s = list(map(int, data[1:1 + m]))
n = int(data[1 + m])
p = list(map(int, data[2 + m:2 + m + n]))
mx = max(p)
g = [0] * (mx + 1) # g[0] = 0
for x in range(1, mx + 1):
seen = {g[x - t] for t in s if t <= x} # Grundy các trạng thái đến được
v = 0
while v in seen: # mex
v += 1
g[x] = v
X = 0
for x in p:
X ^= g[x]
print(*[g[x] for x in p])
print("THANG" if X else "THUA")Phần 4Minimax: trò chơi lấy hai đầu dãy
Không phải trò chơi nào cũng chỉ hỏi thắng/thua. Bài toán kinh điển: một dãy $a_1, \ldots, a_n$ đặt trên bàn. An và Bình lần lượt lấy một số ở đầu trái hoặc đầu phải của dãy còn lại, cộng vào điểm của mình. An đi trước, cả hai muốn điểm của mình lớn nhất. Hỏi điểm của mỗi người?
Tham lam không đúng. Với dãy $8, 15, 3, 7$, nếu An luôn lấy đầu lớn hơn thì An lấy 8, mở đường cho Bình lấy 15:
| Cách chơi của An | Lượt 1 (An) | Lượt 2 (Bình) | Lượt 3 (An) | Lượt 4 (Bình) | An – Bình |
|---|---|---|---|---|---|
| Tham lam: lấy đầu lớn hơn | 8 | 15 | 7 | 3 | 15 – 18 |
| Tối ưu | 7 | 8 (hoặc 3) | 15 | 3 (hoặc 8) | 22 – 11 |
Bảng 4. Lấy 7 trước thì dù Bình lấy đầu nào, số 15 cũng lộ ra cho An.
Ý tưởng minimax. Mỗi người chọn nước đi tốt nhất cho mình, và biết rằng đối thủ cũng sẽ chọn tốt nhất cho họ. Vì tổng điểm cố định (trò chơi “tổng bằng hằng số”), thứ cần tối ưu là hiệu. Gọi $dp[l][r]$ là (điểm người đang đến lượt) − (điểm đối thủ) khi trên bàn còn đoạn $a_l..a_r$ và cả hai chơi tối ưu. Người đang đi có hai lựa chọn:
- lấy $a_l$: được $a_l$, rồi tới lượt đối thủ trên đoạn $[l+1, r]$, đối thủ hơn mình $dp[l+1][r]$ → hiệu là $a_l - dp[l+1][r]$;
- lấy $a_r$: hiệu là $a_r - dp[l][r-1]$.
$dp[l][l] = a_l, \qquad dp[l][r] = \max\big(a_l - dp[l+1][r],\; a_r - dp[l][r-1]\big)$
Phép trừ chính là “đổi vai”: cái tối đa cho đối thủ là cái tối thiểu cho mình. Đây là QHĐ đoạn như bài 27: tính các đoạn theo độ dài tăng dần. Cuối cùng An được $(S + dp[1][n]) / 2$ điểm, Bình được $(S - dp[1][n]) / 2$ với $S$ là tổng dãy. Bảng $dp$ cho ví dụ (đánh số từ 0):
| $dp[l][r]$ | r = 0 | r = 1 | r = 2 | r = 3 |
|---|---|---|---|---|
| l = 0 (8) | 8 | 7 | −4 | 11 |
| l = 1 (15) | 15 | 12 | 11 | |
| l = 2 (3) | 3 | 4 | ||
| l = 3 (7) | 7 |
Bảng 5. $dp[0][3] = \max(8 - dp[1][3], 7 - dp[0][2]) = \max(8 - 11, 7 + 4) = 11$: An nên lấy 7 (đầu phải), hơn Bình 11 điểm. Tổng 33 nên An 22, Bình 11.
Em chạy tay để xem từng ô được tính từ hai ô “bỏ đầu trái” và “bỏ đầu phải” thế nào:
Xem code C++ / Python: trò chơi lấy hai đầu dãy bằng qhđ đoạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
vector<vector<long long>> dp(n, vector<long long>(n, 0));
long long sum = 0;
for(int i = 0; i < n; i++){ dp[i][i] = a[i]; sum += a[i]; }
for(int len = 2; len <= n; len++)
for(int l = 0; l + len - 1 < n; l++){
int r = l + len - 1;
dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
}
cout << (sum + dp[0][n - 1]) / 2 << " " << (sum - dp[0][n - 1]) / 2;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
# dp[l][r] = (điểm người đang đi) − (điểm đối thủ) khi còn đoạn a[l..r]
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = a[i]
for ln in range(2, n + 1): # đoạn ngắn tính trước
for l in range(n - ln + 1):
r = l + ln - 1
dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
s = sum(a)
print((s + dp[0][n - 1]) // 2, (s - dp[0][n - 1]) // 2)Phần 5Tổng ôn series Thuật toán chuyên sâu
Mười bài của series đi theo năm nhánh lớn. Em nhìn sơ đồ để nhớ “bài nào nằm ở đâu”, rồi dùng bảng ngay sau để luyện phản xạ: đọc đề, thấy dấu hiệu, nghĩ ngay tới kỹ thuật.
Hình 2. Sơ đồ kiến thức series Thuật toán chuyên sâu (bài 33 – 42), chia thành 5 nhánh.
| Dấu hiệu trong đề | Bài | Kỹ thuật | Độ phức tạp |
|---|---|---|---|
| Cây n đỉnh, tính một đại lượng cho mọi cây con; chọn đỉnh không kề nhau; đường kính cây | Bài 33 | DFS, QHĐ trên cây | $O(n)$ |
| Nhiều câu hỏi về đường đi giữa hai đỉnh trên cây, khoảng cách, tổ tiên thứ $k$ | Bài 34 | LCA, nhảy nhị phân | $O((n + q) \log n)$ |
| Công việc có điều kiện trước – sau; đường đi dài nhất / đếm đường trên đồ thị không chu trình | Bài 35 | Sắp xếp topo, QHĐ trên DAG | $O(n + m)$ |
| Đồ thị có hướng, nhóm đỉnh đi lại được với nhau; “bỏ một đỉnh / một cạnh thì mất liên thông” | Bài 36 | TPLT mạnh, khớp, cầu | $O(n + m)$ |
| Min/max đoạn trên mảng không đổi, rất nhiều truy vấn; cộng/gán cả đoạn rồi hỏi tổng/min | Bài 37 | Sparse Table; segment tree lazy | $O(1)$; $O(\log n)$ |
| Truy vấn đoạn offline khó gộp (đếm giá trị phân biệt, đếm tần suất), $n, q \le 10^5$ | Bài 38 | Chia căn, thuật toán Mo | $O((n + q)\sqrt{n})$ |
| So khớp tiền tố, xâu con đối xứng dài nhất, nhiều xâu có tiền tố chung, XOR lớn nhất của hai số | Bài 39 | Z-function, Manacher, Trie | $O(n)$ |
| Phân tích thừa số rất nhiều số, sàng trên đoạn lớn, đồng dư, hệ phương trình đồng dư, modulo không nguyên tố | Bài 40 | Sàng spf, sàng đoạn, phi Euler, Euclid mở rộng, CRT | tuỳ bài, thường $O(N \log \log N)$ |
| “Giá trị lớn nhất nhỏ nhất”, “nhỏ nhất để đạt được”; $n \le 40$ nhưng $2^n$ quá lớn | Bài 41 | Tìm kiếm nâng cao (chặt nhị phân đáp án, chặt tam phân, chia đôi tập, nhánh cận) | $O(\log V \cdot \text{kiểm tra})$ |
| “Hai người chơi tối ưu, ai thắng / được bao nhiêu điểm” | Bài 42 | Thắng thua, Nim, Grundy, minimax | theo số trạng thái |
Bảng 6. Dấu hiệu trong đề → kỹ thuật cần dùng, cho series Thuật toán chuyên sâu. Bấm “Bài NN” để mở lại lý thuyết.
Ở mức HSG quốc gia, gần như không còn bài nào chỉ dùng một kỹ thuật. Một vài “cặp đôi” rất hay gặp:
- Topo + QHĐ (bài 35 + bài 19/27): mọi QHĐ thực chất là đi trên một DAG trạng thái; trò chơi trên đồ thị không chu trình cũng là tô W/L theo topo ngược.
- TPLT mạnh + topo (bài 36 + 35): nén mỗi thành phần thành một đỉnh để được DAG, rồi QHĐ trên DAG.
- LCA + mảng cộng dồn trên cây (bài 34 + 13): cộng giá trị trên đường đi $u - v$ bằng cách cộng ở $u$, $v$ và trừ ở LCA.
- Chặt nhị phân đáp án + cấu trúc dữ liệu (bài 41 + 31/37): đoán đáp án, kiểm tra bằng Fenwick hoặc segment tree.
- Trò chơi + số học / cây / Fenwick (bài 42 + 40/33/31): biến trò chơi thành Nim, phần còn lại là tính nhanh Grundy, đúng như bài tập 6 – 8 bên dưới.
Lời khuyên khi ôn HSG quốc gia.
- Thư viện cá nhân phải “thuộc tay”. LCA nhảy nhị phân, Tarjan, segment tree lazy, sparse table, Z-function, Manacher, trie, sàng ước nguyên tố nhỏ nhất: mỗi đoạn em gõ lại được trong 5 phút mà không nhìn.
- Luyện theo chủ đề trước, trộn đề sau. Hai tháng đầu làm mỗi chủ đề 10 – 15 bài từ dễ tới khó; giai đoạn sau chỉ làm đề tổng hợp có bấm giờ để luyện khâu nhận dạng.
- Luôn có vét cạn và stress test. Với bài khó, subtask nhỏ thường chiếm 30 – 50% số điểm; code vét cạn còn là “đáp án chuẩn” để đối chiếu, như mình làm cho mọi bài tập trong series.
- Cẩn thận đệ quy sâu. Cây $2 \cdot 10^5$ đỉnh dạng đường thẳng làm DFS đệ quy tràn ngăn xếp (nhất là Python), nên tập viết DFS bằng ngăn xếp như bài tập 6.
- Chữa đề kỹ hơn làm đề. Mỗi bài sai, ghi lại: dấu hiệu nào mình bỏ lỡ, lỗi cài đặt nào (tràn số, biên, modulo âm). Sổ lỗi này là tài liệu ôn quý nhất trước ngày thi.
- Đọc lại bài 32 về chiến thuật phòng thi: chia thời gian, ăn subtask, kiểm tra tên tệp và định dạng.
Tiếp theo học gì? Lý thuyết đến đây đã đủ cho phần lớn đề HSG quốc gia; phần còn lại là làm thật nhiều bài. Mình đã xếp toàn bộ bài tập trên blog thành lộ trình học thuật toán theo từng chặng, mỗi chặng ứng với một nhóm kỹ thuật, bài nào cũng có lời giải C++ và Python. Em đi lần lượt, chặng nào làm được khoảng 70% số bài thì chuyển sang chặng sau.
- Remove Colored Pieces if Both Neighbors are the Same Color (LeetCode 2038) (Trung bình)
- Stones (AtCoder Educational DP Contest K) (Trung bình)
- Asen Và Boyan (Trung bình)
- Trò Chơi Nhặt Tiền (Khó)
Bài tậpLuyện lý thuyết trò chơi và tổng ôn series
Bài 1 – 5 luyện riêng lý thuyết trò chơi. Bài 6 – 8 là bài tổng ôn: phần trò chơi chỉ là bước đầu, phần còn lại cần kiến thức của bài 33, 31/37 và 40. Quy ước chung: An đi trước, cả hai chơi tối ưu, ai đến lượt mà không đi được thì thua; in An hoặc Binh là tên người thắng.
Có $T$ ván chơi ($T \le 10^5$). Ván thứ $i$ có $n$ viên sỏi, mỗi lượt được bốc từ $1$ tới $k$ viên ($1 \le n, k \le 10^{18}$). Với mỗi ván, in tên người thắng.
3
10 3
8 3
5 9An
Binh
An📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while(T--){
long long n, k;
cin >> n >> k;
cout << (n % (k + 1) != 0 ? "An" : "Binh") << "\n"; // bội của k + 1 là thế thua
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
for t in range(T):
n, k = int(data[1 + 2 * t]), int(data[2 + 2 * t])
out.append("An" if n % (k + 1) else "Binh") # bội của k + 1 là thế thua
print("\n".join(out))Mỗi lượt chỉ được bốc đúng $s_1$, $s_2$, …, hoặc $s_m$ viên ($m \le 10$, các $s_j$ khác nhau, $1 \le s_j \le 10^5$). Có $q$ câu hỏi ($q \le 10^5$), câu thứ $i$ cho số sỏi ban đầu $n_i$ ($1 \le n_i \le 10^5$). In tên người thắng cho từng câu.
Input: dòng đầu $m, q$; dòng hai gồm $m$ số $s_j$; dòng ba gồm $q$ số $n_i$.
3 4
1 3 4
2 5 7 10Binh
An
Binh
An📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
win tới $\max n_i$ một lần như khung chạy tay Phần 1, rồi trả lời mỗi câu trong $O(1)$. Đối chiếu Bảng 1: 2 và 7 là L, 5 và 10 là W. Để ý trạng thái nhỏ hơn mọi $s_j$ là L vì không đi được.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int m, q;
cin >> m >> q;
vector<int> s(m), ns(q);
for(auto &x : s) cin >> x;
int mx = 0;
for(auto &x : ns){ cin >> x; mx = max(mx, x); }
vector<char> win(mx + 1, 0);
for(int i = 1; i <= mx; i++)
for(int x : s)
if(x <= i && !win[i - x]){ win[i] = 1; break; }
for(int x : ns) cout << (win[x] ? "An" : "Binh") << "\n";
return 0;
}import sys
data = sys.stdin.buffer.read().split()
m, q = int(data[0]), int(data[1])
s = sorted(map(int, data[2:2 + m]))
ns = list(map(int, data[2 + m:2 + m + q]))
mx = max(ns)
win = [False] * (mx + 1)
for i in range(1, mx + 1):
for x in s:
if x > i:
break
if not win[i - x]:
win[i] = True
break
print("\n".join("An" if win[x] else "Binh" for x in ns))Có $n$ đống sỏi ($1 \le n \le 2 \cdot 10^5$), đống $i$ có $a_i$ viên ($1 \le a_i \le 10^{18}$), chơi Nim thông thường. In tên người thắng và số nước đi thắng khác nhau của An ở lượt đầu (nước đi đưa An tới chiến thắng nếu sau đó An chơi tối ưu). Nếu Bình thắng, in Binh 0.
3
3 4 5An 1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
long long X = 0;
for(auto &x : a){ cin >> x; X ^= x; }
if(X == 0){ cout << "Binh 0"; return 0; }
int cnt = 0;
for(auto x : a) if((x ^ X) < x) cnt++; // đống chứa bit cao nhất của X
cout << "An " << cnt;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
X = 0
for x in a:
X ^= x
if X == 0:
print("Binh 0")
else:
print("An", sum(1 for x in a if x ^ X < x)) # đống chứa bit cao nhất của XCó $n$ đống sỏi ($n \le 10^5$), đống $i$ có $a_i$ viên ($0 \le a_i \le 10^5$). Mỗi lượt chọn một đống và bốc đúng $s_1$, …, hoặc $s_m$ viên ở đống đó ($m \le 10$, các $s_j$ khác nhau, $1 \le s_j \le 10^5$). In tên người thắng.
Input: dòng đầu $m, n$; dòng hai gồm $m$ số $s_j$; dòng ba gồm $n$ số $a_i$.
3 2
1 3 4
4 6Binh📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int m, n;
cin >> m >> n;
vector<int> s(m), a(n);
for(auto &x : s) cin >> x;
int mx = 0;
for(auto &x : a){ cin >> x; mx = max(mx, x); }
vector<int> g(mx + 1, 0);
for(int x = 1; x <= mx; x++){
bool seen[12] = {false}; // m <= 10 nên Grundy <= 10
for(int t : s) if(t <= x) seen[g[x - t]] = true;
int v = 0;
while(seen[v]) v++;
g[x] = v;
}
int X = 0;
for(int x : a) X ^= g[x];
cout << (X ? "An" : "Binh");
return 0;
}import sys
data = sys.stdin.buffer.read().split()
m, n = int(data[0]), int(data[1])
s = sorted(map(int, data[2:2 + m]))
a = list(map(int, data[2 + m:2 + m + n]))
mx = max(a)
g = [0] * (mx + 1)
for x in range(1, mx + 1):
seen = set()
for t in s:
if t > x:
break
seen.add(g[x - t])
v = 0
while v in seen:
v += 1
g[x] = v
X = 0
for x in a:
X ^= g[x]
print("An" if X else "Binh")Cho dãy $n$ số nguyên dương ($1 \le n \le 2000$, $a_i \le 10^9$). An và Bình lần lượt lấy một số ở đầu trái hoặc đầu phải của dãy còn lại và cộng vào điểm của mình, mỗi người muốn điểm của mình lớn nhất. In điểm của An và điểm của Bình.
4
8 15 3 722 11📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long tốn 32 MB. Mẹo tiết kiệm: chỉ giữ một mảng $d[l]$ cho độ dài hiện tại. Khi chuyển từ độ dài $len - 1$ lên $len$, cập nhật $d[l]$ theo $l$ tăng dần: lúc đó $d[l + 1]$ vẫn là giá trị cũ của đoạn $[l+1, r]$, còn $d[l]$ cũ là đoạn $[l, r-1]$, đúng hai ô cần dùng. Đáp án tới $2 \cdot 10^{12}$ nên dùng long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
long long sum = 0;
for(auto &x : a){ cin >> x; sum += x; }
vector<long long> d(a); // d[l] = dp[l][l + len - 1], độ dài len = 1
for(int len = 2; len <= n; len++)
for(int l = 0; l + len - 1 < n; l++) // d[l + 1] vẫn là giá trị của độ dài len - 1
d[l] = max(a[l] - d[l + 1], a[l + len - 1] - d[l]);
cout << (sum + d[0]) / 2 << " " << (sum - d[0]) / 2;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
d = a[:] # độ dài 1: dp[l][l] = a[l]
for ln in range(2, n + 1):
d = [max(a[l] - d[l + 1], a[l + ln - 1] - d[l]) for l in range(n - ln + 1)]
s = sum(a)
print((s + d[0]) // 2, (s - d[0]) // 2)Cho cây $n$ đỉnh ($n \le 2 \cdot 10^5$) gốc tại đỉnh 1. Trên cây đặt $k$ quân cờ ($k \le 2 \cdot 10^5$) tại các đỉnh $c_1, \ldots, c_k$ (nhiều quân có thể chung một đỉnh). Mỗi lượt, người chơi chọn một quân và đi nó xuống một đỉnh con của đỉnh nó đang đứng. Quân ở lá thì không đi được. In tên người thắng.
Input: dòng đầu $n, k$; $n - 1$ dòng sau mỗi dòng một cạnh $u, v$; dòng cuối gồm $k$ số $c_i$.
7 2
1 2
1 3
2 4
2 5
3 6
6 7
2 6Binh📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<vector<int>> adj(n + 1);
for(int i = 0; i < n - 1; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> par(n + 1, 0), order, st = {1};
par[1] = -1;
while(!st.empty()){ // DFS bằng ngăn xếp, tránh tràn đệ quy
int u = st.back(); st.pop_back();
order.push_back(u);
for(int v : adj[u]) if(v != par[u]){ par[v] = u; st.push_back(v); }
}
vector<int> g(n + 1, 0);
for(int t = n - 1; t >= 0; t--){ // con luôn được tính trước cha
int u = order[t];
vector<int> vals;
for(int v : adj[u]) if(v != par[u]) vals.push_back(g[v]);
sort(vals.begin(), vals.end());
int mex = 0;
for(int x : vals){ if(x == mex) mex++; else if(x > mex) break; }
g[u] = mex;
}
int X = 0;
for(int i = 0; i < k; i++){ int c; cin >> c; X ^= g[c]; }
cout << (X ? "An" : "Binh");
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
pos = 2
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1); par[1] = -1
order, st = [], [1]
while st: # DFS bằng ngăn xếp
u = st.pop(); order.append(u)
for v in adj[u]:
if v != par[u]:
par[v] = u; st.append(v)
g = [0] * (n + 1)
for u in reversed(order): # con luôn được tính trước cha
vals = {g[v] for v in adj[u] if v != par[u]}
m = 0
while m in vals:
m += 1
g[u] = m
X = 0
for i in range(k):
X ^= g[int(data[pos + i])]
print("An" if X else "Binh")
main()Cho dãy $a_1, \ldots, a_n$ ($n \le 10^5$, $1 \le a_i \le 10^9$) và $q$ thao tác ($q \le 10^5$), mỗi thao tác là một trong hai loại:
1 i v: gán $a_i = v$;2 l r: nếu chơi Nim với các đống $a_l, a_{l+1}, \ldots, a_r$ thì ai thắng? InAnhoặcBinh.
5 4
1 2 3 4 5
2 1 3
2 2 4
1 3 2
2 1 3Binh
An
An📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> bit, a;
void upd(int i, int v){ for(; i <= n; i += i & -i) bit[i] ^= v; }
int pre(int i){ int r = 0; for(; i > 0; i -= i & -i) r ^= bit[i]; return r; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
bit.assign(n + 1, 0); a.assign(n + 1, 0);
for(int i = 1; i <= n; i++){ cin >> a[i]; upd(i, a[i]); }
while(q--){
int t, x, y;
cin >> t >> x >> y;
if(t == 1){ upd(x, a[x] ^ y); a[x] = y; } // XOR bỏ giá trị cũ, thêm giá trị mới
else cout << ((pre(y) ^ pre(x - 1)) ? "An" : "Binh") << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
bit = [0] * (n + 1)
for i in range(1, n + 1): # dựng Fenwick trong O(n)
bit[i] ^= a[i]
j = i + (i & -i)
if j <= n:
bit[j] ^= bit[i]
out = []
pos = 2 + n
for _ in range(q):
t, x, y = int(data[pos]), int(data[pos + 1]), int(data[pos + 2]); pos += 3
if t == 1:
v = a[x] ^ y; a[x] = y
while x <= n:
bit[x] ^= v; x += x & -x
else:
r, i = 0, y
while i > 0:
r ^= bit[i]; i -= i & -i
i = x - 1
while i > 0:
r ^= bit[i]; i -= i & -i
out.append("An" if r else "Binh")
print("\n".join(out))
main()Trên bảng có $n$ số nguyên dương $a_1, \ldots, a_n$ ($n \le 10^5$, $a_i \le 10^6$). Mỗi lượt, người chơi chọn một số $x > 1$ trên bảng và một ước $d > 1$ của $x$, rồi thay $x$ bằng $x / d$. Khi mọi số đều bằng 1 thì người đến lượt thua. In tên người thắng.
3
12 8 5An📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
int mx = 2;
for(auto &x : a){ cin >> x; mx = max(mx, x); }
vector<int> spf(mx + 1, 0); // ước nguyên tố nhỏ nhất
for(int i = 2; i <= mx; i++)
if(spf[i] == 0)
for(int j = i; j <= mx; j += i)
if(spf[j] == 0) spf[j] = i;
int X = 0;
for(int x : a){
int cnt = 0; // Omega(x): số thừa số nguyên tố kể cả lặp
while(x > 1){ x /= spf[x]; cnt++; }
X ^= cnt;
}
cout << (X ? "An" : "Binh");
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
M = max(a) + 1
spf = list(range(M)) # ước nguyên tố nhỏ nhất
r = int(M ** 0.5) + 1
is_p = bytearray([1]) * (r + 1)
primes = []
for i in range(2, r + 1):
if is_p[i]:
primes.append(i)
is_p[i * i::i] = bytearray(len(range(i * i, r + 1, i)))
for p in reversed(primes): # số nguyên tố nhỏ ghi đè sau cùng
if p * p < M:
spf[p * p::p] = [p] * len(range(p * p, M, p))
X = 0
for x in a:
c = 0 # Omega(x)
while x > 1:
x //= spf[x]; c += 1
X ^= c
print("An" if X else "Binh")
main()Vậy là em đã hoàn thành trọn vẹn series Thuật toán chuyên sâu. Cảm ơn em đã kiên trì đi cùng mình qua mười bài học dày đặc này. Chúc em giữ nhịp luyện tập đều đặn và đạt kết quả thật tốt ở kỳ thi HSG sắp tới!
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét