Chuyên đề 10: Vét cạn thông minh và tối ưu vòng lặp trong C++ và Python: đếm số phép tính, thu hẹp vòng lặp, đếm cặp bằng mảng đếm, ăn điểm subtask
Lời mở đầu
Gần như mọi đề thi HSG đều chia điểm theo subtask: 30–50% số test có $n$ nhỏ, phần còn lại $n$ rất lớn. Bạn nào viết được lời giải vét cạn (thử hết mọi khả năng) chắc chắn đúng là đã cầm điểm của subtask nhỏ. Bạn nào biết bỏ bớt vòng lặp (tính ra thay vì thử, thu hẹp phạm vi, dùng mảng đếm thay cho vòng lặp thứ hai) thì lấy thêm những subtask lớn. Khoảng cách giữa 40 điểm và 100 điểm nhiều khi chỉ là một vòng for.
Chuyên đề cuối cùng của phần nhập môn này nối ba bài cũ lại với nhau: vòng lặp và vòng lặp lồng nhau ở bài 4, cách đếm số phép tính và quy tắc $10^8$ phép mỗi giây ở bài 9, mảng đánh dấu và đếm phân phối ở bài 13. Em sẽ thấy cùng một bài toán được giải bằng ba cách, nhanh dần, và tận mắt đếm xem mỗi cách tốn bao nhiêu phép thử.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Vét cạn đúng trước đã
Vét cạn (duyệt toàn bộ) là cách giải “thử hết mọi khả năng, khả năng nào thoả đề thì đếm hoặc ghi nhận”. Nó không cần ý tưởng thông minh nào, nên gần như không thể sai. Trước khi gõ code vét cạn, em trả lời ba câu hỏi:
- Một “khả năng” là gì? Một số, một cặp chỉ số, một bộ ba giá trị, một đoạn con, một tập con…
- Có bao nhiêu khả năng? Đây là số lần thân vòng lặp chạy.
- Kiểm tra một khả năng tốn bao lâu? Một phép so sánh, hay lại một vòng lặp nữa?
Nhân hai số cuối với nhau là ra tổng số phép tính, rồi so với khoảng $10^8$ phép mỗi giây như đã học ở bài 9. Bảng dưới đây em nên thuộc:
| Duyệt cái gì | Cách viết | Số khả năng | $n = 100$ | $n = 1000$ |
|---|---|---|---|---|
| mọi số $1..n$ | 1 vòng | $n$ | 100 | 1000 |
| mọi cặp $i < j$ | 2 vòng lồng nhau | $\frac{n(n-1)}{2}$ | 4 950 | ≈ $5 \cdot 10^5$ |
| mọi bộ ba $i < j < k$ | 3 vòng lồng nhau | $\frac{n(n-1)(n-2)}{6}$ | 161 700 | ≈ $1{,}7 \cdot 10^8$ |
| mọi bộ $(a, b, c)$, mỗi biến $1..n$ | 3 vòng lồng nhau | $n^3$ | $10^6$ | $10^9$ |
| mọi đoạn con $[l, r]$, tính tổng lại từ đầu | 3 vòng | ≈ $\frac{n^3}{6}$ | ≈ $1{,}7 \cdot 10^5$ | ≈ $1{,}7 \cdot 10^8$ |
| mọi tập con | đệ quy hoặc bitmask | $2^n$ | ≈ $10^{30}$ | không tưởng |
| mọi hoán vị | đệ quy | $n!$ | không tưởng | không tưởng |
Bảng 1. Số khả năng của các kiểu duyệt hay gặp. Ô đỏ là lúc vét cạn không còn chạy kịp 1 giây. Duyệt tập con và hoán vị em sẽ học ở bài 15.
Bài toán mẫu của cả chuyên đề. Cho $n$ và $S$. Đếm số bộ ba số nguyên $(a, b, c)$ với $1 \le a, b, c \le n$ và $a + b + c = S$ (thứ tự có ý nghĩa: $(1, 2, 3)$ và $(3, 2, 1)$ là hai bộ khác nhau). Ví dụ $n = 4$, $S = 6$: có 10 bộ, gồm $(2, 2, 2)$, 3 hoán vị của $(1, 1, 4)$ và 6 hoán vị của $(1, 2, 3)$. Vét cạn: ba vòng lặp, mỗi biến chạy từ 1 tới $n$, đếm những bộ có tổng bằng $S$.
Xem code C++ / Python: vét cạn ba vòng lặp đếm bộ (a, b, c) có tổng S (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, S;
cin >> n >> S;
long long cnt = 0;
for(int a = 1; a <= n; a++)
for(int b = 1; b <= n; b++)
for(int c = 1; c <= n; c++)
if(a + b + c == S) cnt++; // thử đủ n^3 bộ
cout << cnt;
return 0;
}n, S = map(int, input().split())
cnt = 0
for a in range(1, n + 1):
for b in range(1, n + 1):
for c in range(1, n + 1):
if a + b + c == S: # thử đủ n^3 bộ
cnt += 1
print(cnt)Code này đúng, nhưng có $n^3$ lần thử. Với $n = 100$ là $10^6$ phép, chạy ngay. Với $n = 1000$ là $10^9$ phép, khoảng 10 giây: quá thời gian. Nếu đề ghi “subtask 1 (40% số test): $n \le 100$” thì chừng ấy code đã mang về 40% số điểm. Đó là lý do câu thần chú của chuyên đề này là: viết vét cạn đúng trước, tối ưu sau.
2. Làm “trâu” để chấm bài. Sinh test nhỏ ngẫu nhiên, so kết quả lời giải nhanh với vét cạn; lệch là biết lời giải nhanh sai (kỹ thuật chấm trâu ở bài 22).
3. Tìm quy luật. In kết quả vét cạn với $n = 1, 2, 3, \ldots$, nhiều khi nhìn bảng số là đoán ra công thức.
int bị tràn. Code trâu sai thì chấm trâu cũng vô nghĩa, nên hãy viết nó thật “ngây thơ”, đúng từng chữ của đề.Phần 2Thu hẹp phạm vi vòng lặp
Mẹo 1: biến cuối cùng bị “ép”, đừng duyệt nó. Trong bài mẫu, khi đã chọn $a$ và $b$ thì $c$ chỉ có một giá trị khả dĩ: $c = S - a - b$. Vòng lặp thứ ba chạy $n$ lần chỉ để tìm ra đúng con số đó, quá lãng phí! Ta tính thẳng $c$, rồi kiểm tra $1 \le c \le n$. Số lần thử giảm từ $n^3$ xuống $n^2$.
Xem code C++ / Python: hai vòng lặp, tính ra biến thứ ba (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, S;
cin >> n >> S;
long long cnt = 0;
for(int a = 1; a <= n; a++)
for(int b = 1; b <= n; b++){
int c = S - a - b; // c bị "ép", không cần vòng thứ ba
if(c >= 1 && c <= n) cnt++;
}
cout << cnt;
return 0;
}n, S = map(int, input().split())
cnt = 0
for a in range(1, n + 1):
for b in range(1, n + 1):
c = S - a - b # c bị "ép", không cần vòng thứ ba
if 1 <= c <= n:
cnt += 1
print(cnt)Mẹo 2: bỏ thêm một vòng bằng công thức đếm. Cố định $a$, đặt $T = S - a$. Ta cần đếm số $b$ sao cho cả $b$ và $c = T - b$ đều nằm trong $[1, n]$:
- $1 \le b \le n$;
- $1 \le T - b \le n$, tức là $T - n \le b \le T - 1$.
Giao hai đoạn lại: $b$ chạy trong $[\max(1, T - n),\ \min(n, T - 1)]$. Số giá trị nguyên trong đoạn $[lo, hi]$ là $hi - lo + 1$ nếu $lo \le hi$, ngược lại là 0. Vòng lặp theo $b$ biến mất, chỉ còn một vòng theo $a$: $O(n)$.
Hình 1. Thay vì thử từng $b$, ta tìm đoạn các giá trị $b$ hợp lệ bằng cách giao hai đoạn, rồi lấy độ dài đoạn giao.
Em bấm Tự chạy để xem ba cách cùng đếm một bài. Bảng bên trái là mọi cặp $(b, c)$ khi đã cố định $a$; cách 1 phải đi qua cả bảng, cách 2 đi một ô mỗi hàng, cách 3 chỉ đo độ dài đường chéo xanh:
Xem code C++ / Python: một vòng lặp và công thức đếm đoạn, $O(n)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n, S;
cin >> n >> S;
long long cnt = 0;
for(long long a = 1; a <= n; a++){
long long T = S - a; // cần b + c = T
long long lo = max(1LL, T - n); // c = T - b <= n => b >= T - n
long long hi = min(n, T - 1); // c = T - b >= 1 => b <= T - 1
if(lo <= hi) cnt += hi - lo + 1; // đếm cả đoạn b một lúc
}
cout << cnt;
return 0;
}n, S = map(int, input().split())
cnt = 0
for a in range(1, n + 1):
T = S - a # cần b + c = T
lo = T - n if T - n > 1 else 1 # max(1, T - n): c = T - b <= n => b >= T - n
hi = T - 1 if T - 1 < n else n # min(n, T - 1): c = T - b >= 1 => b <= T - 1
if lo <= hi:
cnt += hi - lo + 1 # đếm cả đoạn b một lúc
print(cnt)| Cách | Số vòng lặp | Số phép thử | $n = 1000$ | $n = 10^6$ |
|---|---|---|---|---|
| Vét cạn $a, b, c$ | 3 | $n^3$ | $10^9$ (≈ 10 giây) | không tưởng |
| Tính ra $c$ | 2 | $n^2$ | $10^6$ | $10^{12}$ |
| Công thức đếm $b$ | 1 | $n$ | $1000$ | $10^6$ |
Bảng 2. Mỗi lần bỏ được một vòng lặp, thời gian chạy chia cho $n$.
Mẹo 3: dùng thứ tự để cắt bớt. Khi đề hỏi bộ không có thứ tự (ví dụ ba cạnh tam giác), ta chỉ đếm bộ có $a \le b \le c$. Điều kiện này cho thêm giới hạn rất mạnh:
- $a$ là số nhỏ nhất nên $3a \le a + b + c = n$, tức $a \le n / 3$;
- $b \le c = n - a - b$ nên $b \le (n - a) / 2$; và $b$ bắt đầu từ $a$ chứ không từ 1.
Bài kinh điển: đếm số tam giác có ba cạnh nguyên và chu vi $n$ (hai tam giác chỉ khác thứ tự cạnh tính là một). Với $a \le b \le c$, ba số là ba cạnh tam giác khi và chỉ khi $a + b > c$ (chỉ cần kiểm tra với cạnh lớn nhất). Ví dụ $n = 12$ có 3 tam giác: $(2, 5, 5)$, $(3, 4, 5)$, $(4, 4, 4)$. Mô phỏng dưới đây tô mờ mọi ô mà giới hạn mới cho phép bỏ qua:
Xem code C++ / Python: đếm tam giác chu vi n với vòng lặp đã thu hẹp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
long long cnt = 0;
for(int a = 1; 3 * a <= n; a++) // a là cạnh nhỏ nhất: 3a <= n
for(int b = a; b <= (n - a) / 2; b++){ // a <= b <= c
int c = n - a - b; // tính ra, không cần vòng thứ ba
if(a + b > c) cnt++; // điều kiện tam giác (cạnh lớn nhất là c)
}
cout << cnt;
return 0;
}n = int(input())
cnt = 0
a = 1
while 3 * a <= n: # a là cạnh nhỏ nhất: 3a <= n
for b in range(a, (n - a) // 2 + 1): # a <= b <= c
c = n - a - b # tính ra, không cần vòng thứ ba
if a + b > c: # điều kiện tam giác (cạnh lớn nhất là c)
cnt += 1
a += 1
print(cnt)Vùng được xét chỉ cỡ $\frac{n^2}{12}$ ô: với $n = 5000$ là khoảng $2 \cdot 10^6$ lần thử, so với $1{,}25 \cdot 10^{11}$ của ba vòng $1..n$. Ở bài tập 6 em sẽ dùng thêm mẹo 2 để đưa bài này về $O(n)$.
Mẹo 4: giới hạn kiểu $a^2 \le n$. Đếm số cách viết $n = a^2 + b^2$ với $0 \le a \le b$: vì $a \le b$ nên $2a^2 \le n$, $a$ chỉ chạy tới khoảng $\sqrt{n/2}$, còn $b$ được ép bằng $\sqrt{n - a^2}$ và chỉ cần kiểm tra có phải số nguyên không. Với $n = 10^{12}$, vòng lặp chạy khoảng $7 \cdot 10^5$ lần thay vì $10^{12}$ (bài tập 4). Tương tự, khi tìm ước của $n$ chỉ cần duyệt $i$ với $i \cdot i \le n$ như em đã biết.
for(long long a = 0; 2 * a * a <= n; a++) thay vì a <= sqrt(n / 2). Hàm sqrt trả về số thực và có thể sai lệch ở số lớn (xem chuyên đề 2), còn phép nhân số nguyên thì chính xác tuyệt đối. Nhớ dùng long long vì a * a có thể vượt int. Khi cần căn nguyên, tính b = sqrtl(x) rồi chỉnh lại bằng hai vòng while, hoặc dùng math.isqrt trong Python.Phần 3Đếm cặp, đếm bộ bằng mảng đếm thay cho vòng lặp
Bài: cho dãy $n$ số ($0 \le a_i \le 10^6$) và số $k$. Đếm số cặp chỉ số $i < j$ có $a_i + a_j = k$. Vét cạn hai vòng $i$, $j$ tốn $\frac{n(n-1)}{2}$ phép, $n = 2 \cdot 10^5$ là $2 \cdot 10^{10}$: quá chậm.
Lật ngược câu hỏi: đứng ở vị trí $j$, số $a_j$ cần một “bạn cặp” có giá trị đúng bằng $k - a_j$ ở phía trước. Câu hỏi “phía trước có bao nhiêu số bằng $v$?” chính là việc của mảng đếm ở bài 13: cnt[v] = số lần giá trị $v$ đã xuất hiện. Vậy khi đi từ trái sang phải:
- cộng
ans += cnt[k - a[j]](ghép $a_j$ với mọi bạn cặp đứng trước); - rồi mới
cnt[a[j]]++(để $a_j$ làm bạn cặp cho những số đứng sau).
Thứ tự “cộng trước, tăng sau” giúp mỗi cặp được đếm đúng một lần (lúc gặp số đứng sau) và một số không bao giờ tự ghép với chính nó. Vòng lặp thứ hai đã được thay bằng một lần tra mảng $O(1)$.
| $j$ | $a_j$ | cần giá trị | cnt của giá trị đó | ans | sau khi tăng cnt |
|---|---|---|---|---|---|
| 0 | 1 | 5 | 0 | 0 | cnt[1] = 1 |
| 1 | 5 | 1 | 1 | 1 | cnt[5] = 1 |
| 2 | 3 | 3 | 0 | 1 | cnt[3] = 1 |
| 3 | 4 | 2 | 0 | 1 | cnt[4] = 1 |
| 4 | 2 | 4 | 1 | 2 | cnt[2] = 1 |
| 5 | 3 | 3 | 1 | 3 | cnt[3] = 2 |
Bảng 3. Dãy 1 5 3 4 2 3 với $k = 6$. Ba cặp là (1, 5), (4, 2) và (3, 3) ở vị trí 2 và 5.
Xem code C++ / Python: đếm cặp có tổng bằng k bằng mảng đếm, $O(n)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int cnt[2000005]; // 0 <= a[i] <= 10^6, 0 <= k <= 2*10^6
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
long long ans = 0;
for(int j = 0; j < n; j++){
int x;
cin >> x;
if(k - x >= 0) ans += cnt[k - x]; // ghép x với các số đứng TRƯỚC nó
cnt[x]++; // rồi mới cho x vào mảng đếm
}
cout << ans;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
MAXV = 10**6
cnt = [0] * (MAXV + 1)
ans = 0
for x in map(int, data[2:2 + n]):
if 0 <= k - x <= MAXV:
ans += cnt[k - x] # ghép x với các số đứng TRƯỚC nó
cnt[x] += 1 # rồi mới cho x vào mảng đếm
print(ans)map (C++) hoặc dict (Python) như ở bài 11, ý tưởng giữ nguyên. Một cách khác là sắp xếp rồi dùng hai con trỏ (sẽ học ở bài 17). Nếu giá trị âm nhưng nhỏ, cộng thêm một hằng số OFFSET cho mọi chỉ số.Đếm cặp có tổng chia hết cho $k$. Tổng $a_i + a_j$ chia hết cho $k$ chỉ phụ thuộc vào số dư của hai số: nếu $a_j$ dư $r$ thì bạn cặp phải dư $(k - r) \bmod k$ (phép % k lần nữa để $r = 0$ ghép với dư 0 chứ không phải dư $k$). Vậy mảng đếm chỉ cần $k$ ô, đếm theo số dư thay vì theo giá trị, và giá trị $a_i$ lớn bao nhiêu cũng được:
Hình 2. Với $k = 5$: nhóm dư 0 tự ghép với nhau, dư 1 ghép dư 4, dư 2 ghép dư 3. Với $k$ chẵn, nhóm dư $k/2$ cũng tự ghép với nhau.
Xem code C++ / Python: đếm cặp có tổng chia hết cho k theo số dư (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> cnt(k, 0); // cnt[r] = số phần tử đã gặp có dư r
long long ans = 0;
for(int i = 0; i < n; i++){
long long x;
cin >> x;
int r = x % k;
ans += cnt[(k - r) % k]; // bạn cặp phải có dư (k - r) % k
cnt[r]++;
}
cout << ans;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
cnt = [0] * k # cnt[r] = số phần tử đã gặp có dư r
ans = 0
for x in map(int, data[2:2 + n]):
r = x % k
ans += cnt[(k - r) % k] # bạn cặp phải có dư (k - r) % k
cnt[r] += 1
print(ans)Nếu chỉ cần đáp án (không cần đi từng bước) thì còn gọn hơn: đếm xong cả mảng cnt rồi ghép từng cặp nhóm. Với $k = 3$: đáp án $= C(\text{cnt}_0, 2) + \text{cnt}_1 \cdot \text{cnt}_2$, trong đó $C(x, 2) = \frac{x(x-1)}{2}$. Trường hợp $k = 2$ chính là tính chẵn lẻ, dạng xuất hiện rất nhiều trong đề:
| Câu hỏi về cặp $i < j$ | Khi nào đúng | Công thức ($c$ = số chẵn, $l$ = số lẻ) |
|---|---|---|
| tổng $a_i + a_j$ chẵn | cùng chẵn hoặc cùng lẻ | $C(c, 2) + C(l, 2)$ |
| tổng $a_i + a_j$ lẻ | một chẵn, một lẻ | $c \cdot l$ |
| hiệu $a_i - a_j$ chẵn | giống tổng chẵn | $C(c, 2) + C(l, 2)$ |
| tích $a_i \cdot a_j$ chẵn | có ít nhất một số chẵn | $C(n, 2) - C(l, 2)$ |
| tích $a_i \cdot a_j$ lẻ | cả hai đều lẻ | $C(l, 2)$ |
Bảng 4. Đếm cặp theo tính chẵn lẻ: chỉ cần hai biến đếm, không cần vòng lặp lồng nhau. Mẹo “đếm phần bù” ở dòng tích chẵn: tổng số cặp trừ đi số cặp không thoả.
long long, và khi tính $\frac{x(x-1)}{2}$ phải ép $x$ sang long long trước khi nhân. Một lỗi nữa: với số âm, x % k trong C++ cho số dư âm, phải sửa thành ((x % k) + k) % k.Phần 4Duyệt theo đáp án thay vì theo dữ liệu, và dừng sớm
Thói quen của người mới là vòng lặp luôn chạy trên dữ liệu vào: mọi phần tử, mọi cặp phần tử. Nhiều bài nhanh hơn hẳn nếu ta chạy vòng lặp trên đáp án hoặc trên một thứ nhỏ hơn dữ liệu.
Ví dụ 1: duyệt đáp án và chứng minh nó dừng sớm. Cho $n \le 10^{18}$, tìm số $m \ge n$ nhỏ nhất có tổng chữ số chia hết cho 10. Nghe như phải tìm công thức phức tạp, nhưng cứ thử $m = n, n + 1, n + 2, \ldots$ là được, vì vòng lặp chắc chắn dừng rất sớm: trong $n, n + 1, \ldots, n + 18$ luôn có đủ một “chục” trọn vẹn $\overline{x0}, \overline{x1}, \ldots, \overline{x9}$, mà tổng chữ số của mười số đó là mười số liên tiếp, nên có một số chia hết cho 10. Vậy mỗi câu hỏi thử không quá 19 số.
| $n$ | Các số thử | Đáp án |
|---|---|---|
| 1 | 1, 2, …, 19 (tổng chữ số 1, 2, …, 9, 1, 2, …, 10) | 19 |
| 20 | 20 (2), 21 (3), …, 28 (10) | 28 |
| 1999 | 1999 (28), 2000 (2), 2001 (3), …, 2008 (10) | 2008 |
| $10^{18}$ | tổng chữ số 1, 2, …, 10 | $10^{18} + 9$ |
Bảng 5. Duyệt từ $n$ trở lên. Ví dụ 1999: số tiếp theo nhảy qua chục mới nên tổng chữ số tụt về 2, nhưng sau đó tăng đều tới 10.
Xem code C++ / Python: duyệt đáp án: số nhỏ nhất có tổng chữ số chia hết cho 10 (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int digitSum(long long x){
int s = 0;
while(x > 0){ s += x % 10; x /= 10; }
return s;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int q;
cin >> q;
while(q--){
long long n;
cin >> n;
long long m = n;
while(digitSum(m) % 10 != 0) m++; // duyệt đáp án; chắc chắn dừng sau tối đa 19 số
cout << m << "\n";
}
return 0;
}import sys
def digit_sum(x):
return sum(map(int, str(x)))
data = sys.stdin.read().split()
q = int(data[0])
out = []
for t in range(1, q + 1):
m = int(data[t])
while digit_sum(m) % 10 != 0: # duyệt đáp án; chắc chắn dừng sau tối đa 19 số
m += 1
out.append(str(m))
print('\n'.join(out))Ví dụ 2: duyệt theo giá trị khi giá trị nhỏ. Dãy có $n = 2 \cdot 10^5$ phần tử nhưng mỗi $a_i \le 100$. Đếm bộ ba chỉ số $i < j < k$ có tổng bằng $S$: ba vòng theo chỉ số là $10^{15}$ phép. Nhưng chỉ có 100 giá trị khác nhau! Đếm cnt[v], rồi duyệt bộ giá trị $u \le v \le w$ với $w = S - u - v$ (lại là mẹo “biến cuối bị ép”), và nhân số cách chọn chỉ số: $\text{cnt}[u] \cdot \text{cnt}[v] \cdot \text{cnt}[w]$ nếu ba giá trị khác nhau, $C(\text{cnt}[u], 2) \cdot \text{cnt}[w]$ nếu $u = v < w$… Tổng cộng chưa tới $100^2$ phép (bài tập 8).
Ví dụ 3: vòng trong chạy theo bội. Vòng for(j = i; j <= n; j += i) chạy $n / i$ lần, cả hai vòng tốn $\frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} \approx n \ln n$ phép, với $n = 10^6$ chỉ khoảng $1{,}4 \cdot 10^7$. Đây là nền tảng của sàng ước, đếm ước cho mọi số đã gặp ở chuyên đề 6. Nhìn hai vòng lồng nhau đừng vội kết luận $O(n^2)$: phải đếm xem vòng trong thực sự chạy bao nhiêu lần.
| Vòng trong | Tổng số lần chạy | $n = 10^5$ |
|---|---|---|
for(j = 1; j <= n; j++) | $n^2$ | $10^{10}$ |
for(j = i + 1; j <= n; j++) | $\frac{n(n-1)}{2}$ | $5 \cdot 10^9$ |
for(j = i; j <= n; j += i) | $\approx n \ln n$ | $1{,}2 \cdot 10^6$ |
for(j = 1; j * j <= i; j++) | $\approx \frac{2}{3} n \sqrt{n}$ | $2 \cdot 10^7$ |
for(j = i; j > 0; j /= 2) | $\approx n \log_2 n$ | $1{,}7 \cdot 10^6$ |
Bảng 6. Hai vòng lồng nhau, vòng ngoài i = 1..n, nhưng số phép tính rất khác nhau tuỳ vòng trong.
Dừng sớm bằng break. Khi biến chạy tăng dần và điều kiện “đã vượt thì càng về sau càng vượt”, hãy thoát ngay: duyệt $b$ tăng dần mà $a^2 + b^2 > n$ thì các $b$ sau cũng vượt; dãy đã sắp xếp tăng mà $a_i + a_j > k$ thì các $j$ sau cũng vượt. Khi đề chỉ hỏi “có tồn tại hay không”, tìm thấy một khả năng là break luôn. Dừng sớm không đổi độ phức tạp trong trường hợp xấu nhất, nhưng thường giúp code vét cạn ăn thêm vài test.
break chỉ thoát vòng trong cùng chứa nó (bài 4). Muốn thoát cả hai vòng khi tìm thấy, hãy đặt hai vòng vào một hàm rồi return, hoặc dùng biến cờ found và kiểm tra nó ở vòng ngoài.Phần 5Bảng giới hạn và quy trình chia subtask
Đọc giới hạn của $n$ là đoán được đề muốn độ phức tạp nào, từ đó biết được phép lồng bao nhiêu vòng lặp. Bài 9 và bài 22 đã giải thích cách ước lượng; bảng dưới đây tóm tắt lại theo góc nhìn “vòng lặp”, kèm kỹ thuật tương ứng trong chuyên đề này:
| Giới hạn $n$ | Độ phức tạp chấp nhận | Vòng lặp lồng nhau | Kỹ thuật thường dùng |
|---|---|---|---|
| $n \le 10$ | $O(n!)$, $O(n^6)$ | duyệt hoán vị, 6 vòng | vét cạn mọi cấu hình |
| $n \le 20$ | $O(2^n \cdot n)$ | duyệt tập con | vét cạn tập con (bài 15, bài 20) |
| $n \le 500$ | $O(n^3)$ | 3 vòng | vét cạn ba biến |
| $n \le 5000$ | $O(n^2)$ | 2 vòng | tính ra biến cuối, thu hẹp phạm vi |
| $n \le 10^6$ | $O(n)$, $O(n \log n)$ | 1 vòng (+ sắp xếp) | mảng đếm, công thức đếm đoạn, cộng dồn |
| $n \le 10^{12}$ | $O(\sqrt{n})$ | 1 vòng tới căn | $a^2 \le n$, duyệt ước |
| $n \le 10^{18}$ | $O(\log n)$, $O(1)$ | không vòng (hoặc theo chữ số) | công thức, duyệt đáp án ngắn |
Bảng 7. Giới hạn của $n$ cho biết số vòng lặp được phép lồng nhau (với khoảng 1 giây, $10^8$ phép).
Quy trình 4 bước khi gặp bài có subtask:
- Đọc hết các subtask và ghi điểm của từng cái. Có subtask đặc biệt (giá trị nhỏ, dãy toàn số dương, $k = 1$…) thì gạch chân, vì đó là gợi ý của người ra đề.
- Viết vét cạn cho subtask nhỏ nhất, chạy đúng ví dụ, nộp hoặc lưu lại. Đây là điểm “ăn chắc”.
- Gọt từng vòng lặp: biến cuối bị ép? thu hẹp được phạm vi? thay vòng trong bằng mảng đếm hay công thức? Mỗi lần bỏ một vòng là mở khoá subtask kế tiếp.
- Chấm trâu bản nhanh với bản vét cạn trên nhiều test nhỏ ngẫu nhiên trước khi nộp. Giữ cả hai trong cùng một chương trình và chọn theo dữ liệu vào: test nhỏ chạy vét cạn (không thể sai), test lớn mới chạy bản nhanh.
Code dưới đây là khung mẫu cho bài đếm cặp có tổng bằng $k$ với ba subtask: $n \le 2000$; giá trị trong $[0, 10^6]$; và giá trị tuỳ ý, $|a_i| \le 10^9$.
Xem code C++ / Python: một chương trình, ba subtask: trâu, mảng đếm, map (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n;
long long k;
vector<long long> a;
int cnt[1000005];
long long trau(){ // subtask 1: n <= 2000, O(n^2)
long long ans = 0;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(a[i] + a[j] == k) ans++;
return ans;
}
long long demMang(){ // subtask 2: 0 <= a[i] <= 10^6, O(n)
long long ans = 0;
for(int j = 0; j < n; j++){
long long need = k - a[j];
if(need >= 0 && need <= 1000000) ans += cnt[need];
cnt[a[j]]++;
}
return ans;
}
long long demMap(){ // đầy đủ: giá trị tuỳ ý, O(n log n)
map<long long, int> c;
long long ans = 0;
for(int j = 0; j < n; j++){
auto it = c.find(k - a[j]);
if(it != c.end()) ans += it->second;
c[a[j]]++;
}
return ans;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
a.resize(n);
bool small = true;
for(auto &x : a){
cin >> x;
if(x < 0 || x > 1000000) small = false;
}
if(n <= 2000) cout << trau(); // chắc ăn: code trâu không thể sai
else if(small) cout << demMang();
else cout << demMap();
return 0;
}import sys
def trau(a, k): # subtask 1: n <= 2000, O(n^2)
n = len(a)
return sum(1 for i in range(n) for j in range(i + 1, n) if a[i] + a[j] == k)
def dem_mang(a, k): # subtask 2: 0 <= a[i] <= 10^6, O(n)
cnt = [0] * (10**6 + 1)
ans = 0
for x in a:
if 0 <= k - x <= 10**6:
ans += cnt[k - x]
cnt[x] += 1
return ans
def dem_dict(a, k): # đầy đủ: giá trị tuỳ ý, O(n)
cnt = {}
ans = 0
for x in a:
ans += cnt.get(k - x, 0)
cnt[x] = cnt.get(x, 0) + 1
return ans
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
if n <= 2000:
print(trau(a, k))
elif all(0 <= x <= 10**6 for x in a):
print(dem_mang(a, k))
else:
print(dem_dict(a, k))n <= 2000), không đoán mò.- Đếm số bộ 3 (Dễ)
- Đổi 1 Chữ Số Để Chia Hết Cho 3 (Dễ)
- Cặp Số Chia Hết Cho 3 (BAI3) (Trung bình)
- Tìm 3 Phần Tử Có Tổng Bằng Key (Trung bình)
- Cặp Số Kì Diệu (PAIRS) (Trung bình)
- Dãy Chẵn Lẻ (DAYSO) (Trung bình)
- Chia phần (CHIAPHAN) (Khá)
Bài tậpLuyện vét cạn và tối ưu vòng lặp
Cho hai số nguyên $n$, $S$ ($1 \le n \le 10^6$, $1 \le S \le 3 \cdot 10^6$). Đếm số bộ có thứ tự $(a, b, c)$ gồm các số nguyên thoả $1 \le a, b, c \le n$ và $a + b + c = S$.
4 610📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long. Mẫu: 10 bộ là $(2, 2, 2)$, 3 hoán vị của $(1, 1, 4)$, 6 hoán vị của $(1, 2, 3)$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n, S;
cin >> n >> S;
long long cnt = 0;
for(long long a = 1; a <= n; a++){
long long T = S - a; // cần b + c = T
long long lo = max(1LL, T - n); // c = T - b <= n => b >= T - n
long long hi = min(n, T - 1); // c = T - b >= 1 => b <= T - 1
if(lo <= hi) cnt += hi - lo + 1; // đếm cả đoạn b một lúc
}
cout << cnt;
return 0;
}n, S = map(int, input().split())
cnt = 0
for a in range(1, n + 1):
T = S - a # cần b + c = T
lo = T - n if T - n > 1 else 1 # max(1, T - n): c = T - b <= n => b >= T - n
hi = T - 1 if T - 1 < n else n # min(n, T - 1): c = T - b >= 1 => b <= T - 1
if lo <= hi:
cnt += hi - lo + 1 # đếm cả đoạn b một lúc
print(cnt)Cho dãy $n$ số nguyên ($1 \le n \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Dòng thứ nhất in số cặp $i < j$ có $a_i + a_j$ chẵn, dòng thứ hai in số cặp $i < j$ có $a_i \cdot a_j$ chẵn.
5
1 2 3 4 54
7📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
x % 2 == 0, đừng viết x % 2 == 1 để kiểm tra lẻ.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
long long n, c = 0, l = 0;
cin >> n;
for(int i = 0; i < n; i++){
long long x;
cin >> x;
if(x % 2 == 0) c++; // với số âm lẻ, x % 2 là -1 nên không so với 1
else l++;
}
cout << c * (c - 1) / 2 + l * (l - 1) / 2 << "\n";
cout << n * (n - 1) / 2 - l * (l - 1) / 2;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = sum(1 for x in data[1:n + 1] if int(x) % 2 == 0)
l = n - c
print(c * (c - 1) // 2 + l * (l - 1) // 2)
print(n * (n - 1) // 2 - l * (l - 1) // 2)Có $n$ con trâu và $n$ bó cỏ ($1 \le n \le 10^6$). Trâu đứng ăn 5 bó, trâu nằm ăn 3 bó, ba con trâu già ăn chung 1 bó. Hỏi có bao nhiêu cách chia sao cho mỗi loại trâu có ít nhất một con và ăn vừa hết $n$ bó cỏ? Dòng đầu in số cách, sau đó mỗi dòng in một cách gồm số trâu đứng, trâu nằm, trâu già, theo thứ tự số trâu đứng tăng dần.
1003
4 18 78
8 11 81
12 4 84📝 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(){
long long n;
cin >> n;
vector<array<long long, 3>> res;
for(long long x = 1; 7 * x + 4 <= n; x++){ // 7x + 4y = n, y >= 1
long long r = n - 7 * x;
if(r % 4 != 0) continue;
long long y = r / 4, z = n - x - y;
res.push_back({x, y, z});
}
string out = to_string(res.size()) + "\n";
for(auto &t : res) out += to_string(t[0]) + " " + to_string(t[1]) + " " + to_string(t[2]) + "\n";
cout << out;
return 0;
}n = int(input())
res = []
x = 1
while 7 * x + 4 <= n: # 7x + 4y = n, y >= 1
r = n - 7 * x
if r % 4 == 0:
y = r // 4
res.append(f"{x} {y} {n - x - y}")
x += 1
print(len(res))
if res:
print('\n'.join(res))Cho $n$ ($1 \le n \le 10^{12}$). Đếm số cặp số nguyên $(a, b)$ với $0 \le a \le b$ và $a^2 + b^2 = n$.
252📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
sqrtl rồi chỉnh bằng while, Python dùng math.isqrt. Mẫu: $25 = 0^2 + 5^2 = 3^2 + 4^2$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long isq(long long x){ // căn bậc hai nguyên, chính xác
long long r = sqrtl((long double)x);
while(r * r > x) r--;
while((r + 1) * (r + 1) <= x) r++;
return r;
}
int main(){
long long n;
cin >> n;
long long cnt = 0;
for(long long a = 0; 2 * a * a <= n; a++){ // a <= b => 2a^2 <= n
long long rem = n - a * a;
long long b = isq(rem); // b bị ép
if(b * b == rem) cnt++;
}
cout << cnt;
return 0;
}from math import isqrt
n = int(input())
cnt = 0
for a in range(isqrt(n // 2) + 1): # a <= b => 2a^2 <= n
rem = n - a * a
b = isqrt(rem) # b bị ép
if b * b == rem:
cnt += 1
print(cnt)Cho dãy $n$ số nguyên ($1 \le n \le 2 \cdot 10^5$, $0 \le a_i \le 10^6$) và số $d$ ($0 \le d \le 10^6$). Đếm số cặp chỉ số $i < j$ có $|a_i - a_j| = d$.
6 2
1 5 3 4 2 35📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cnt[x - d] + cnt[x + d] (nhớ kiểm tra chỉ số nằm trong mảng), rồi mới tăng cnt[x]. Bẫy: khi $d = 0$ thì $x - d$ và $x + d$ là một, chỉ được cộng một lần. Mẫu: các cặp (1, 3), (1, 3), (5, 3), (5, 3), (4, 2).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
int cnt[MAXV + 1];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, d;
cin >> n >> d;
long long ans = 0;
for(int i = 0; i < n; i++){
int x;
cin >> x;
if(x - d >= 0) ans += cnt[x - d];
if(d > 0 && x + d <= MAXV) ans += cnt[x + d]; // d = 0: không cộng hai lần
cnt[x]++;
}
cout << ans;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, d = int(data[0]), int(data[1])
MAXV = 10**6
cnt = [0] * (MAXV + 1)
ans = 0
for x in map(int, data[2:2 + n]):
if x - d >= 0:
ans += cnt[x - d]
if d > 0 and x + d <= MAXV: # d = 0: không cộng hai lần
ans += cnt[x + d]
cnt[x] += 1
print(ans)Cho $n$ ($1 \le n \le 10^6$). Đếm số tam giác có ba cạnh là số nguyên dương và chu vi bằng $n$. Hai tam giác chỉ khác nhau về thứ tự cạnh được tính là một.
123📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long. Mẫu: $(2, 5, 5)$, $(3, 4, 5)$, $(4, 4, 4)$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
long long cnt = 0;
for(long long a = 1; 3 * a <= n; a++){
long long lo = max(a, (n - 2 * a) / 2 + 1); // b >= a và a + b > c
long long hi = (n - a) / 2; // b <= c
if(lo <= hi) cnt += hi - lo + 1;
}
cout << cnt;
return 0;
}n = int(input())
cnt = 0
for a in range(1, n // 3 + 1): # 3a <= n
lo = max(a, (n - 2 * a) // 2 + 1) # b >= a và a + b > c
hi = (n - a) // 2 # b <= c
if lo <= hi:
cnt += hi - lo + 1
print(cnt)Cho dãy $n$ số nguyên ($1 \le n \le 2 \cdot 10^5$, $0 \le a_i \le 10^9$). Đếm số bộ ba chỉ số $i < j < k$ sao cho $a_i + a_j + a_k$ chia hết cho 3.
6
1 2 3 4 5 68📝 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;
long long C3(long long x){ return x * (x - 1) * (x - 2) / 6; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
long long c[3] = {0, 0, 0};
for(int i = 0; i < n; i++){
long long x;
cin >> x;
c[x % 3]++;
}
cout << C3(c[0]) + C3(c[1]) + C3(c[2]) + c[0] * c[1] * c[2];
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0, 0, 0]
for x in data[1:n + 1]:
c[int(x) % 3] += 1
C3 = lambda x: x * (x - 1) * (x - 2) // 6
print(C3(c[0]) + C3(c[1]) + C3(c[2]) + c[0] * c[1] * c[2])Cho dãy $n$ số nguyên ($3 \le n \le 2 \cdot 10^5$, $1 \le a_i \le 100$) và số $S$ ($3 \le S \le 300$). Đếm số bộ ba chỉ số $i < j < k$ có $a_i + a_j + a_k = S$.
6 7
1 2 3 4 2 35📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cnt[v]. Duyệt $u \le v$ (giá trị), ép $w = S - u - v$, chỉ nhận $v \le w \le 100$ để mỗi bộ giá trị gặp đúng một lần. Số cách chọn chỉ số: $u < v < w$: $\text{cnt}_u \text{cnt}_v \text{cnt}_w$; $u = v < w$: $C(\text{cnt}_u, 2) \cdot \text{cnt}_w$; $u < v = w$: $\text{cnt}_u \cdot C(\text{cnt}_v, 2)$; $u = v = w$: $C(\text{cnt}_u, 3)$. Tổng chưa tới $10^4$ phép. Mẫu: các bộ giá trị (1, 2, 4) có $1 \cdot 2 \cdot 1 = 2$ cách, (1, 3, 3) có $1 \cdot C(2, 2) = 1$ cách, (2, 2, 3) có $C(2, 2) \cdot 2 = 2$ cách, tổng 5.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long C2(long long x){ return x * (x - 1) / 2; }
long long C3(long long x){ return x * (x - 1) * (x - 2) / 6; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, S;
cin >> n >> S;
long long cnt[105] = {0};
for(int i = 0; i < n; i++){ int x; cin >> x; cnt[x]++; }
long long ans = 0;
for(int u = 1; u <= 100; u++)
for(int v = u; v <= 100; v++){
int w = S - u - v; // w bị ép
if(w < v || w > 100) continue; // giữ u <= v <= w
if(u < v && v < w) ans += cnt[u] * cnt[v] * cnt[w];
else if(u == v && v < w) ans += C2(cnt[u]) * cnt[w];
else if(u < v && v == w) ans += cnt[u] * C2(cnt[v]);
else ans += C3(cnt[u]); // u == v == w
}
cout << ans;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, S = int(data[0]), int(data[1])
cnt = [0] * 101
for x in data[2:2 + n]:
cnt[int(x)] += 1
C2 = lambda x: x * (x - 1) // 2
C3 = lambda x: x * (x - 1) * (x - 2) // 6
ans = 0
for u in range(1, 101):
for v in range(u, 101):
w = S - u - v # w bị ép
if w < v or w > 100: # giữ u <= v <= w
continue
if u < v < w:
ans += cnt[u] * cnt[v] * cnt[w]
elif u == v < w:
ans += C2(cnt[u]) * cnt[w]
elif u < v == w:
ans += cnt[u] * C2(cnt[v])
else: # u == v == w
ans += C3(cnt[u])
print(ans)- 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