Bài 32: Tổng ôn Thuật toán nâng cao: nhận dạng bài và đề thi thử 6 câu có lời giải C++ và Python
Lời mở đầu
Vậy là em đã đi hết series Thuật toán nâng cao: từ chia để trị ở bài 24 tới Fenwick và segment tree ở bài 31. Học từng bài thì thấy bài nào cũng dễ hiểu, nhưng vào phòng thi, đề không bao giờ ghi “bài này dùng Dijkstra”. Cái khó nhất lúc ấy là nhận ra kỹ thuật cần dùng, và biết ăn điểm từng subtask khi chưa nghĩ ra lời giải đầy đủ.
Giống như bài 23 khép lại series Thuật toán cơ bản, bài này không dạy kỹ thuật mới. Mình sẽ cùng em: vẽ lại bản đồ kiến thức của cả series, luyện cách đọc giới hạn để đoán độ phức tạp, làm một đề thi thử 6 câu từ dễ tới khó, rồi chữa thật kỹ từng câu, đi từ vét cạn lấy điểm subtask tới lời giải tối ưu. Em nhớ tự làm đề trước (bấm giờ 180 phút), sau đó mới đọc lời giải nhé.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Bản đồ kiến thức của series
Bảng dưới đây là “tờ giấy nhớ” của cả series. Cột quan trọng nhất là dấu hiệu trong đề: đó là những cụm từ, những kiểu giới hạn mà hễ nhìn thấy là em phải nghĩ ngay tới kỹ thuật tương ứng. Bấm vào tên bài để mở lại lý thuyết khi cần.
| Kỹ thuật | Bài | Dấu hiệu trong đề | Độ phức tạp |
|---|---|---|---|
| Merge sort, đếm nghịch thế | Bài 24 | đếm cặp $i < j$ mà $a_i > a_j$; “số lần đổi chỗ kề nhau” | $O(n \log n)$ |
Quickselect, nth_element | Bài 24 | số nhỏ thứ $k$, trung vị, $n$ tới $10^7$ | $O(n)$ TB |
| Ngăn xếp đơn điệu | Bài 25 | “gần nhất bên trái/phải lớn hơn”, hình chữ nhật lớn nhất | $O(n)$ |
| Hàng đợi đơn điệu (deque) | Bài 25 | min/max mọi đoạn dài $k$, cửa sổ trượt, QHĐ $f_i = \min f_j + \ldots$ với $j$ trong cửa sổ | $O(n)$ |
| Lũy thừa nhanh, nghịch đảo modulo | Bài 26 | “in theo modulo $10^9+7$”, số mũ tới $10^{18}$, phép chia dưới modulo | $O(\log b)$ |
| Tổ hợp $C(n, k)$ modulo | Bài 26 | đếm số cách chọn, đường đi trên lưới, nhiều truy vấn | $O(N)$ + $O(1)$/truy vấn |
| QHĐ có truy vết | Bài 27 | “in ra một phương án tối ưu” | như QHĐ gốc |
| QHĐ đoạn | Bài 27 | gộp/cắt đoạn liên tiếp, $n \le 500$, nhân ma trận, xâu đối xứng | $O(n^3)$ |
| QHĐ bitmask | Bài 27 | $n \le 20$, “đi qua mỗi đỉnh đúng 1 lần”, phân công | $O(2^n \cdot n^2)$ |
| QHĐ chữ số | Bài 27 | đếm số trong $[L, R]$ với $R \le 10^{18}$ theo tính chất chữ số | $O(\text{số chữ số} \cdot \text{trạng thái})$ |
| Hash xâu | Bài 28 | so sánh nhanh hai xâu con, xâu con lặp lại, kết hợp tìm kiếm nhị phân | $O(n)$ + $O(1)$/so sánh |
| KMP (hàm tiền tố) | Bài 28 | tìm mọi lần xuất hiện của mẫu, chu kỳ nhỏ nhất của xâu | $O(n + m)$ |
| Dijkstra | Bài 29 | đường đi ngắn nhất, trọng số không âm, một nguồn | $O(m \log n)$ |
| BFS 0-1 | Bài 29 | trọng số chỉ 0 hoặc 1 (“miễn phí / tốn 1 lượt”) | $O(n + m)$ |
| Floyd | Bài 29 | mọi cặp đỉnh, $n \le 400$ | $O(n^3)$ |
| Bellman-Ford | Bài 29 | cạnh âm, phát hiện chu trình âm | $O(nm)$ |
| DSU | Bài 30 | gộp nhóm, “cùng nhóm không?”, đếm thành phần khi thêm cạnh | $\approx O(1)$/thao tác |
| Kruskal, Prim | Bài 30 | “nối mọi điểm với chi phí nhỏ nhất”, cây khung nhỏ nhất | $O(m \log m)$ |
| Fenwick (BIT) | Bài 31 | sửa điểm + tổng tiền tố, đếm “bao nhiêu số nhỏ hơn đã gặp” | $O(\log n)$/thao tác |
| Segment tree | Bài 31 | sửa + hỏi min/max/tổng trên đoạn, cập nhật đoạn (lazy) | $O(\log n)$/thao tác |
Bảng 1. Bản đồ kiến thức series Thuật toán nâng cao: kỹ thuật, bài học, dấu hiệu nhận biết và độ phức tạp.
Em để ý: rất nhiều bài thi là tổ hợp của hai kỹ thuật. Đếm nghịch thế làm được bằng merge sort (bài 24) hoặc Fenwick (bài 31). Bài đường đi có “phiếu giảm giá” là Dijkstra (bài 29) trên đồ thị trạng thái, giống cách nghĩ trạng thái của QHĐ (bài 27). Kruskal (bài 30) bản chất là sắp xếp + DSU. Vì vậy khi ôn, đừng chỉ học thuộc từng bài, hãy tự hỏi “kỹ thuật này giải quyết được thao tác gì trong $O(?)$”.
2. Có thao tác gì lặp đi lặp lại? Hỏi tổng đoạn, so sánh xâu con, gộp nhóm, lấy min cửa sổ… Thao tác lặp lại nhiều nhất quyết định cấu trúc dữ liệu.
3. Giới hạn cho phép bao nhiêu? Đây là gợi ý mạnh nhất, Phần 2 sẽ nói kỹ.
Phần 2Đọc giới hạn để chọn thuật toán
Máy chấm thường chạy khoảng $10^8$ phép tính đơn giản mỗi giây (Python chậm hơn chừng 10 – 50 lần). Nhân giới hạn vào công thức độ phức tạp là em biết ngay cách nào qua, cách nào không. Nhắc lại từ bài 9, nhưng nay mỗi dòng đã có thêm “vũ khí” của series này:
| Giới hạn | Độ phức tạp chấp nhận | Kỹ thuật của series nên nghĩ tới |
|---|---|---|
| $n \le 10$ | $O(n!)$ | quay lui (bài 15) thử mọi hoán vị |
| $n \le 20$ | $O(2^n \cdot n)$, $O(2^n \cdot n^2)$ | QHĐ bitmask (bài 27) |
| $n \le 500$ | $O(n^3)$ | QHĐ đoạn (bài 27), Floyd (bài 29) |
| $n \le 5000$ | $O(n^2)$ | QHĐ hai chiều, vét cạn mọi cặp, Bellman-Ford trên đồ thị nhỏ |
| $n \le 2 \cdot 10^5$ | $O(n \log n)$, $O(n \log^2 n)$ | sắp xếp, merge sort (bài 24), Dijkstra (bài 29), Kruskal (bài 30), Fenwick, segment tree (bài 31), hash + chặt nhị phân (bài 28) |
| $n \le 10^6$ – $10^7$ | $O(n)$ | ngăn xếp/hàng đợi đơn điệu (bài 25), KMP (bài 28), giai thừa nghịch đảo (bài 26), BFS 0-1 (bài 29) |
| $n \le 10^{18}$ | $O(\log n)$ hoặc theo số chữ số | lũy thừa nhanh (bài 26), QHĐ chữ số (bài 27), tìm kiếm nhị phân (bài 16) |
Bảng 2. Từ giới hạn tới độ phức tạp và kỹ thuật. Với Python, nên lùi xuống một bậc khi giới hạn sát ngưỡng.
Ca 1: “Đếm số cặp …” với $n \le 2 \cdot 10^5$
Đề nói: đếm số cặp $(i, j)$, $i < j$, thoả một điều kiện so sánh giữa $a_i$ và $a_j$. Nghĩ tới: đếm mọi cặp là $O(n^2) = 4 \cdot 10^{10}$, chắc chắn quá chậm. Cố định $j$, cần đếm nhanh “có bao nhiêu $i$ đứng trước thoả điều kiện” → hoặc Fenwick trên giá trị (thêm dần từng số, hỏi tiền tố), hoặc merge sort đếm lúc trộn. Nếu điều kiện là tổng/hiệu cố định thì có khi chỉ cần map đếm.
Ca 2: “Sau mỗi thao tác, in ra …”
Đề nói: có $q \le 10^5$ thao tác xen kẽ, sau mỗi thao tác in kết quả. Nghĩ tới: tính lại từ đầu mỗi lần là $O(nq)$. Phải tìm cấu trúc dữ liệu cập nhật được dần. Thao tác “nối hai nhóm, hỏi số nhóm” → DSU. Thao tác “sửa một số, hỏi tổng/min đoạn” → Fenwick / segment tree. Nếu thao tác là xoá cạnh thì mẹo là đảo ngược thứ tự: xử lý từ cuối lên, xoá biến thành thêm, rồi dùng DSU.
Ca 3: “Đáp án rất lớn, in theo modulo $10^9 + 7$”
Đề nói: đếm số cách, đáp án in theo modulo. Nghĩ tới: đây là bài đếm, gần như chắc chắn là QHĐ (bài 27) hoặc công thức tổ hợp (bài 26). Nếu đối tượng là “chọn $k$ trong $n$”, “đường đi trên lưới”, “chia kẹo” thì thử tìm công thức $C(n, k)$ trước; nếu có ràng buộc phức tạp thì quay về QHĐ. Thấy phép chia dưới modulo thì nhớ nghịch đảo modulo bằng lũy thừa nhanh: $a^{-1} \equiv a^{p-2} \pmod p$.
Giờ em tự luyện phản xạ với 10 đề ngắn dưới đây. Mỗi đề, em đọc rồi tự đoán kỹ thuật trước, sau đó bấm Tiếp để mở dần từng dấu hiệu và đáp án. Nhập số đề (1 – 10) để luyện riêng một đề:
Phần 3Chiến thuật trong phòng thi
Đề thi HSG thường có 4 – 6 câu, mỗi câu chia subtask: subtask nhỏ cho vét cạn, subtask lớn mới cần thuật toán tối ưu. Điểm của em là tổng điểm subtask, nên chiến thuật quan trọng không kém thuật toán.
| Thời gian | Việc cần làm |
|---|---|
| 10 phút đầu | Đọc hết 6 câu, ghi nhanh dấu hiệu và giới hạn từng subtask. Đánh dấu câu chắc làm được. |
| 60 phút | Làm trọn các câu dễ (thường câu 1 – 3). Mỗi câu xong phải tự thử biên: $n = 1$, toàn số bằng nhau, số lớn nhất. |
| 60 phút | Với câu khó: viết vét cạn lấy subtask 1 trước, nộp ngay. Sau đó mới nghĩ lời giải tối ưu. |
| 40 phút | Đối chiếu lời giải tối ưu với vét cạn bằng test ngẫu nhiên (stress test). Còn thời gian thì vét thêm subtask câu cuối. |
| 10 phút cuối | Không sửa lớn nữa. Kiểm tra tên tệp, đọc/ghi đúng định dạng, đã bỏ dòng in gỡ lỗi chưa. |
Bảng 3. Gợi ý chia 180 phút cho đề 6 câu.
Stress test là cách nhanh nhất để bắt lỗi khi chưa có máy chấm: sinh hàng trăm test nhỏ ngẫu nhiên, chạy cả code nhanh và code vét cạn, hễ khác nhau thì in test đó ra. Một đoạn Python ngắn là đủ:
import random, subprocess
for it in range(500):
n = random.randint(1, 8)
a = [random.randint(1, 5) for _ in range(n)]
inp = f"{n}\n" + " ".join(map(str, a)) + "\n"
fast = subprocess.run(["./fast"], input=inp, capture_output=True, text=True).stdout
slow = subprocess.run(["./brute"], input=inp, capture_output=True, text=True).stdout
if fast.split() != slow.split():
print("SAI:", inp, fast, slow); break
else:
print("OK 500 test")Giá trị nhỏ (1 – 5) cố ý tạo nhiều số bằng nhau, nơi các lỗi < / <= hay ẩn nấp nhất.
Bài tậpĐề thi thử 6 câu (180 phút)
Em chuẩn bị giấy nháp, bấm đồng hồ 180 phút và làm như thi thật. Mỗi câu có gợi ý và code tham khảo nhưng đều được giấu, em chỉ mở khi đã hết giờ hoặc bí thật sự. Lời giải đầy đủ (đi từ vét cạn tới tối ưu) nằm ở Phần 4.
| Câu | Tên bài | Điểm | Mức độ |
|---|---|---|---|
| 1 | Xếp hàng chào cờ | 15 | Dễ |
| 2 | Đoạn ổn định dài nhất | 15 | Trung bình |
| 3 | Đường về tránh ô sửa | 15 | Trung bình |
| 4 | Phiếu giảm giá taxi | 20 | Khá |
| 5 | Kéo điện về làng | 15 | Khá |
| 6 | Bộ ba tăng dần | 20 | Khó |
Bảng 4. Cấu trúc đề thi thử, tổng 100 điểm. Giới hạn thời gian mỗi test: 1 giây (C++), Python được nới gấp đôi.
Hàng chào cờ có $n$ bạn, bạn thứ $i$ cao $h_i$. Mỗi lần, thầy được đổi chỗ hai bạn đứng cạnh nhau. Hỏi cần ít nhất bao nhiêu lần đổi để hàng có chiều cao không giảm từ đầu tới cuối?
Giới hạn: $1 \le n \le 2 \cdot 10^5$, $1 \le h_i \le 10^9$. Subtask 1 (50% số điểm): $n \le 1000$. Subtask 2 (50%): không có ràng buộc thêm.
5
160 150 170 150 1555📝 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 a[200005], tmp[200005];
long long countInv(int l, int r){
if(l >= r) return 0;
int m = (l + r) / 2;
long long res = countInv(l, m) + countInv(m + 1, r);
int i = l, j = m + 1, k = l;
while(i <= m && j <= r){
if(a[i] <= a[j]) tmp[k++] = a[i++]; // bằng nhau: không phải nghịch thế
else { res += m - i + 1; tmp[k++] = a[j++]; }
}
while(i <= m) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for(int t = l; t <= r; t++) a[t] = tmp[t];
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
cout << countInv(0, n - 1);
return 0;
}import sys
def count_inv(a):
if len(a) <= 1:
return a, 0
m = len(a) // 2
left, x = count_inv(a[:m])
right, y = count_inv(a[m:])
res, i, j, cnt = [], 0, 0, x + y
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i]); i += 1
else:
cnt += len(left) - i # left[i:] đều lớn hơn right[j]
res.append(right[j]); j += 1
res.extend(left[i:]); res.extend(right[j:])
return res, cnt
data = sys.stdin.buffer.read().split()
n = int(data[0])
print(count_inv(list(map(int, data[1:n + 1])))[1])Một cảm biến ghi lại $n$ số đo nhiệt độ $a_1, a_2, \ldots, a_n$. Một đoạn liên tiếp gọi là ổn định nếu chênh lệch giữa số lớn nhất và số nhỏ nhất trong đoạn không vượt quá $K$. Tìm độ dài đoạn ổn định dài nhất.
Giới hạn: $1 \le n \le 5 \cdot 10^5$, $0 \le K, a_i \le 10^9$. Subtask 1 (30%): $n \le 300$. Subtask 2 (30%): $n \le 5000$. Subtask 3 (40%): không có ràng buộc thêm.
Input: dòng đầu $n$ và $K$, dòng sau $n$ số $a_i$. Output: một số nguyên.
8 2
5 3 4 6 2 3 1 34📝 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;
vector<long long> a(n);
for(auto &x : a) cin >> x;
deque<int> mx, mn; // chỉ số; a[mx] giảm dần, a[mn] tăng dần
int l = 0, best = 0;
for(int r = 0; r < n; r++){
while(!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
mx.push_back(r);
while(!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mn.push_back(r);
while(a[mx.front()] - a[mn.front()] > K){ // cửa sổ hỏng: thu hẹp bên trái
l++;
if(mx.front() < l) mx.pop_front();
if(mn.front() < l) mn.pop_front();
}
best = max(best, r - l + 1);
}
cout << best;
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
mx, mn = deque(), deque() # chỉ số; a[mx] giảm dần, a[mn] tăng dần
l = best = 0
for r in range(n):
x = a[r]
while mx and a[mx[-1]] <= x: mx.pop()
mx.append(r)
while mn and a[mn[-1]] >= x: mn.pop()
mn.append(r)
while a[mx[0]] - a[mn[0]] > K: # cửa sổ hỏng: thu hẹp bên trái
l += 1
if mx[0] < l: mx.popleft()
if mn[0] < l: mn.popleft()
if r - l + 1 > best: best = r - l + 1
print(best)
main()Robot đứng ở ô $(0, 0)$ và muốn tới ô $(n, m)$. Mỗi bước nó chỉ đi sang phải $(x+1, y)$ hoặc lên trên $(x, y+1)$. Ô $(a, b)$ đang sửa nên robot không được đi qua. Đếm số đường đi, in theo modulo $10^9 + 7$. Có $q$ câu hỏi độc lập.
Giới hạn: $1 \le q \le 10^5$, $0 \le n, m \le 5 \cdot 10^5$, $0 \le a \le n$, $0 \le b \le m$. Subtask 1 (30%): $n, m \le 10$. Subtask 2 (30%): $q = 1$, $n, m \le 1000$. Subtask 3 (40%): không có ràng buộc thêm.
Input: dòng đầu $q$, mỗi dòng sau gồm $n, m, a, b$. Output: $q$ dòng, mỗi dòng một đáp án.
3
2 2 1 1
3 3 0 0
2 3 2 02
0
9📝 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;
const long long MOD = 1000000007;
const int N = 1000005;
long long f[N], inv[N];
long long power(long long a, long long b){
long long r = 1; a %= MOD;
while(b){ if(b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; }
return r;
}
long long C(int n, int k){
if(k < 0 || k > n) return 0;
return f[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
f[0] = 1;
for(int i = 1; i < N; i++) f[i] = f[i - 1] * i % MOD;
inv[N - 1] = power(f[N - 1], MOD - 2); // Fermat
for(int i = N - 1; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
int q;
cin >> q;
while(q--){
int n, m, a, b;
cin >> n >> m >> a >> b;
long long all = C(n + m, n);
long long bad = C(a + b, a) * C(n - a + m - b, n - a) % MOD; // đi qua ô (a, b)
cout << ((all - bad) % MOD + MOD) % MOD << "\n";
}
return 0;
}import sys
def main():
MOD = 10**9 + 7
data = sys.stdin.buffer.read().split()
q = int(data[0])
Q = [tuple(map(int, data[1 + 4 * i: 5 + 4 * i])) for i in range(q)]
N = max(n + m for n, m, a, b in Q) + 1
f = [1] * (N + 1)
for i in range(1, N + 1):
f[i] = f[i - 1] * i % MOD
inv = [1] * (N + 1)
inv[N] = pow(f[N], MOD - 2, MOD) # Fermat
for i in range(N, 0, -1):
inv[i - 1] = inv[i] * i % MOD
def C(n, k):
return f[n] * inv[k] % MOD * inv[n - k] % MOD
out = []
for n, m, a, b in Q:
bad = C(a + b, a) * C(n - a + m - b, n - a) # đi qua ô (a, b)
out.append((C(n + m, n) - bad) % MOD)
print('\n'.join(map(str, out)))
main()Thành phố có $n$ địa điểm và $m$ con đường hai chiều, đi taxi trên đường thứ $i$ tốn $w_i$ đồng. Em có một phiếu giảm giá, dùng cho tối đa một con đường: đường đó chỉ tốn $\lfloor w_i / 2 \rfloor$. Tìm chi phí nhỏ nhất để đi từ địa điểm $1$ tới địa điểm $n$, in $-1$ nếu không thể đi tới.
Giới hạn: $2 \le n \le 10^5$, $1 \le m \le 2 \cdot 10^5$, $1 \le w_i \le 10^9$. Subtask 1 (30%): $n \le 100$, $m \le 200$. Subtask 2 (70%): không có ràng buộc thêm.
4 4
1 2 10
2 4 10
1 3 3
3 4 1812📝 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;
typedef long long ll;
const ll INF = LLONG_MAX / 4;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, ll>>> g(n + 1);
for(int i = 0; i < m; i++){
int u, v; ll w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
// d[v][t]: chi phí nhỏ nhất tới v, t = 1 nếu đã dùng phiếu
vector<array<ll, 2>> d(n + 1, {INF, INF});
priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
d[1][0] = 0; pq.push({0, 1, 0});
while(!pq.empty()){
auto [du, u, t] = pq.top(); pq.pop();
if(du != d[u][t]) continue; // bản ghi cũ
for(auto [v, w] : g[u]){
if(du + w < d[v][t]){ d[v][t] = du + w; pq.push({d[v][t], v, t}); }
if(t == 0 && du + w / 2 < d[v][1]){ // dùng phiếu cho cạnh này
d[v][1] = du + w / 2; pq.push({d[v][1], v, 1});
}
}
}
ll ans = min(d[n][0], d[n][1]);
cout << (ans >= INF ? -1 : ans);
return 0;
}import sys, heapq
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
g[u].append((v, w)); g[v].append((u, w))
INF = float('inf')
d0 = [INF] * (n + 1) # chưa dùng phiếu
d1 = [INF] * (n + 1) # đã dùng phiếu
d0[1] = 0
pq = [(0, 1, 0)]
pop, push = heapq.heappop, heapq.heappush
while pq:
du, u, t = pop(pq)
if t == 0:
if du != d0[u]:
continue # bản ghi cũ
for v, w in g[u]:
nd = du + w
if nd < d0[v]:
d0[v] = nd; push(pq, (nd, v, 0))
nd = du + w // 2 # dùng phiếu cho cạnh này
if nd < d1[v]:
d1[v] = nd; push(pq, (nd, v, 1))
else:
if du != d1[u]:
continue
for v, w in g[u]:
nd = du + w
if nd < d1[v]:
d1[v] = nd; push(pq, (nd, v, 1))
ans = min(d0[n], d1[n])
print(-1 if ans == INF else ans)
main()Huyện có $n$ làng, trong đó $p$ làng đã có trạm điện. Có $m$ phương án kéo dây: dây thứ $i$ nối hai làng $u_i, v_i$ với chi phí $c_i$. Một làng có điện nếu nó nối (trực tiếp hoặc qua các làng khác) tới ít nhất một trạm. Tìm tổng chi phí nhỏ nhất để mọi làng có điện, in $-1$ nếu không thể.
Giới hạn: $1 \le p \le n \le 10^5$, $0 \le m \le 2 \cdot 10^5$, $0 \le c_i \le 10^9$. Subtask 1 (30%): $n \le 8$, $m \le 12$. Subtask 2 (30%): $p = 1$. Subtask 3 (40%): không có ràng buộc thêm.
Input: dòng đầu $n, m, p$; dòng hai gồm $p$ làng có trạm (khác nhau); $m$ dòng sau mỗi dòng $u_i, v_i, c_i$.
5 5 2
1 4
1 2 3
2 3 1
3 4 4
4 5 2
2 5 66📝 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 par[100005];
int findRoot(int x){ return par[x] == x ? x : par[x] = findRoot(par[x]); }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, p;
cin >> n >> m >> p;
vector<array<long long, 3>> E; // {chi phí, u, v}
for(int i = 0; i < p; i++){ int x; cin >> x; E.push_back({0, 0, x}); } // cạnh ảo 0 – nhà máy
for(int i = 0; i < m; i++){ long long u, v, c; cin >> u >> v >> c; E.push_back({c, u, v}); }
sort(E.begin(), E.end());
for(int i = 0; i <= n; i++) par[i] = i;
long long cost = 0; int used = 0;
for(auto &e : E){
int a = findRoot(e[1]), b = findRoot(e[2]);
if(a == b) continue; // tạo chu trình
par[a] = b; cost += e[0]; used++;
if(used == n) break; // n + 1 đỉnh cần n cạnh
}
cout << (used == n ? cost : -1);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, p = int(data[0]), int(data[1]), int(data[2])
E = [(0, 0, int(x)) for x in data[3:3 + p]] # cạnh ảo 0 – nhà máy
pos = 3 + p
for i in range(m):
u, v, c = int(data[pos]), int(data[pos + 1]), int(data[pos + 2]); pos += 3
E.append((c, u, v))
E.sort()
par = list(range(n + 1))
def find(x):
while par[x] != x:
par[x] = par[par[x]] # nén đường đi (chia đôi)
x = par[x]
return x
cost = used = 0
for c, u, v in E:
a, b = find(u), find(v)
if a == b:
continue # tạo chu trình
par[a] = b; cost += c; used += 1
if used == n:
break
print(cost if used == n else -1)
main()Cho dãy $n$ số nguyên dương $a_1, \ldots, a_n$. Đếm số bộ ba chỉ số $i < j < k$ sao cho $a_i < a_j < a_k$.
Giới hạn: $1 \le n \le 2 \cdot 10^5$, $1 \le a_i \le 10^9$. Subtask 1 (20%): $n \le 200$. Subtask 2 (30%): $n \le 5000$. Subtask 3 (50%): không có ràng buộc thêm.
5
1 3 2 4 57📝 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 n, bit[200005];
void add(int i){ for(; i <= n; i += i & -i) bit[i]++; }
int get(int i){ int s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<int> a(n), v;
for(auto &x : a) cin >> x;
v = a; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
for(auto &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin() + 1; // nén về 1..k
vector<long long> L(n), R(n);
for(int j = 0; j < n; j++){ L[j] = get(a[j] - 1); add(a[j]); } // bên trái, nhỏ hơn
fill(bit, bit + n + 1, 0);
for(int j = n - 1; j >= 0; j--){ R[j] = (n - 1 - j) - get(a[j]); add(a[j]); } // bên phải, lớn hơn
long long ans = 0;
for(int j = 0; j < n; j++) ans += L[j] * R[j];
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
rank = {x: i + 1 for i, x in enumerate(sorted(set(a)))}
a = [rank[x] for x in a] # nén về 1..k
k = len(rank)
bit = [0] * (k + 1)
L = [0] * n
for j in range(n): # bên trái, nhỏ hơn
i, s = a[j] - 1, 0
while i > 0: s += bit[i]; i -= i & -i
L[j] = s
i = a[j]
while i <= k: bit[i] += 1; i += i & -i
bit = [0] * (k + 1)
ans = 0
for j in range(n - 1, -1, -1): # bên phải, lớn hơn
i, s = a[j], 0
while i > 0: s += bit[i]; i -= i & -i
ans += L[j] * ((n - 1 - j) - s)
i = a[j]
while i <= k: bit[i] += 1; i += i & -i
print(ans)
main()Phần 4Lời giải chi tiết từng câu
Với mỗi câu, mình đi theo đúng thứ tự em nên nghĩ trong phòng thi: nhận dạng → vét cạn lấy subtask → tối ưu. Code vét cạn và code đầy đủ đều đã được đối chiếu với nhau trên hàng trăm test ngẫu nhiên.
Câu 1. Xếp hàng chào cờ (nghịch thế, bài 24)
Nhận dạng. “Đổi chỗ hai phần tử kề nhau, ít nhất bao nhiêu lần để sắp xếp” là câu hỏi kinh điển, đáp án là số cặp nghịch thế. Vì sao? Đổi chỗ hai bạn kề nhau $h_i > h_{i+1}$ chỉ làm thay đổi thứ tự của đúng cặp đó, nên số nghịch thế giảm đúng 1. Không có cách nào giảm nhiều hơn 1 mỗi lần, và hàng còn nghịch thế thì luôn có cặp kề nhau bị ngược. Đây cũng chính là số lần đổi chỗ của thuật toán nổi bọt.
Subtask 1 ($n \le 1000$): hai vòng for đếm cặp, $O(n^2) = 10^6$.
Xem code C++ / Python: câu 1 vét cạn $O(n^2)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> a(n);
for(auto &x : a) cin >> x;
long long cnt = 0;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(a[i] > a[j]) cnt++; // mỗi cặp nghịch thế cần đúng 1 lần đổi chỗ
cout << cnt;
return 0;
}n = int(input())
a = list(map(int, input().split()))
print(sum(1 for i in range(n) for j in range(i + 1, n) if a[i] > a[j]))Subtask 2 ($n = 2 \cdot 10^5$): $O(n^2)$ là $2 \cdot 10^{10}$, quá chậm. Dùng merge sort đếm nghịch thế (bài 24): khi trộn, lấy $a_j$ từ nửa phải thì cộng $m - i + 1$. Lưu ý chiều cao bằng nhau không cần đổi, nên khi $a_i = a_j$ phải lấy bên trái trước (dấu <=).
Xem code C++ / Python: câu 1 đầy đủ, merge sort $O(n \log n)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int a[200005], tmp[200005];
long long countInv(int l, int r){
if(l >= r) return 0;
int m = (l + r) / 2;
long long res = countInv(l, m) + countInv(m + 1, r);
int i = l, j = m + 1, k = l;
while(i <= m && j <= r){
if(a[i] <= a[j]) tmp[k++] = a[i++]; // bằng nhau: không phải nghịch thế
else { res += m - i + 1; tmp[k++] = a[j++]; }
}
while(i <= m) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for(int t = l; t <= r; t++) a[t] = tmp[t];
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
cout << countInv(0, n - 1);
return 0;
}import sys
def count_inv(a):
if len(a) <= 1:
return a, 0
m = len(a) // 2
left, x = count_inv(a[:m])
right, y = count_inv(a[m:])
res, i, j, cnt = [], 0, 0, x + y
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i]); i += 1
else:
cnt += len(left) - i # left[i:] đều lớn hơn right[j]
res.append(right[j]); j += 1
res.extend(left[i:]); res.extend(right[j:])
return res, cnt
data = sys.stdin.buffer.read().split()
n = int(data[0])
print(count_inv(list(map(int, data[1:n + 1])))[1])Độ phức tạp: $O(n \log n)$ thời gian, $O(n)$ bộ nhớ. Cách khác: nén giá trị rồi dùng Fenwick đếm “số đã gặp lớn hơn $h_j$”, cũng $O(n \log n)$.
Câu 2. Đoạn ổn định dài nhất (hàng đợi đơn điệu, bài 25)
Nhận dạng. “Đoạn liên tiếp dài nhất thoả điều kiện” + điều kiện có tính đơn điệu (đoạn tốt thì đoạn con cũng tốt) → hai con trỏ (bài 17). Điều kiện cần max và min của cửa sổ đang trượt → hàng đợi đơn điệu.
Subtask 1 ($n \le 300$): thử mọi đoạn, tính max − min bằng vòng lặp, $O(n^3)$. Subtask 2 ($n \le 5000$): cố định $l$, mở rộng $r$ và cập nhật min/max dần, đoạn hỏng thì dừng ngay vì kéo dài thêm vẫn hỏng: $O(n^2)$.
Xem code C++ / Python: câu 2 vét cạn $O(n^2)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long K;
cin >> n >> K;
vector<long long> a(n);
for(auto &x : a) cin >> x;
int best = 0;
for(int l = 0; l < n; l++){
long long lo = a[l], hi = a[l];
for(int r = l; r < n; r++){ // mở rộng dần, cập nhật min/max
lo = min(lo, a[r]); hi = max(hi, a[r]);
if(hi - lo > K) break; // đã hỏng thì kéo dài thêm cũng hỏng
best = max(best, r - l + 1);
}
}
cout << best;
return 0;
}n, K = map(int, input().split())
a = list(map(int, input().split()))
best = 0
for l in range(n):
lo = hi = a[l]
for r in range(l, n): # mở rộng dần, cập nhật min/max
lo = min(lo, a[r]); hi = max(hi, a[r])
if hi - lo > K: # đã hỏng thì kéo dài thêm cũng hỏng
break
best = max(best, r - l + 1)
print(best)Subtask 3. Với mỗi $r$, ta muốn $l$ nhỏ nhất để $[l, r]$ ổn định. Khi $r$ tăng, $l$ không bao giờ giảm (vì đoạn $[l, r+1]$ hỏng thì $[l-1, r+1]$ càng hỏng). Vậy chỉ cần hai con trỏ, mỗi con trỏ đi tối đa $n$ bước. Max của cửa sổ lấy từ deque mx: khi thêm $a_r$, bỏ khỏi cuối mọi chỉ số có giá trị $\le a_r$ (chúng đứng trước và không lớn hơn $a_r$ nên không bao giờ là max nữa). Tương tự mn cho min. Khi $l$ tăng vượt chỉ số ở đầu deque thì bỏ đầu.
Xem code C++ / Python: câu 2 đầy đủ, hai deque $O(n)$ (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;
vector<long long> a(n);
for(auto &x : a) cin >> x;
deque<int> mx, mn; // chỉ số; a[mx] giảm dần, a[mn] tăng dần
int l = 0, best = 0;
for(int r = 0; r < n; r++){
while(!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
mx.push_back(r);
while(!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mn.push_back(r);
while(a[mx.front()] - a[mn.front()] > K){ // cửa sổ hỏng: thu hẹp bên trái
l++;
if(mx.front() < l) mx.pop_front();
if(mn.front() < l) mn.pop_front();
}
best = max(best, r - l + 1);
}
cout << best;
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
mx, mn = deque(), deque() # chỉ số; a[mx] giảm dần, a[mn] tăng dần
l = best = 0
for r in range(n):
x = a[r]
while mx and a[mx[-1]] <= x: mx.pop()
mx.append(r)
while mn and a[mn[-1]] >= x: mn.pop()
mn.append(r)
while a[mx[0]] - a[mn[0]] > K: # cửa sổ hỏng: thu hẹp bên trái
l += 1
if mx[0] < l: mx.popleft()
if mn[0] < l: mn.popleft()
if r - l + 1 > best: best = r - l + 1
print(best)
main()Em chạy tay từng dòng dưới đây để thấy hai deque co giãn thế nào. Ô đỏ là vị trí đang giữ max (đầu mx), ô xanh lá là vị trí đang giữ min (đầu mn):
Độ phức tạp: mỗi chỉ số vào và ra mỗi deque nhiều nhất một lần, $l$ chỉ tăng, nên tổng $O(n)$.
while, không phải if: có khi phải tăng $l$ nhiều bước mới hết hỏng.Câu 3. Đường về tránh ô sửa (tổ hợp modulo, bài 26)
Nhận dạng. “Đếm số đường đi”, “modulo $10^9 + 7$”, $q$ tới $10^5$ câu hỏi → không thể QHĐ cho từng câu, phải có công thức và trả lời $O(1)$.
Subtask 1 và 2: QHĐ trên lưới như bài 19: $f[x][y] = f[x-1][y] + f[x][y-1]$, ô sửa gán $f = 0$. Mỗi câu tốn $O(nm)$, đủ cho $n, m \le 1000$ và $q = 1$.
Xem code C++ / Python: câu 3 vét cạn bằng QHĐ trên lưới (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
int q;
cin >> q;
while(q--){
int n, m, a, b;
cin >> n >> m >> a >> b;
vector<vector<long long>> f(n + 1, vector<long long>(m + 1, 0));
for(int x = 0; x <= n; x++)
for(int y = 0; y <= m; y++){
if(x == a && y == b) { f[x][y] = 0; continue; } // ô đang sửa
if(x == 0 && y == 0) { f[x][y] = 1; continue; }
if(x > 0) f[x][y] += f[x - 1][y];
if(y > 0) f[x][y] += f[x][y - 1];
f[x][y] %= MOD;
}
cout << f[n][m] << "\n";
}
return 0;
}MOD = 10**9 + 7
q = int(input())
for _ in range(q):
n, m, a, b = map(int, input().split())
f = [[0] * (m + 1) for _ in range(n + 1)]
for x in range(n + 1):
for y in range(m + 1):
if x == a and y == b: # ô đang sửa
continue
if x == 0 and y == 0:
f[x][y] = 1
else:
f[x][y] = ((f[x - 1][y] if x else 0) + (f[x][y - 1] if y else 0)) % MOD
print(f[n][m])Subtask 3. Một đường đi bất kỳ gồm đúng $n$ bước “phải” và $m$ bước “lên” xếp theo thứ tự nào đó, nên có $C(n+m, n)$ đường. Đường đi qua ô $(a, b)$ = (đường từ $(0,0)$ tới $(a,b)$) × (đường từ $(a,b)$ tới $(n,m)$) = $C(a+b, a) \cdot C(n-a+m-b, n-a)$. Đáp án là hiệu hai số này, lấy modulo (nhớ cộng thêm $p$ trước khi lấy dư vì hiệu có thể âm).
Để tính $C(n, k) = \frac{n!}{k!\,(n-k)!}$ dưới modulo, ta tiền xử lý $f_i = i! \bmod p$ và $\mathit{inv}_i = (i!)^{-1} \bmod p$. Chỉ cần một lần lũy thừa nhanh: $\mathit{inv}_N = f_N^{\,p-2}$, rồi lùi xuống $\mathit{inv}_{i-1} = \mathit{inv}_i \cdot i$.
| Câu hỏi | Tất cả $C(n+m, n)$ | Qua ô sửa | Đáp án |
|---|---|---|---|
| $n=2, m=2$, ô $(1,1)$ | $C(4,2) = 6$ | $C(2,1) \cdot C(2,1) = 4$ | 2 |
| $n=3, m=3$, ô $(0,0)$ | $C(6,3) = 20$ | $C(0,0) \cdot C(6,3) = 20$ | 0 |
| $n=2, m=3$, ô $(2,0)$ | $C(5,2) = 10$ | $C(2,2) \cdot C(3,0) = 1$ | 9 |
Bảng 5. Tính tay ví dụ của câu 3.
Xem code C++ / Python: câu 3 đầy đủ, giai thừa và nghịch đảo giai thừa (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const int N = 1000005;
long long f[N], inv[N];
long long power(long long a, long long b){
long long r = 1; a %= MOD;
while(b){ if(b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; }
return r;
}
long long C(int n, int k){
if(k < 0 || k > n) return 0;
return f[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
f[0] = 1;
for(int i = 1; i < N; i++) f[i] = f[i - 1] * i % MOD;
inv[N - 1] = power(f[N - 1], MOD - 2); // Fermat
for(int i = N - 1; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
int q;
cin >> q;
while(q--){
int n, m, a, b;
cin >> n >> m >> a >> b;
long long all = C(n + m, n);
long long bad = C(a + b, a) * C(n - a + m - b, n - a) % MOD; // đi qua ô (a, b)
cout << ((all - bad) % MOD + MOD) % MOD << "\n";
}
return 0;
}import sys
def main():
MOD = 10**9 + 7
data = sys.stdin.buffer.read().split()
q = int(data[0])
Q = [tuple(map(int, data[1 + 4 * i: 5 + 4 * i])) for i in range(q)]
N = max(n + m for n, m, a, b in Q) + 1
f = [1] * (N + 1)
for i in range(1, N + 1):
f[i] = f[i - 1] * i % MOD
inv = [1] * (N + 1)
inv[N] = pow(f[N], MOD - 2, MOD) # Fermat
for i in range(N, 0, -1):
inv[i - 1] = inv[i] * i % MOD
def C(n, k):
return f[n] * inv[k] % MOD * inv[n - k] % MOD
out = []
for n, m, a, b in Q:
bad = C(a + b, a) * C(n - a + m - b, n - a) # đi qua ô (a, b)
out.append((C(n + m, n) - bad) % MOD)
print('\n'.join(map(str, out)))
main()Độ phức tạp: $O(N + \log p)$ tiền xử lý với $N = n + m \le 10^6$, mỗi câu hỏi $O(1)$.
Câu 4. Phiếu giảm giá taxi (Dijkstra trên đồ thị trạng thái, bài 29)
Nhận dạng. Đường đi chi phí nhỏ nhất, trọng số dương, $n$ lớn → Dijkstra. Nhưng có thêm “quyền đặc biệt dùng một lần”, nên một đỉnh thôi chưa đủ mô tả tình trạng: đứng ở $v$ khi còn phiếu khác hẳn đứng ở $v$ khi hết phiếu.
Subtask 1 ($m \le 200$): thử dùng phiếu cho từng cạnh (và trường hợp không dùng), mỗi lần chạy Dijkstra một lần: $O(m \cdot m \log n)$.
Xem code C++ / Python: câu 4 vét cạn: thử phiếu cho từng cạnh (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;
int n, m;
vector<array<ll, 3>> E;
ll dijkstra(int half){ // half = chỉ số cạnh dùng phiếu (-1: không dùng)
vector<vector<pair<int, ll>>> g(n + 1);
for(int i = 0; i < m; i++){
ll w = (i == half) ? E[i][2] / 2 : E[i][2];
g[E[i][0]].push_back({(int)E[i][1], w});
g[E[i][1]].push_back({(int)E[i][0], w});
}
vector<ll> d(n + 1, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
d[1] = 0; pq.push({0, 1});
while(!pq.empty()){
auto [du, u] = pq.top(); pq.pop();
if(du != d[u]) continue;
for(auto [v, w] : g[u]) if(du + w < d[v]){ d[v] = du + w; pq.push({d[v], v}); }
}
return d[n];
}
int main(){
cin >> n >> m;
E.resize(m);
for(auto &e : E) cin >> e[0] >> e[1] >> e[2];
ll ans = dijkstra(-1);
for(int i = 0; i < m; i++) ans = min(ans, dijkstra(i)); // thử phiếu cho từng cạnh
cout << (ans >= INF ? -1 : ans);
return 0;
}import heapq
def dijkstra(n, E, half): # half = chỉ số cạnh dùng phiếu (-1: không dùng)
g = [[] for _ in range(n + 1)]
for i, (u, v, w) in enumerate(E):
c = w // 2 if i == half else w
g[u].append((v, c)); g[v].append((u, c))
d = [float('inf')] * (n + 1); d[1] = 0
pq = [(0, 1)]
while pq:
du, u = heapq.heappop(pq)
if du != d[u]:
continue
for v, w in g[u]:
if du + w < d[v]:
d[v] = du + w; heapq.heappush(pq, (d[v], v))
return d[n]
n, m = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(m)]
ans = min(dijkstra(n, E, h) for h in range(-1, m)) # thử phiếu cho từng cạnh
print(-1 if ans == float('inf') else ans)Subtask 2. Xây đồ thị trạng thái $2n$ đỉnh, $(v, t)$ với $t \in \{0, 1\}$ là đã dùng phiếu chưa. Mỗi cạnh $u - v$ trọng số $w$ sinh ra các cung:
- $(u, 0) \to (v, 0)$ giá $w$ và $(u, 1) \to (v, 1)$ giá $w$: đi bình thường;
- $(u, 0) \to (v, 1)$ giá $\lfloor w/2 \rfloor$: dùng phiếu cho cạnh này.
Không cần xây đồ thị mới, chỉ cần mảng $d[v][t]$ và sinh cung ngay lúc duyệt. Đáp án là $\min(d[n][0], d[n][1])$.
| Đường đi | Không dùng phiếu | Phiếu cho cạnh đắt nhất | Tốt nhất |
|---|---|---|---|
| 1 → 2 → 4 | 10 + 10 = 20 | 10 + 5 = 15 | 15 |
| 1 → 3 → 4 | 3 + 18 = 21 | 3 + 9 = 12 | 12 |
Bảng 6. Ví dụ câu 4: đường 1 → 3 → 4 đắt hơn khi không có phiếu, nhưng rẻ nhất khi dùng phiếu.
Xem code C++ / Python: câu 4 đầy đủ, Dijkstra trên $2n$ trạng thái (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, ll>>> g(n + 1);
for(int i = 0; i < m; i++){
int u, v; ll w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
// d[v][t]: chi phí nhỏ nhất tới v, t = 1 nếu đã dùng phiếu
vector<array<ll, 2>> d(n + 1, {INF, INF});
priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
d[1][0] = 0; pq.push({0, 1, 0});
while(!pq.empty()){
auto [du, u, t] = pq.top(); pq.pop();
if(du != d[u][t]) continue; // bản ghi cũ
for(auto [v, w] : g[u]){
if(du + w < d[v][t]){ d[v][t] = du + w; pq.push({d[v][t], v, t}); }
if(t == 0 && du + w / 2 < d[v][1]){ // dùng phiếu cho cạnh này
d[v][1] = du + w / 2; pq.push({d[v][1], v, 1});
}
}
}
ll ans = min(d[n][0], d[n][1]);
cout << (ans >= INF ? -1 : ans);
return 0;
}import sys, heapq
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
g[u].append((v, w)); g[v].append((u, w))
INF = float('inf')
d0 = [INF] * (n + 1) # chưa dùng phiếu
d1 = [INF] * (n + 1) # đã dùng phiếu
d0[1] = 0
pq = [(0, 1, 0)]
pop, push = heapq.heappop, heapq.heappush
while pq:
du, u, t = pop(pq)
if t == 0:
if du != d0[u]:
continue # bản ghi cũ
for v, w in g[u]:
nd = du + w
if nd < d0[v]:
d0[v] = nd; push(pq, (nd, v, 0))
nd = du + w // 2 # dùng phiếu cho cạnh này
if nd < d1[v]:
d1[v] = nd; push(pq, (nd, v, 1))
else:
if du != d1[u]:
continue
for v, w in g[u]:
nd = du + w
if nd < d1[v]:
d1[v] = nd; push(pq, (nd, v, 1))
ans = min(d0[n], d1[n])
print(-1 if ans == INF else ans)
main()Độ phức tạp: $O(m \log n)$ (số trạng thái và số cung chỉ gấp đôi, gấp ba). Chi phí tới $2 \cdot 10^5 \cdot 10^9$, phải long long.
Câu 5. Kéo điện về làng (DSU và Kruskal, bài 30)
Nhận dạng. “Nối mọi điểm với tổng chi phí nhỏ nhất” → cây khung nhỏ nhất. Điểm lạ là có nhiều trạm, nên đáp án không còn là một cây mà là một rừng, mỗi cây chứa ít nhất một trạm.
Subtask 1 ($m \le 12$): thử mọi tập con đường dây ($2^{12} = 4096$), dùng DSU kiểm tra mọi làng nối tới trạm. Subtask 2 ($p = 1$): Kruskal bình thường.
Xem code C++ / Python: câu 5 vét cạn: thử mọi tập đường dây (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m, p, par[20];
int findRoot(int x){ return par[x] == x ? x : par[x] = findRoot(par[x]); }
int main(){
cin >> n >> m >> p;
vector<int> P(p);
for(auto &x : P) cin >> x;
vector<array<long long, 3>> E(m);
for(auto &e : E) cin >> e[0] >> e[1] >> e[2];
long long best = -1;
for(int mask = 0; mask < (1 << m); mask++){ // thử mọi tập đường dây
for(int i = 0; i <= n; i++) par[i] = i;
for(int x : P) par[findRoot(x)] = findRoot(0);
long long cost = 0;
for(int k = 0; k < m; k++) if(mask >> k & 1){
cost += E[k][2];
par[findRoot(E[k][0])] = findRoot(E[k][1]);
}
bool ok = true;
for(int v = 1; v <= n; v++) if(findRoot(v) != findRoot(0)) ok = false;
if(ok && (best < 0 || cost < best)) best = cost;
}
cout << best;
return 0;
}n, m, p = map(int, input().split())
P = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(m)]
best = -1
for mask in range(1 << m): # thử mọi tập đường dây
par = list(range(n + 1))
def find(x):
while par[x] != x:
x = par[x]
return x
for x in P:
par[find(x)] = find(0)
cost = 0
for k in range(m):
if mask >> k & 1:
u, v, c = E[k]; cost += c
par[find(u)] = find(v)
if all(find(v) == find(0) for v in range(1, n + 1)) and (best < 0 or cost < best):
best = cost
print(best)Subtask 3: mẹo đỉnh ảo. Thêm đỉnh $0$ đại diện cho “lưới điện quốc gia”, nối tới mọi làng có trạm bằng cạnh giá $0$. Một rừng hợp lệ (mỗi cây có trạm) cộng thêm các cạnh ảo chính là một cây khung của đồ thị $n+1$ đỉnh, cùng chi phí; và ngược lại. Vậy chỉ cần Kruskal trên đồ thị mới: sắp các cạnh tăng dần, cạnh nào nối hai nhóm khác nhau thì lấy, đủ $n$ cạnh thì dừng. Em xem mô phỏng ví dụ của đề:
Xem code C++ / Python: câu 5 đầy đủ, Kruskal với đỉnh ảo (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int par[100005];
int findRoot(int x){ return par[x] == x ? x : par[x] = findRoot(par[x]); }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, p;
cin >> n >> m >> p;
vector<array<long long, 3>> E; // {chi phí, u, v}
for(int i = 0; i < p; i++){ int x; cin >> x; E.push_back({0, 0, x}); } // cạnh ảo 0 – nhà máy
for(int i = 0; i < m; i++){ long long u, v, c; cin >> u >> v >> c; E.push_back({c, u, v}); }
sort(E.begin(), E.end());
for(int i = 0; i <= n; i++) par[i] = i;
long long cost = 0; int used = 0;
for(auto &e : E){
int a = findRoot(e[1]), b = findRoot(e[2]);
if(a == b) continue; // tạo chu trình
par[a] = b; cost += e[0]; used++;
if(used == n) break; // n + 1 đỉnh cần n cạnh
}
cout << (used == n ? cost : -1);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, p = int(data[0]), int(data[1]), int(data[2])
E = [(0, 0, int(x)) for x in data[3:3 + p]] # cạnh ảo 0 – nhà máy
pos = 3 + p
for i in range(m):
u, v, c = int(data[pos]), int(data[pos + 1]), int(data[pos + 2]); pos += 3
E.append((c, u, v))
E.sort()
par = list(range(n + 1))
def find(x):
while par[x] != x:
par[x] = par[par[x]] # nén đường đi (chia đôi)
x = par[x]
return x
cost = used = 0
for c, u, v in E:
a, b = find(u), find(v)
if a == b:
continue # tạo chu trình
par[a] = b; cost += c; used += 1
if used == n:
break
print(cost if used == n else -1)
main()Độ phức tạp: $O((m + p) \log (m + p))$ cho việc sắp xếp, DSU gần như $O(1)$ mỗi thao tác.
Câu 6. Bộ ba tăng dần (Fenwick, bài 31)
Nhận dạng. Đếm bộ $i < j < k$ với điều kiện so sánh: cùng họ với đếm nghịch thế, nhưng ba chỉ số. Mẹo chuẩn: cố định phần tử giữa, khi đó hai đầu độc lập với nhau, đáp án tách thành tích $L_j \cdot R_j$.
Subtask 1 ($n \le 200$): ba vòng for, $O(n^3)$. Subtask 2 ($n \le 5000$): cố định $j$, đếm $L_j$ và $R_j$ bằng hai vòng lặp, $O(n^2)$.
Xem code C++ / Python: câu 6 vét cạn $O(n^2)$, cố định phần tử giữa (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;
long long ans = 0;
for(int j = 0; j < n; j++){ // cố định phần tử giữa
long long L = 0, R = 0;
for(int i = 0; i < j; i++) if(a[i] < a[j]) L++;
for(int k = j + 1; k < n; k++) if(a[k] > a[j]) R++;
ans += L * R;
}
cout << ans;
return 0;
}n = int(input())
a = list(map(int, input().split()))
ans = 0
for j in range(n): # cố định phần tử giữa
L = sum(1 for i in range(j) if a[i] < a[j])
R = sum(1 for k in range(j + 1, n) if a[k] > a[j])
ans += L * R
print(ans)Subtask 3. $L_j$ = số phần tử đứng trước nhỏ hơn $a_j$: quét từ trái sang, Fenwick lưu “giá trị $x$ đã xuất hiện bao nhiêu lần”, hỏi tổng tiền tố tới $a_j - 1$ rồi cộng 1 tại $a_j$. Giá trị tới $10^9$ nên phải nén về $1..k$ trước. $R_j$ làm y hệt nhưng quét từ phải sang và đếm số lớn hơn: (số đã thêm) − (tiền tố tới $a_j$). Dùng tiền tố tới $a_j - 1$ và tiền tố tới $a_j$ đúng chỗ là để loại các số bằng $a_j$, vì đề yêu cầu tăng ngặt.
Xem code C++ / Python: câu 6 đầy đủ, hai lượt quét Fenwick (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, bit[200005];
void add(int i){ for(; i <= n; i += i & -i) bit[i]++; }
int get(int i){ int s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<int> a(n), v;
for(auto &x : a) cin >> x;
v = a; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
for(auto &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin() + 1; // nén về 1..k
vector<long long> L(n), R(n);
for(int j = 0; j < n; j++){ L[j] = get(a[j] - 1); add(a[j]); } // bên trái, nhỏ hơn
fill(bit, bit + n + 1, 0);
for(int j = n - 1; j >= 0; j--){ R[j] = (n - 1 - j) - get(a[j]); add(a[j]); } // bên phải, lớn hơn
long long ans = 0;
for(int j = 0; j < n; j++) ans += L[j] * R[j];
cout << ans;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
rank = {x: i + 1 for i, x in enumerate(sorted(set(a)))}
a = [rank[x] for x in a] # nén về 1..k
k = len(rank)
bit = [0] * (k + 1)
L = [0] * n
for j in range(n): # bên trái, nhỏ hơn
i, s = a[j] - 1, 0
while i > 0: s += bit[i]; i -= i & -i
L[j] = s
i = a[j]
while i <= k: bit[i] += 1; i += i & -i
bit = [0] * (k + 1)
ans = 0
for j in range(n - 1, -1, -1): # bên phải, lớn hơn
i, s = a[j], 0
while i > 0: s += bit[i]; i -= i & -i
ans += L[j] * ((n - 1 - j) - s)
i = a[j]
while i <= k: bit[i] += 1; i += i & -i
print(ans)
main()Độ phức tạp: $O(n \log n)$. Đáp án tối đa $C(2 \cdot 10^5, 3) \approx 1{,}3 \cdot 10^{15}$, cần long long; $L_j$, $R_j$ cũng nên để long long để tích không tràn.
Phần 5Lời khuyên ôn thi và lộ trình tiếp theo
- Có thư viện code của riêng em. Lũy thừa nhanh, giai thừa nghịch đảo, Dijkstra, DSU, Fenwick, segment tree, KMP, hash: mỗi cái em phải gõ lại được trong 3 – 5 phút, không cần nhìn.
- Luyện theo dấu hiệu, không theo tên bài. Khi làm xong một bài, ghi vào sổ: “dấu hiệu nào làm mình nghĩ tới kỹ thuật này?”. Lần sau gặp dấu hiệu đó, em sẽ nhớ ra ngay.
- Luôn viết vét cạn trước cho câu khó, và tập thói quen stress test như Phần 3.
- Soi biên và kiểu dữ liệu. Hơn một nửa số bài “đúng ý tưởng mà mất điểm” là do tràn
int, quên modulo âm, hoặc nhầm<với<=. - Thi thử định kỳ. Mỗi tuần một đề 180 phút, sau đó dành thời gian chữa kỹ hơn cả thời gian làm. Đề bài 23 và đề bài này là hai đề đầu tiên của em.
Tiếp theo học gì? Series đến đây là khép lại, nhưng kỹ năng chỉ thật sự chắc khi em giải nhiều bài. Mình đã sắp 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 xếp từ dễ tới khó, bài nào cũng có lời giải C++ và Python. Em đi lần lượt từng chặng, chặng nào làm được khoảng 70% số bài thì chuyển sang chặng sau.
- Two Sets II (Trung bình)
- Món Ăn (DPRCMA) (Trung bình)
- Dãy nghịch thế (NKINV) (Khá)
- Camera (Khá)
- Bin Laden (Khá)
- Chuỗi Con Xuất Hiện K Lần (DTKSUB) (Khá)
- Chênh Lệch Lớn Nhất (Khó)
Cảm ơn em đã đồng hành cùng mình suốt 9 bài của series Thuật toán nâng cao. Chúc em giữ được nhịp luyện đều đặn và đạt kết quả thật tốt trong kỳ thi 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