Chuyên đề cơ bản 1: Kỹ thuật cộng dồn kết hợp map trong C++ và Python: đếm đoạn con có tổng bằng k, chia hết cho k, XOR tiền tố, đoạn cân bằng
Lời mở đầu
Chào mừng em tới nhóm Chuyên đề cơ bản: bốn bài học thêm dành cho các bạn đã đi hết series Thuật toán cơ bản. Mỗi chuyên đề xoáy sâu vào một dạng bài ra rất nhiều trong đề HSG cấp tỉnh và đề vào chuyên Tin, gom các mẹo, bẫy và cách biến đổi đề mà bài giảng chính chưa có chỗ nói kỹ.
Chuyên đề đầu tiên ghép hai món em đã biết: mảng cộng dồn ở bài 13 và map ở bài 11. Riêng từng món thì quen, nhưng ghép lại ta được một kỹ thuật cực mạnh để đếm đoạn con: thay vì thử mọi cặp $(l, r)$ mất $O(n^2)$, ta đi một vòng từ trái sang phải và hỏi map “trước đây đã gặp bao nhiêu tiền tố có giá trị như thế này?”. Kỹ thuật này còn làm được những việc mà hai con trỏ (bài 17) bó tay, ví dụ khi dãy có số âm.
dict trong Python, tràn số. Có hai khung chạy tay, ba mô phỏng từng bước và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Đếm đoạn con có tổng bằng k
Nhắc nhanh. Với mảng cộng dồn $S_0 = 0$, $S_i = a_1 + a_2 + \ldots + a_i$, tổng đoạn $[l, r]$ là $S_r - S_{l-1}$ (em xem lại phần mảng cộng dồn của bài 13 nếu chưa nhớ). Bài 13 dùng công thức này để trả lời truy vấn tổng đoạn. Hôm nay ta đặt câu hỏi ngược lại:
Cách 1: thử mọi cặp. Có mảng $S$ rồi thì mỗi đoạn kiểm tra trong $O(1)$:
for(int l = 1; l <= n; l++)
for(int r = l; r <= n; r++)
if(S[r] - S[l - 1] == k) ans++; // O(n^2): 2.10^10 phép thử khi n = 2.10^5Đúng nhưng chậm: có $\frac{n(n+1)}{2}$ đoạn, với $n = 2 \cdot 10^5$ là khoảng $2 \cdot 10^{10}$ phép thử, chạy cả phút.
Cách 2: cố định đầu phải $r$, đếm đầu trái bằng map. Biến đổi điều kiện một chút:
$S_r - S_{l-1} = k \iff S_{l-1} = S_r - k$
Vậy với mỗi $r$, số đoạn có tổng $k$ kết thúc tại $r$ chính là số chỉ số $j \in [0, r-1]$ có $S_j = S_r - k$. Nếu ta duyệt $r$ từ trái sang phải và dùng một map cnt ghi lại “giá trị tiền tố $v$ đã xuất hiện bao nhiêu lần”, thì câu trả lời cho mỗi $r$ chỉ là một lần tra cnt[S_r - k]. Tra xong, ta cất $S_r$ vào map để các $r$ phía sau dùng. Toàn bộ thuật toán là $O(n \log n)$ với map, hoặc $O(n)$ trung bình với unordered_map/dict.
Hình 1. Dãy a = [3, 4, 7, 2, −3, 1, 4, 2], k = 7. Hàng ô là các tiền tố S[0..8]. Mỗi cung nối hai tiền tố chênh nhau đúng 7, và ứng với đúng một đoạn con có tổng 7 (ghi trên cung). Có 4 cung nên đáp án là 4.
Bảng dưới chạy tay đúng ví dụ trong hình. Cột “map trước khi hỏi” là trạng thái của cnt ngay trước bước tra:
| r | $a_r$ | $S_r$ | $S_r - k$ | map trước khi hỏi | cnt[$S_r - k$] | ans |
|---|---|---|---|---|---|---|
| 1 | 3 | 3 | −4 | {0:1} | 0 | 0 |
| 2 | 4 | 7 | 0 | {0:1, 3:1} | 1 → đoạn [1..2] | 1 |
| 3 | 7 | 14 | 7 | {0:1, 3:1, 7:1} | 1 → đoạn [3..3] | 2 |
| 4 | 2 | 16 | 9 | {0:1, 3:1, 7:1, 14:1} | 0 | 2 |
| 5 | −3 | 13 | 6 | {…, 16:1} | 0 | 2 |
| 6 | 1 | 14 | 7 | {…, 13:1} | 1 → đoạn [3..6] | 3 |
| 7 | 4 | 18 | 11 | {…, 14:2} | 0 | 3 |
| 8 | 2 | 20 | 13 | {…, 18:1} | 1 → đoạn [6..8] | 4 |
Bảng 1. Đếm đoạn tổng 7: mỗi bước một lần hỏi map, một lần cất. Ở r = 7, map đã có 14 hai lần (r = 3 và r = 6) nhưng ta cần 11 nên không dùng tới.
Em tự nhập dãy khác (có số âm, có số 0) vào mô phỏng để thấy map lớn dần và các tiền tố “khớp” sáng lên như thế nào:
cnt[0] = 1; // tiền tố rỗng
for(int r = 1; r <= n; r++){
S += a[r]; // 1. cập nhật tiền tố
ans += cnt[S - k]; // 2. HỎI: ghép với các tiền tố cũ
cnt[S]++; // 3. CẤT: dành cho các r phía sau
}Xem code C++ / Python: đếm đoạn con có tổng bằng k bằng cộng dồn + map (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long k;
cin >> n >> k;
map<long long, long long> cnt; // cnt[v] = số tiền tố đã gặp có giá trị v
cnt[0] = 1; // tiền tố rỗng S[0] = 0
long long S = 0, ans = 0;
for(int r = 1; r <= n; r++){
long long x; cin >> x;
S += x; // S bây giờ là S[r]
auto it = cnt.find(S - k); // có bao nhiêu S[l-1] = S[r] - k ?
if(it != cnt.end()) ans += it->second;
cnt[S]++; // hỏi xong mới cất S[r] vào map
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
cnt = {0: 1} # tiền tố rỗng S[0] = 0
S = ans = 0
for x in data[2:2 + n]:
S += int(x) # S bây giờ là S[r]
ans += cnt.get(S - k, 0) # có bao nhiêu S[l-1] = S[r] - k ?
cnt[S] = cnt.get(S, 0) + 1 # hỏi xong mới cất S[r]
print(ans)
main()Khung chạy tay dưới đây theo từng dòng của code (bản rút gọn dùng count cho dễ đọc). Em để ý ở mỗi vòng, dòng hỏi luôn chạy trước dòng cất:
cnt[0] = 1: mọi đoạn bắt đầu từ vị trí 1 (ứng với $S_{l-1} = S_0 = 0$) bị bỏ sót. Với ví dụ trên em sẽ ra 3 thay vì 4 vì mất đoạn [1..2].Cất $S_r$ trước rồi mới hỏi: khi $k = 0$, $S_r$ sẽ tự ghép với chính nó, tức là đếm cả “đoạn rỗng” $[r+1, r]$. Dãy
5, $k = 0$ đáp án là 0 nhưng code sai in ra 1. Quy tắc: hỏi trước, cất sau, để $j = l - 1$ luôn nhỏ hơn hẳn $r$.Phần 2Đoạn con có tổng chia hết cho k: đếm theo số dư
Bài toán. Đếm số đoạn con có tổng chia hết cho $k$ ($k \ge 1$). Lần này ta không cần $S_{l-1}$ bằng một giá trị cụ thể nữa:
$k \mid (S_r - S_{l-1}) \iff S_r \bmod k = S_{l-1} \bmod k$
Nghĩa là: hai tiền tố có cùng số dư khi chia cho $k$ thì đoạn nằm giữa chúng có tổng chia hết cho $k$. Vậy ta thay $S$ bằng số dư $d = S \bmod k$ và đếm theo đúng khuôn mẫu, với khoá cần hỏi chính là $d$ (giống bài “tổng bằng 0” trên dãy số dư). Một cách nhìn khác: nếu có $c$ tiền tố cùng số dư thì chúng tạo ra $\binom{c}{2} = \frac{c(c-1)}{2}$ đoạn, đáp án là tổng các $\binom{c}{2}$ trên mọi số dư.
| r | $a_r$ | $S_r$ | $S_r \bmod 5$ | đã có cùng số dư | ans |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | ||
| 1 | 4 | 4 | 4 | 0 | 0 |
| 2 | 5 | 9 | 4 | 1 | 1 |
| 3 | 0 | 9 | 4 | 2 | 3 |
| 4 | −2 | 7 | 2 | 0 | 3 |
| 5 | −3 | 4 | 4 | 3 | 6 |
| 6 | 1 | 5 | 0 | 1 | 7 |
Bảng 2. Dãy [4, 5, 0, −2, −3, 1], k = 5. Số dư 4 xuất hiện 4 lần (r = 1, 2, 3, 5) cho C(4, 2) = 6 đoạn, số dư 0 xuất hiện 2 lần (r = 0, 6) cho 1 đoạn: tổng 7 đoạn.
Bẫy số dư âm. Trong C++ (và Java, Pascal), phép % giữ dấu của số bị chia: -7 % 3 cho −1 chứ không phải 2. Mà $-7$ và $2$ thật ra cùng lớp đồng dư theo 3 (chênh nhau 9). Nếu để nguyên, hai tiền tố $-7$ và $2$ sẽ rơi vào hai ô khác nhau ($-1$ và $2$) và ta đếm thiếu. Cách sửa chuẩn: d = (S % k + k) % k. Python thì % với $k > 0$ luôn trả về số trong $[0, k-1]$ nên không cần sửa. Em xem bước có $S_r$ âm trong mô phỏng sau:
Xem code C++ / Python: đếm đoạn con có tổng chia hết cho k (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long k;
cin >> n >> k;
map<long long, long long> cnt; // cnt[d] = số tiền tố có số dư d
cnt[0] = 1;
long long S = 0, ans = 0;
for(int i = 1; i <= n; i++){
long long x; cin >> x;
S += x;
long long d = (S % k + k) % k; // số dư chuẩn trong [0, k-1], kể cả khi S âm
ans += cnt[d]; // ghép với mọi tiền tố cùng số dư
cnt[d]++;
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
cnt = {0: 1}
S = ans = 0
for x in data[2:2 + n]:
S += int(x)
d = S % k # Python: S % k luôn trong [0, k-1] khi k > 0
ans += cnt.get(d, 0)
cnt[d] = cnt.get(d, 0) + 1
print(ans)
main()long long cnt[k], vừa nhanh hơn vừa không lo bị hack (phần 5). Chỉ khi $k$ lớn tới $10^9$ mới cần map. Nhớ khởi tạo cnt[0] = 1 giống hệt phần 1.Phần 3Đoạn dài nhất có tổng bằng k, đoạn cân bằng
Đổi câu hỏi từ “có bao nhiêu” sang “dài nhất bao nhiêu”. Với mỗi $r$, đoạn $[l, r]$ có tổng $k$ khi $S_{l-1} = S_r - k$, và đoạn dài nhất ứng với $l - 1$ nhỏ nhất. Vậy thay vì đếm số lần, map chỉ cần lưu vị trí đầu tiên mà mỗi giá trị tiền tố xuất hiện: first[v]. Độ dài tốt nhất kết thúc tại $r$ là $r - $first[S_r - k].
Chỗ duy nhất cần cẩn thận: khi gặp lại một giá trị tiền tố đã có, không được ghi đè vị trí mới lên. Vị trí cũ nằm xa hơn về bên trái nên luôn cho đoạn dài hơn. Ví dụ dãy [1, −1, 5, −2, 3], $k = 3$: $S = 0, 1, 0, 5, 3, 6$. Giá trị 0 xuất hiện ở vị trí 0 và 2. Tới $r = 4$, $S_4 = 3$, cần tiền tố bằng 0: dùng vị trí 0 cho đoạn [1..4] dài 4; nếu lỡ ghi đè thành 2 thì chỉ được đoạn [3..4] dài 2.
Mô phỏng dưới đây có hai chế độ: “Tổng bằng k” và “Cân bằng 0/1” (giải thích ngay bên dưới). Em để ý những bước tô đỏ “đã có, không ghi đè”:
Xem code C++ / Python: đoạn con dài nhất có tổng bằng k (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long k;
cin >> n >> k;
map<long long, int> first; // first[v] = vị trí đầu tiên có S[i] = v
first[0] = 0;
long long S = 0;
int best = 0;
for(int r = 1; r <= n; r++){
long long x; cin >> x;
S += x;
auto it = first.find(S - k);
if(it != first.end()) best = max(best, r - it->second);
if(!first.count(S)) first[S] = r; // chỉ ghi lần đầu, không ghi đè
}
cout << best;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
first = {0: 0} # first[v] = vị trí đầu tiên có S[i] = v
S = best = 0
for r in range(1, n + 1):
S += int(data[1 + r])
l = first.get(S - k)
if l is not None and r - l > best:
best = r - l
if S not in first: # chỉ ghi lần đầu, không ghi đè
first[S] = r
print(best)
main()Đoạn cân bằng: mẹo đổi thành $\pm 1$. Rất nhiều đề không nói gì tới “tổng” nhưng vẫn là bài này sau một bước biến đổi:
- Xâu 0/1, đoạn có số chữ 0 bằng số chữ 1: đổi 0 thành $-1$, 1 giữ $+1$. Số chữ 0 bằng số chữ 1 ⇔ tổng đoạn bằng 0.
- Đoạn có số số chẵn bằng số số lẻ: chẵn thành $+1$, lẻ thành $-1$, tìm đoạn tổng 0.
- Đoạn có trung bình cộng bằng $x$: trừ mỗi số đi $x$. Trung bình bằng $x$ ⇔ $\sum (a_i - x) = 0$.
- Đoạn có số chữ A nhiều hơn số chữ B: A thành $+1$, B thành $-1$, chữ khác thành 0, tìm đoạn có tổng $> 0$ (dạng này cần thêm kỹ thuật đếm theo thứ tự, sẽ gặp ở các bài sau).
Ví dụ xâu 0110111000 đổi thành $-1, +1, +1, -1, +1, +1, +1, -1, -1, -1$, tiền tố là $0, -1, 0, 1, 0, 1, 2, 3, 2, 1, 0$. Giá trị 0 xuất hiện ở vị trí 0 và 10, vậy cả xâu dài 10 là đoạn cân bằng dài nhất.
first[2n + 1] và truy cập first[S + n] (dời chỉ số thêm $n$ cho khỏi âm). Đây là cách các bài tập 2 và 6 cài đặt.Phần 4XOR tiền tố và bitmask chẵn lẻ
Khuôn mẫu không chỉ dành cho phép cộng. Điều ta cần chỉ là một phép toán có “phép ngược” để tách tiền tố ra. Với XOR (xem phần XOR của bài 20), phép ngược chính là XOR: $x \oplus x = 0$. Đặt $P_0 = 0$, $P_i = a_1 \oplus a_2 \oplus \ldots \oplus a_i$ thì XOR của đoạn $[l, r]$ là $P_r \oplus P_{l-1}$, và
$P_r \oplus P_{l-1} = k \iff P_{l-1} = P_r \oplus k$
Vẫn đúng khuôn mẫu, chỉ đổi S += a thành P ^= a và khoá cần hỏi thành P ^ k.
| r | $a_r$ | $P_r$ | $P_r \oplus 6$ | đã có | ans |
|---|---|---|---|---|---|
| 1 | 4 | 4 | 2 | 0 | 0 |
| 2 | 2 | 6 | 0 | 1 (P0) → [1..2] | 1 |
| 3 | 2 | 4 | 2 | 0 | 1 |
| 4 | 6 | 2 | 4 | 2 (P1, P3) → [2..4], [4..4] | 3 |
| 5 | 4 | 6 | 0 | 1 (P0) → [1..5] | 4 |
Bảng 3. Dãy [4, 2, 2, 6, 4], k = 6: có 4 đoạn có XOR bằng 6. Chẳng hạn đoạn [2..4]: 2 ⊕ 2 ⊕ 6 = 6.
Xem code C++ / Python: đếm đoạn con có XOR bằng k (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long k;
cin >> n >> k;
map<long long, long long> cnt;
cnt[0] = 1; // P[0] = 0
long long P = 0, ans = 0;
for(int i = 1; i <= n; i++){
long long x; cin >> x;
P ^= x; // P = P[r]
auto it = cnt.find(P ^ k); // cần P[l-1] = P[r] ^ k
if(it != cnt.end()) ans += it->second;
cnt[P]++;
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
cnt = {0: 1} # P[0] = 0
P = ans = 0
for x in data[2:2 + n]:
P ^= int(x) # P = P[r]
ans += cnt.get(P ^ k, 0) # cần P[l-1] = P[r] ^ k
cnt[P] = cnt.get(P, 0) + 1
print(ans)
main()Bitmask chẵn lẻ của 26 chữ cái. Bài toán: cho xâu $s$ gồm chữ thường, đếm số xâu con mà mọi chữ cái đều xuất hiện số chẵn lần. Ta không cần biết mỗi chữ xuất hiện bao nhiêu lần, chỉ cần biết chẵn hay lẻ, nên gói 26 thông tin chẵn/lẻ vào 26 bit của một số nguyên mask: bit thứ $c$ bằng 1 nếu chữ $c$ đã xuất hiện lẻ lần trong tiền tố. Đọc thêm một chữ $c$ thì lật bit $c$: mask ^= 1 << c. Đây chính là XOR tiền tố, với mỗi chữ cái đóng vai một số $2^c$.
Đoạn $[l, r]$ có mọi chữ xuất hiện chẵn lần ⇔ hai tiền tố có cùng mask. Ví dụ abba: mask lần lượt là 0, 1 (a), 3 (ab), 1 (abb), 0 (abba). Mask 0 xuất hiện 2 lần cho đoạn abba, mask 1 xuất hiện 2 lần cho đoạn bb: đáp án 2.
Xem code C++ / Python: đếm xâu con có mọi chữ cái xuất hiện chẵn lần (bitmask) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> s;
unordered_map<int, long long> cnt;
cnt.reserve(s.size() * 2 + 1);
cnt[0] = 1; // tiền tố rỗng: mọi chữ xuất hiện 0 lần (chẵn)
int mask = 0;
long long ans = 0;
for(char c : s){
mask ^= 1 << (c - 'a'); // lật bit chẵn/lẻ của chữ c
ans += cnt[mask]; // cùng mask ⇔ đoạn giữa có mọi chữ xuất hiện chẵn lần
cnt[mask]++;
}
cout << ans;
return 0;
}import sys
def main():
s = sys.stdin.readline().strip()
cnt = {0: 1} # tiền tố rỗng: mọi chữ xuất hiện 0 lần
mask = ans = 0
for c in s:
mask ^= 1 << (ord(c) - 97) # lật bit chẵn/lẻ của chữ c
v = cnt.get(mask, 0)
ans += v
cnt[mask] = v + 1
print(ans)
main()mask ta hỏi thêm 26 khoá mask ^ (1 << c) (hai tiền tố khác nhau đúng một bit). Độ phức tạp $O(26n)$ lần tra map. Bài tập 7 là phiên bản 10 chữ cái, mask nhỏ hơn $2^{10}$ nên dùng hẳn mảng.Phần 5Mảng đếm hay map? unordered_map, dict và tràn số
| Giá trị tiền tố | Ví dụ | Nên dùng |
|---|---|---|
| Nằm trong đoạn nhỏ $[0, V]$, $V \le 10^7$ | số dư khi $k \le 10^6$, mask 10 chữ, số lượng số lẻ | mảng cnt[V + 1] |
| Nằm trong $[-n, n]$ | dãy $\pm 1$: cân bằng 0/1, chẵn/lẻ | mảng cnt[2n + 1], chỉ số S + n |
| Lớn tới $10^{14}$, hoặc mask 26 bit | tổng các $a_i$ tới $10^9$, xâu chữ thường | map / unordered_map (C++), dict (Python) |
| Lớn nhưng muốn chắc chắn $O(n \log n)$ | đề có hack, test chống băm | nén số rồi dùng mảng, hoặc sort các tiền tố |
Bảng 4. Chọn cấu trúc lưu các tiền tố đã gặp. Mask 26 bit có tới $2^{26} \approx 6{,}7 \cdot 10^7$ giá trị, mảng long long cỡ đó tốn 512 MB, nên vẫn phải dùng map.
map hay unordered_map? map là cây cân bằng, mỗi thao tác $O(\log n)$, chậm hơn một chút nhưng ổn định. unordered_map là bảng băm, trung bình $O(1)$, nhưng hàm băm mặc định của số nguyên trong GCC đơn giản tới mức người ta có thể cố ý tạo bộ test làm mọi khoá rơi vào cùng một ô, đẩy mỗi thao tác lên $O(n)$ và cả bài thành $O(n^2)$. Trên Codeforces chuyện này xảy ra thường xuyên ở các vòng có “hack”. Đề HSG chấm bằng test cố định thì hiếm gặp, nhưng thêm một hàm băm có hạt giống ngẫu nhiên là chắc ăn:
Xem code C++ / Python: unordered_map với hàm băm chống hack (và dict an toàn trong Python) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
struct SafeHash { // hàm băm "trộn bit" với hạt giống ngẫu nhiên
static unsigned long long mix(unsigned long long x){
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(long long x) const {
static const unsigned long long SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix((unsigned long long)x + SEED);
}
};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long k;
cin >> n >> k;
unordered_map<long long, long long, SafeHash> cnt;
cnt.reserve(2 * n + 2); // cấp chỗ trước, đỡ phải băm lại nhiều lần
cnt[0] = 1;
long long S = 0, ans = 0;
for(int i = 1; i <= n; i++){
long long x; cin >> x;
S += x;
auto it = cnt.find(S - k);
if(it != cnt.end()) ans += it->second;
cnt[S]++;
}
cout << ans;
return 0;
}import sys, random
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
salt = random.getrandbits(60) # XOR khoá với số ngẫu nhiên: không ai đoán trước được
cnt = {0 ^ salt: 1}
S = ans = 0
for x in data[2:2 + n]:
S += int(x)
ans += cnt.get((S - k) ^ salt, 0)
key = S ^ salt
cnt[key] = cnt.get(key, 0) + 1
print(ans)
main()dict chính là bảng băm. Cách viết nhanh nhất là cnt.get(key, 0). defaultdict(int) và Counter tiện hơn nhưng có một bẫy giống cnt[key] của C++: chỉ cần đọc d[key] là khoá đó bị tạo ra với giá trị 0, map phình to vô ích (với Counter thì đọc không tạo khoá). Băm số nguyên trong Python cũng là hash(x) = x nên về lý thuyết cũng bị hack được; mẹo XOR khoá với một số ngẫu nhiên như code trên giải quyết việc đó.int. Kể cả $S - k$ cũng phải tính trong long long.2. Đáp án: dãy toàn số 0 với $k = 0$ thì mọi đoạn đều thoả, đáp án là $\frac{n(n+1)}{2} \approx 2 \cdot 10^{10}$. Biến
ans và giá trị trong map đều phải là long long.3. Lấy số dư: viết
(S % k + k) % k chứ đừng viết (S + k) % k: cách sau chỉ đúng khi $S \ge -k$.cnt[S - k] trên map/unordered_map sẽ chèn khoá $S - k$ với giá trị 0 nếu chưa có. Kết quả vẫn đúng nhưng map có thể to gấp đôi, chậm hơn và tốn bộ nhớ hơn. Khi chỉ hỏi, hãy dùng find (hoặc count) như code mẫu ở phần 1.- Dãy Chẵn Lẻ (DAYSO) (Trung bình)
- Dây Đèn (HSG9 Hà Nội 2025 – Bài 3) (Trung bình)
- Make Sum Divisible by P (LeetCode 1590) (Trung bình)
- Dãy Số (CAU3) (Khá)
- Chia phần (CHIAPHAN) (Khá)
- Maximum Number of Ways to Partition an Array (LeetCode 2025) (Khó)
Bài tậpLuyện cộng dồn kết hợp map
Một cửa hàng ghi lại $n$ ngày liên tiếp, ngày thứ $i$ có lãi $a_i$ đồng ($a_i$ âm nghĩa là lỗ). Đếm số khoảng ngày liên tiếp mà tổng lãi lỗ đúng bằng 0. $1 \le n \le 2 \cdot 10^5$, $|a_i| \le 10^9$.
6
1 -1 2 -2 3 -36📝 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 n;
cin >> n;
map<long long, long long> cnt;
cnt[0] = 1;
long long S = 0, ans = 0;
for(int i = 0; i < n; i++){
long long x; cin >> x;
S += x;
ans += cnt[S]; // đoạn tổng 0 ⇔ hai tiền tố bằng nhau
cnt[S]++;
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
cnt = {0: 1}
S = ans = 0
for x in data[1:n + 1]:
S += int(x)
v = cnt.get(S, 0) # đoạn tổng 0 ⇔ hai tiền tố bằng nhau
ans += v
cnt[S] = v + 1
print(ans)
main()Cho xâu $s$ chỉ gồm các chữ số 0 và 1, độ dài không quá $2 \cdot 10^5$. Tìm độ dài lớn nhất của một xâu con liên tiếp có số chữ 0 bằng số chữ 1. Nếu không có, in 0.
11010006📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
110100 dài 6.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int n = s.size();
vector<int> first(2 * n + 1, -1); // tiền tố nằm trong [-n, n] → dời thêm n
first[n] = 0; // S[0] = 0
int S = 0, best = 0;
for(int r = 1; r <= n; r++){
S += (s[r - 1] == '1') ? 1 : -1;
if(first[S + n] == -1) first[S + n] = r;
else best = max(best, r - first[S + n]);
}
cout << best;
return 0;
}s = input().strip()
n = len(s)
first = [-1] * (2 * n + 1) # tiền tố nằm trong [-n, n] → dời thêm n
first[n] = 0
S = best = 0
for r in range(1, n + 1):
S += 1 if s[r - 1] == '1' else -1
if first[S + n] == -1:
first[S + n] = r
elif r - first[S + n] > best:
best = r - first[S + n]
print(best)Cho dãy $n$ số nguyên $a_1, \ldots, a_n$ và số nguyên $x$. Đếm số đoạn con liên tiếp có trung bình cộng đúng bằng $x$. $1 \le n \le 2 \cdot 10^5$, $|a_i|, |x| \le 10^9$.
5 3
1 5 3 2 46📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long. Dãy $b$ của ví dụ là −2, 2, 0, −1, 1, tiền tố 0, −2, 0, 0, −1, 0: số 0 xuất hiện 4 lần cho $\binom{4}{2} = 6$ đoạn, đó là [1..2], [1..3], [1..5], [3..3], [3..5], [4..5] (chẳng hạn trung bình của 1 5 3 2 4 đúng bằng 3).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; long long x;
cin >> n >> x;
map<long long, long long> cnt;
cnt[0] = 1;
long long S = 0, ans = 0;
for(int i = 0; i < n; i++){
long long a; cin >> a;
S += a - x; // trung bình bằng x ⇔ tổng (a_i - x) bằng 0
ans += cnt[S];
cnt[S]++;
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, x = int(data[0]), int(data[1])
cnt = {0: 1}
S = ans = 0
for a in data[2:2 + n]:
S += int(a) - x # trung bình bằng x ⇔ tổng (a_i - x) bằng 0
v = cnt.get(S, 0)
ans += v
cnt[S] = v + 1
print(ans)
main()Cho dãy $n$ số nguyên dương và số $m$ ($0 \le m \le n \le 10^6$, $a_i \le 10^9$). Đếm số đoạn con liên tiếp chứa đúng $m$ số lẻ.
6 2
3 2 7 4 5 16📝 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, m;
cin >> n >> m;
vector<long long> cnt(n + 1, 0); // số lẻ trong tiền tố chỉ từ 0 tới n → mảng là đủ
cnt[0] = 1;
int S = 0;
long long ans = 0;
for(int i = 0; i < n; i++){
long long a; cin >> a;
S += (a % 2 != 0);
if(S - m >= 0) ans += cnt[S - m];
cnt[S]++;
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
cnt = [0] * (n + 1) # số lẻ trong tiền tố chỉ từ 0 tới n
cnt[0] = 1
S = ans = 0
for a in data[2:2 + n]:
S += int(a) & 1
if S >= m:
ans += cnt[S - m]
cnt[S] += 1
print(ans)
main()Cho dãy $n$ số nguyên ($n \le 2 \cdot 10^5$, $|a_i| \le 10^9$) và số nguyên dương $k \le 10^9$. Tìm độ dài lớn nhất của một đoạn con liên tiếp có tổng chia hết cho $k$. Nếu không có đoạn nào, in 0.
6 5
3 -8 4 1 6 -24📝 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; long long k;
cin >> n >> k;
map<long long, int> first; // first[d] = vị trí đầu tiên có số dư d
first[0] = 0;
long long S = 0;
int best = 0;
for(int r = 1; r <= n; r++){
long long a; cin >> a;
S += a;
long long d = (S % k + k) % k;
auto it = first.find(d);
if(it == first.end()) first[d] = r;
else best = max(best, r - it->second);
}
cout << best;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
first = {0: 0} # first[d] = vị trí đầu tiên có số dư d
S = best = 0
for r in range(1, n + 1):
S += int(data[1 + r])
d = S % k
l = first.get(d)
if l is None:
first[d] = r
elif r - l > best:
best = r - l
print(best)
main()Cho dãy $n$ số nguyên dương ($n \le 10^6$, $a_i \le 10^9$). Đếm số đoạn con liên tiếp có số lượng số chẵn bằng số lượng số lẻ.
7
2 5 4 4 7 1 69📝 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 cnt[2000005]; // tiền tố trong [-n, n], dời thêm n
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
cnt[n] = 1; // S[0] = 0
int S = 0;
long long ans = 0;
for(int i = 0; i < n; i++){
long long a; cin >> a;
S += (a % 2 == 0) ? 1 : -1; // chẵn +1, lẻ -1
ans += cnt[S + n];
cnt[S + n]++;
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
cnt = [0] * (2 * n + 1) # tiền tố trong [-n, n], dời thêm n
S = n # lưu luôn S + n cho gọn
cnt[S] = 1
ans = 0
for a in data[1:n + 1]:
S += -1 if int(a) & 1 else 1
ans += cnt[S]
cnt[S] += 1
print(ans)
main()Cho xâu $s$ độ dài $n \le 10^5$ chỉ gồm các chữ cái từ a tới j. Một xâu con liên tiếp gọi là gần đối xứng nếu có thể sắp xếp lại các chữ của nó để được một xâu đối xứng. Đếm số xâu con gần đối xứng (các xâu con ở vị trí khác nhau tính là khác nhau).
aba4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
mask và mask ^ (1 << b) với $b = 0..9$. Mask nhỏ hơn $2^{10} = 1024$ nên dùng mảng. Ví dụ aba: 3 xâu một chữ, aba, và hai xâu ab, ba không hợp lệ, đáp án 4.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long cnt[1024]; // 10 chữ cái → mask < 2^10, mảng là đủ
int main(){
string s;
cin >> s;
cnt[0] = 1;
int mask = 0;
long long ans = 0;
for(char c : s){
mask ^= 1 << (c - 'a');
ans += cnt[mask]; // không chữ nào lẻ
for(int b = 0; b < 10; b++)
ans += cnt[mask ^ (1 << b)]; // đúng chữ b lẻ
cnt[mask]++;
}
cout << ans;
return 0;
}import sys
def main():
s = sys.stdin.readline().strip()
cnt = [0] * 1024 # 10 chữ cái → mask < 2^10
cnt[0] = 1
bits = [1 << b for b in range(10)]
mask = ans = 0
for c in s:
mask ^= 1 << (ord(c) - 97)
ans += cnt[mask] # không chữ nào lẻ
ans += sum(cnt[mask ^ t] for t in bits) # đúng một chữ lẻ
cnt[mask] += 1
print(ans)
main()Cho bảng số nguyên $n \times m$ ($1 \le n, m \le 100$, $|a_{ij}| \le 10^4$) và số nguyên $k$. Đếm số hình chữ nhật con (gồm các ô liên tiếp, cạnh song song với cạnh bảng) có tổng các ô đúng bằng $k$.
3 3 2
1 -1 0
2 0 -2
0 1 18📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
col[j]. Hình chữ nhật giữa hai hàng đó, từ cột $j_1$ tới $j_2$, có tổng bằng tổng đoạn col[j1..j2], nên ta quay về đúng bài phần 1 trên dãy col độ dài $m$. Khi tăng hàng dưới thêm 1, chỉ cần cộng thêm hàng mới vào col, không phải tính lại từ đầu. Tổng độ phức tạp $O(n^2 m \log m)$, khoảng $3{,}5 \cdot 10^6$ thao tác map khi $n = m = 100$. (Nếu $n > m$ thì nên xoay bảng để cặp hàng là chiều ngắn hơn.)Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long a[105][105], col[105];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; long long k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
long long ans = 0;
for(int top = 1; top <= n; top++){
for(int j = 1; j <= m; j++) col[j] = 0;
for(int bot = top; bot <= n; bot++){
for(int j = 1; j <= m; j++) col[j] += a[bot][j]; // tổng cột j từ hàng top tới bot
map<long long, int> cnt; // bài 1 chiều trên dãy col
cnt[0] = 1;
long long S = 0;
for(int j = 1; j <= m; j++){
S += col[j];
auto it = cnt.find(S - k);
if(it != cnt.end()) ans += it->second;
cnt[S]++;
}
}
}
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
a = [list(map(int, data[3 + i * m:3 + (i + 1) * m])) for i in range(n)]
ans = 0
for top in range(n):
col = [0] * m
for bot in range(top, n):
row = a[bot]
for j in range(m):
col[j] += row[j] # tổng cột j từ hàng top tới bot
cnt = {0: 1} # bài 1 chiều trên dãy col
S = 0
for v in col:
S += v
ans += cnt.get(S - k, 0)
cnt[S] = cnt.get(S, 0) + 1
print(ans)
main()
- 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