Mật thư (Đề tự luyện HSG Tin 12 – Bài 4) – Sắp xếp tô-pô, QHĐ trên DAG và xếp hạng theo tầng để so sánh thứ tự từ điển
Đề bài
Mật thư. Có $N$ trạm, trạm $i$ treo thẻ ghi số $a_i$, và $M$ lối đi một chiều $u_j \to v_j$; bảo đảm không thể đi theo mũi tên mà quay về trạm cũ (đồ thị có hướng không chu trình). Một đội đi theo các lối, chép lại số trên thẻ của mọi trạm đã qua theo thứ tự – đó là mật thư. Mật thư đúng là mật thư có nhiều số nhất; nếu nhiều mật thư cùng dài nhất thì lấy mật thư nhỏ nhất theo thứ tự từ điển. Hãy in mật thư đúng.
Dữ liệu vào: dòng đầu $N, M$ ($1 \le N \le 2 \cdot 10^5$, $0 \le M \le 3 \cdot 10^5$); dòng hai là $a_1..a_N$ ($1 \le a_i \le 10^9$); $M$ dòng sau mỗi dòng $u_j\ v_j$ ($u_j \ne v_j$, có thể trùng lối).
Kết quả: dòng một là $K$ – số lượng số của mật thư đúng; dòng hai là $K$ số đó.
- Subtask 1 (20%): $N \le 12$ và $M \le 30$.
- Subtask 2 (20%): các số $a_i$ đôi một khác nhau.
- Subtask 3 (30%): $N \le 2000$ và $M \le 5000$.
- Subtask 4 (30%): không có ràng buộc gì thêm.
8 10
5 5 3 1 5 2 1 5
1 4
2 3
2 4
2 5
2 6
2 8
3 5
4 5
5 6
5 74
5 1 5 1Hành trình dài nhất qua $4$ trạm; có $6$ hành trình như vậy với các mật thư 5 1 5 1 ($1 \to 4 \to 5 \to 7$ và $2 \to 4 \to 5 \to 7$), 5 1 5 2 (hai cách), 5 3 5 1, 5 3 5 2. Nhỏ nhất là 5 1 5 1. Mật thư 1 5 1 ($4 \to 5 \to 7$) nhỏ hơn nhưng chỉ có $3$ số.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Mật thưLời mở đầu
Bài này có hai "tầng" yêu cầu lồng nhau: trước hết phải dài nhất, sau đó mới tới nhỏ nhất theo thứ tự từ điển. Phần "dài nhất" là bài kinh điển: đường đi dài nhất trên đồ thị có hướng không chu trình (DAG) – làm bằng sắp xếp tô-pô + quy hoạch động. Cái khó thật sự nằm ở phần thứ hai: so sánh hai dãy dài tới $2 \cdot 10^5$ số mà không được so từng số một.
Ta gọi $f[u]$ là số trạm nhiều nhất của một hành trình xuất phát từ $u$. Ba nhận xét làm nền cho mọi cách bên dưới:
- $f[u] = 1 + \max f[v]$ trên các lối $u \to v$ (không có lối ra thì $f[u] = 1$). Vì đồ thị không có chu trình, ta tính được $f$ theo thứ tự tô-pô ngược: trạm nào đứng sau trong thứ tự tô-pô thì tính trước.
- Độ dài mật thư đúng là $K = \max f[u]$, và mật thư đúng phải xuất phát từ một trạm có $f[u] = K$.
- Đang ở trạm $u$ mà muốn đi tiếp để hành trình vẫn dài nhất, ta bắt buộc phải sang một trạm $v$ có $f[v] = f[u] - 1$. Gom các trạm có cùng $f$ thành một tầng: mọi hành trình dài nhất đi đúng từ tầng $K$ xuống tầng $K-1$, … xuống tầng $1$, mỗi tầng một trạm. Những lối "tắt" nhảy qua tầng (ví dụ $2 \to 5$) không bao giờ nằm trên một hành trình dài nhất.
Ví dụ của đề xếp theo tầng $f$. Mật thư đúng đi qua đúng một trạm ở mỗi tầng $4 \to 3 \to 2 \to 1$; các lối nét đứt nhảy qua tầng nên bị loại.
Sau nhận xét 3, bài toán còn lại là: ở mỗi bước, trong các trạm ở tầng kề dưới, chọn trạm nào? Nếu số trên thẻ khác nhau thì cứ chọn số nhỏ nhất (tham lam). Nhưng khi hai trạm cùng số, ta phải nhìn xa hơn – có khi tới tận cuối hành trình – mới biết nên rẽ đường nào. Đó là "nút thắt" của bài.
Cách 1Thử mọi hành trình – hàm mũ · 20%
Với $N \le 12$, ta xuất phát từ từng trạm và đệ quy đi theo mọi lối, vừa đi vừa ghi mật thư vào mảng cur. Mỗi khi tới một trạm (kể cả trạm đầu), ta so cur với mật thư tốt nhất best: dài hơn thì lấy, bằng độ dài mà nhỏ hơn theo thứ tự từ điển thì cũng lấy. Trong C++, phép cur < best giữa hai vector chính là so sánh theo thứ tự từ điển; trong Python, phép < giữa hai list cũng vậy.
Vì đồ thị không có chu trình nên đệ quy luôn dừng. Nhưng số hành trình có thể tăng theo hàm mũ: chỉ cần một "cái thang" 2 trạm mỗi tầng, nối đủ 4 lối giữa hai tầng liền nhau, thì 40 tầng đã có $2^{40}$ hành trình. Các test từ subtask 2 trở đi đều có cái thang như vậy.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<long long> a;
vector<vector<int>> ke;
vector<long long> cur, best;
// Thử mọi hành trình đi tiếp từ trạm u (cur đang chứa mật thư tới u)
void duyet(int u) {
cur.push_back(a[u]);
if (cur.size() > best.size() || (cur.size() == best.size() && cur < best)) best = cur;
for (int v : ke[u]) duyet(v);
cur.pop_back();
}
int main() {
scanf("%d %d", &n, &m);
a.assign(n + 1, 0);
ke.assign(n + 1, {});
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int j = 0; j < m; j++) {
int u, v;
scanf("%d %d", &u, &v);
ke[u].push_back(v);
}
for (int s = 1; s <= n; s++) duyet(s);
printf("%d\n", (int)best.size());
for (size_t t = 0; t < best.size(); t++)
printf("%lld%c", best[t], t + 1 < best.size() ? ' ' : '\n');
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0]); m = int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
ke = [[] for _ in range(n + 1)]
for j in range(m):
u = int(data[2 + n + 2 * j]); v = int(data[3 + n + 2 * j])
ke[u].append(v)
best = []
cur = []
# Thử mọi hành trình đi tiếp từ trạm u (cur đang chứa mật thư tới u)
def duyet(u):
nonlocal best
cur.append(a[u])
if len(cur) > len(best) or (len(cur) == len(best) and cur < best):
best = cur[:]
for v in ke[u]:
duyet(v)
cur.pop()
for s in range(1, n + 1):
duyet(s)
print(len(best))
print(*best)
main()Cách 2Sắp xếp tô-pô, QHĐ $f$ rồi tham lam – $O(N + M)$ · 20%
Bước 1 – thứ tự tô-pô (thuật toán Kahn). Đếm vao[v] = số lối đi vào trạm $v$. Mọi trạm có vao = 0 (không ai đi tới được nó) cho vào danh sách topo. Lần lượt lấy từng trạm $u$ trong danh sách, "xóa" các lối ra của nó: giảm vao[v] của mọi $v$ kề; trạm nào giảm về 0 thì nối vào cuối topo. Vì không có chu trình, cuối cùng topo chứa đủ $N$ trạm và mọi lối $u \to v$ đều có $u$ đứng trước $v$.
Bước 2 – QHĐ. Duyệt topo từ cuối về đầu: khi xét $u$ thì mọi $v$ kề đã có $f[v]$, nên $f[u] = \max(1, f[v] + 1)$.
Em hãy bấm "Tiếp" để xem hai bước này chạy trên ví dụ của đề (có thể sửa số trên thẻ và danh sách lối; mỗi lối là một cặp u v).
Bước 3 – tham lam (đúng khi các số khác nhau). Bắt đầu ở trạm có $f = K$ mang số nhỏ nhất; ở mỗi bước, trong các trạm kề có $f$ đúng bằng $f[u] - 1$, đi sang trạm mang số nhỏ nhất. Khi mọi $a_i$ khác nhau, hai mật thư cùng độ dài khác nhau ngay ở số đầu tiên, nên chọn số nhỏ nhất ở từng bước là đúng.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
vector<vector<int>> ke(n + 1);
vector<int> vao(n + 1, 0);
for (int j = 0; j < m; j++) {
int u, v;
scanf("%d %d", &u, &v);
ke[u].push_back(v);
vao[v]++;
}
vector<int> topo;
for (int i = 1; i <= n; i++)
if (vao[i] == 0) topo.push_back(i);
for (int h = 0; h < (int)topo.size(); h++) {
int u = topo[h];
for (int v : ke[u])
if (--vao[v] == 0) topo.push_back(v);
}
vector<int> f(n + 1, 1);
for (int h = n - 1; h >= 0; h--) {
int u = topo[h];
for (int v : ke[u]) f[u] = max(f[u], f[v] + 1);
}
int K = *max_element(f.begin() + 1, f.end());
// Tham lam: các số a[i] đôi một khác nhau nên chỉ cần chọn số nhỏ nhất ở mỗi bước
int u = 0;
for (int i = 1; i <= n; i++)
if (f[i] == K && (u == 0 || a[i] < a[u])) u = i;
printf("%d\n", K);
for (int t = 0; t < K; t++) {
printf("%lld%c", a[u], t + 1 < K ? ' ' : '\n');
int nx = 0;
for (int v : ke[u])
if (f[v] == f[u] - 1 && (nx == 0 || a[v] < a[nx])) nx = v;
u = nx;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[1 + i])
ke = [[] for _ in range(n + 1)]
vao = [0] * (n + 1)
p = 2 + n
for j in range(m):
u = int(data[p]); v = int(data[p + 1]); p += 2
ke[u].append(v)
vao[v] += 1
topo = [i for i in range(1, n + 1) if vao[i] == 0]
h = 0
while h < len(topo):
u = topo[h]; h += 1
for v in ke[u]:
vao[v] -= 1
if vao[v] == 0:
topo.append(v)
f = [1] * (n + 1)
for h in range(n - 1, -1, -1):
u = topo[h]
for v in ke[u]:
if f[v] + 1 > f[u]:
f[u] = f[v] + 1
K = max(f[1:])
# Tham lam: các số a[i] đôi một khác nhau nên chỉ cần chọn số nhỏ nhất ở mỗi bước
u = 0
for i in range(1, n + 1):
if f[i] == K and (u == 0 or a[i] < a[u]):
u = i
res = []
for t in range(K):
res.append(a[u])
nx = 0
for v in ke[u]:
if f[v] == f[u] - 1 and (nx == 0 or a[v] < a[nx]):
nx = v
u = nx
sys.stdout.write(str(K) + "\n" + " ".join(map(str, res)) + "\n")
main()Bấm nút "Bẫy tham lam" ở mô phỏng trên: $a = (5, 3, 3, 9, 1)$, lối $1 \to 2$, $1 \to 3$, $2 \to 4$, $3 \to 5$. Hai hành trình dài nhất là $1 \to 2 \to 4$ (mật thư 5 3 9) và $1 \to 3 \to 5$ (5 3 1). Từ trạm $1$, hai trạm kề $2$ và $3$ cùng số 3; tham lam chọn trạm gặp trước là $2$ và in 5 3 9 – sai. Cái hòa này chỉ được phân định ở số thứ ba. Trong bộ test, chỗ hòa có thể chỉ được phân định sau hàng chục nghìn trạm, nên "nhìn trước thêm một, hai bước" cũng không cứu được.
Nhiều bạn bỏ qua bước tô-pô và tính $f$ bằng vòng for (u = n; u >= 1; u--). Cách đó chỉ đúng khi mọi lối có $u < v$ – đề không hề hứa điều này (thử nút "Lối đi ngược chỉ số"). Bộ test đánh số các trạm ngẫu nhiên nên lời giải kiểu này gần như mất trắng.
Cách 3So sánh trực tiếp hai mật thư theo con trỏ nxt – $O(N \cdot M)$ · 70%
Gọi $S(u)$ là mật thư tốt nhất xuất phát từ $u$ (dài đúng $f[u]$ số, nhỏ nhất theo từ điển). Ta có công thức truy hồi:
$S(u) = a_u$ nối với $\min S(v)$, lấy trên các lối $u \to v$ có $f[v] = f[u] - 1$.
Lý do: mật thư từ $u$ luôn bắt đầu bằng $a_u$; phần còn lại là một mật thư dài $f[u]-1$ xuất phát từ trạm kề $v$ (ở tầng ngay dưới), và để cả dãy nhỏ nhất thì phần đuôi phải nhỏ nhất. Ta lưu $S(u)$ một cách "gọn" bằng con trỏ nxt[u] = trạm kề được chọn: muốn đọc $S(u)$ thì đi $u \to$ nxt[u] $\to$ nxt[nxt[u]] …
So sánh $S(p)$ với $S(q)$ (cùng tầng) bằng hàm totHon(p, q): đi song song theo nxt, gặp số khác nhau đầu tiên thì kết luận; nếu hai con trỏ gặp nhau ($p = q$) thì phần còn lại giống hệt, hai mật thư bằng nhau. Tính nxt theo thứ tự tô-pô ngược (cùng lúc với $f$), cuối cùng chọn trạm xuất phát tốt nhất ở tầng $K$ cũng bằng totHon.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<long long> a;
vector<int> nxt;
// So sánh mật thư tốt nhất từ trạm p và từ trạm q (cùng độ dài): p tốt hơn hẳn q?
bool totHon(int p, int q) {
while (p != 0 && p != q) {
if (a[p] != a[q]) return a[p] < a[q];
p = nxt[p];
q = nxt[q];
}
return false;
}
int main() {
scanf("%d %d", &n, &m);
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
vector<vector<int>> ke(n + 1);
vector<int> vao(n + 1, 0);
for (int j = 0; j < m; j++) {
int u, v;
scanf("%d %d", &u, &v);
ke[u].push_back(v);
vao[v]++;
}
vector<int> topo;
for (int i = 1; i <= n; i++)
if (vao[i] == 0) topo.push_back(i);
for (int h = 0; h < (int)topo.size(); h++) {
int u = topo[h];
for (int v : ke[u])
if (--vao[v] == 0) topo.push_back(v);
}
vector<int> f(n + 1, 1);
nxt.assign(n + 1, 0);
for (int h = n - 1; h >= 0; h--) {
int u = topo[h];
for (int v : ke[u]) f[u] = max(f[u], f[v] + 1);
for (int v : ke[u])
if (f[v] == f[u] - 1 && (nxt[u] == 0 || totHon(v, nxt[u]))) nxt[u] = v;
}
int K = *max_element(f.begin() + 1, f.end());
int u = 0;
for (int i = 1; i <= n; i++)
if (f[i] == K && (u == 0 || totHon(i, u))) u = i;
printf("%d\n", K);
for (int t = 0; t < K; t++) {
printf("%lld%c", a[u], t + 1 < K ? ' ' : '\n');
u = nxt[u];
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[1 + i])
ke = [[] for _ in range(n + 1)]
vao = [0] * (n + 1)
p = 2 + n
for j in range(m):
u = int(data[p]); v = int(data[p + 1]); p += 2
ke[u].append(v)
vao[v] += 1
nxt = [0] * (n + 1)
# So sánh mật thư tốt nhất từ trạm p và từ trạm q (cùng độ dài): p tốt hơn hẳn q?
def tot_hon(p, q):
while p != 0 and p != q:
if a[p] != a[q]:
return a[p] < a[q]
p = nxt[p]
q = nxt[q]
return False
topo = [i for i in range(1, n + 1) if vao[i] == 0]
h = 0
while h < len(topo):
u = topo[h]; h += 1
for v in ke[u]:
vao[v] -= 1
if vao[v] == 0:
topo.append(v)
f = [1] * (n + 1)
for h in range(n - 1, -1, -1):
u = topo[h]
for v in ke[u]:
if f[v] + 1 > f[u]:
f[u] = f[v] + 1
for v in ke[u]:
if f[v] == f[u] - 1 and (nxt[u] == 0 or tot_hon(v, nxt[u])):
nxt[u] = v
K = max(f[1:])
u = 0
for i in range(1, n + 1):
if f[i] == K and (u == 0 or tot_hon(i, u)):
u = i
res = []
for t in range(K):
res.append(a[u])
u = nxt[u]
sys.stdout.write(str(K) + "\n" + " ".join(map(str, res)) + "\n")
main()Mỗi lối gọi totHon một lần, mỗi lần đi tối đa $K$ bước. Khi các số đôi một khác nhau (subtask 2), mỗi lần so sánh dừng ngay ở bước đầu nên cách này vẫn nhanh – vì vậy nó được 70% (subtask 1, 2, 3). Nhưng hãy hình dung hai chuỗi "song sinh" $X_1 \to X_2 \to \dots \to X_T$ và $Y_1 \to \dots \to Y_T$ mang cùng dãy số, chỉ khác ở trạm cuối, cộng thêm các lối chéo $X_i \to Y_{i+1}$. Ở mỗi $X_i$ ta phải so $S(X_{i+1})$ với $S(Y_{i+1})$ – hai con trỏ không bao giờ gặp nhau và đi tới tận cuối – tốn $T - i$ bước. Tổng cộng khoảng $T^2/2$: với $T = 40\,000$ là $8 \cdot 10^8$ bước nhảy con trỏ ngẫu nhiên trong bộ nhớ, chạy cỡ 8 giây trở lên.
Cách 4Xếp hạng mật thư theo từng tầng – $O(N \log N + M)$ · 100%
Ý tưởng then chốt: đừng so sánh hai dãy dài – hãy so sánh "thứ hạng" của chúng. Ta xử lý các tầng từ dưới lên: tầng $1$, tầng $2$, …, tầng $K$. Sau khi xử lý xong tầng $k$, mỗi trạm $u$ ở tầng $k$ có một số nguyên hang[u] sao cho:
nếu $S(u) < S(w)$ (nhỏ hơn hẳn) thì hang[u] < hang[w], với mọi $u, w$ cùng tầng $k$.
Khi sang tầng $k$, tầng $k-1$ đã có hạng. Với mỗi trạm $u$ ở tầng $k$:
nxt[u]= trạm kề $v$ ở tầng $k-1$ cóhang[v]nhỏ nhất – đó chính là trạm có $S(v)$ nhỏ nhất.- $S(u) = a_u$ nối $S(\text{nxt}[u])$, nên so sánh $S(u)$ với $S(w)$ tương đương so sánh cặp $(a_u, \text{hang}[\text{nxt}[u]])$ với cặp $(a_w, \text{hang}[\text{nxt}[w]])$: số đầu khác nhau thì quyết định ngay; số đầu bằng nhau thì phần đuôi quyết định, mà phần đuôi đã được "nén" thành hạng.
- Gộp cặp thành một số
khoa[u] = a[u]·(N+1) + hang[nxt[u]](vì hạng $< N + 1$), sắp xếp tầng $k$ theokhoa; vị trí sau khi sắp chính làhangmới.
Không sao. Nếu $S(u) = S(w)$ mà hang[u] < hang[w] thì ở tầng trên ta có thể chọn $u$ thay vì $w$ – nhưng hai lựa chọn cho cùng một dãy số, nên mật thư in ra không đổi. Điều duy nhất ta cần là thứ tự "nhỏ hơn hẳn" luôn được giữ, và điều đó đúng theo quy nạp: tầng $1$ chỉ so $a_u$; ở tầng $k$, nếu $S(u) < S(w)$ thì hoặc $a_u < a_w$, hoặc $a_u = a_w$ và đuôi của $u$ nhỏ hơn hẳn – khi đó (giả thiết quy nạp) hạng đuôi nhỏ hơn hẳn, nên khoa[u] < khoa[w].
Đáp án: trạm có hạng $0$ ở tầng $K$ là điểm xuất phát; đi theo nxt và in $K$ số. Mỗi trạm được sắp xếp đúng một lần trong tầng của nó, mỗi lối được xét đúng một lần, nên tổng chi phí là $O(N \log N + M)$.
Mô phỏng dưới đây chạy phần xếp hạng trên ví dụ của đề (cột "khóa" ghi dạng cặp cho dễ đọc):
Code hoàn chỉnh (giữ đúng 4 bước: tô-pô, $f$, xếp hạng theo tầng, in mật thư):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
vector<vector<int>> ke(n + 1);
vector<int> vao(n + 1, 0);
for (int j = 0; j < m; j++) {
int u, v;
scanf("%d %d", &u, &v);
ke[u].push_back(v);
vao[v]++;
}
// 1) Thứ tự tô-pô (thuật toán Kahn)
vector<int> topo;
for (int i = 1; i <= n; i++)
if (vao[i] == 0) topo.push_back(i);
for (int h = 0; h < (int)topo.size(); h++) {
int u = topo[h];
for (int v : ke[u])
if (--vao[v] == 0) topo.push_back(v);
}
// 2) f[u] = số trạm nhiều nhất của hành trình xuất phát từ u
vector<int> f(n + 1, 1);
for (int h = n - 1; h >= 0; h--) {
int u = topo[h];
for (int v : ke[u]) f[u] = max(f[u], f[v] + 1);
}
int K = *max_element(f.begin() + 1, f.end());
vector<vector<int>> tang(K + 1);
for (int i = 1; i <= n; i++) tang[f[i]].push_back(i);
// 3) Xếp hạng mật thư tốt nhất của từng trạm, lần lượt tầng 1, 2, ..., K
vector<int> hang(n + 1, 0), nxt(n + 1, 0);
vector<long long> khoa(n + 1, 0);
for (int k = 1; k <= K; k++) {
for (int u : tang[k]) {
for (int v : ke[u])
if (f[v] == k - 1 && (nxt[u] == 0 || hang[v] < hang[nxt[u]])) nxt[u] = v;
khoa[u] = a[u] * (n + 1) + (nxt[u] ? hang[nxt[u]] : 0);
}
sort(tang[k].begin(), tang[k].end(), [&](int x, int y) { return khoa[x] < khoa[y]; });
for (int t = 0; t < (int)tang[k].size(); t++) hang[tang[k][t]] = t;
}
// 4) In mật thư: bắt đầu từ trạm hạng 0 của tầng K, đi theo nxt
printf("%d\n", K);
int u = tang[K][0];
for (int t = 0; t < K; t++) {
printf("%lld%c", a[u], t + 1 < K ? ' ' : '\n');
u = nxt[u];
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[1 + i])
ke = [[] for _ in range(n + 1)]
vao = [0] * (n + 1)
p = 2 + n
for j in range(m):
u = int(data[p]); v = int(data[p + 1]); p += 2
ke[u].append(v)
vao[v] += 1
# 1) Thứ tự tô-pô (thuật toán Kahn)
topo = [i for i in range(1, n + 1) if vao[i] == 0]
h = 0
while h < len(topo):
u = topo[h]; h += 1
for v in ke[u]:
vao[v] -= 1
if vao[v] == 0:
topo.append(v)
# 2) f[u] = số trạm nhiều nhất của hành trình xuất phát từ u
f = [1] * (n + 1)
for h in range(n - 1, -1, -1):
u = topo[h]
best = 1
for v in ke[u]:
if f[v] >= best:
best = f[v] + 1
f[u] = best
K = max(f[1:])
tang = [[] for _ in range(K + 1)]
for i in range(1, n + 1):
tang[f[i]].append(i)
# 3) Xếp hạng mật thư tốt nhất của từng trạm, lần lượt tầng 1, 2, ..., K
hang = [0] * (n + 1)
nxt = [0] * (n + 1)
khoa = [0] * (n + 1)
for k in range(1, K + 1):
T = tang[k]
for u in T:
b = 0
for v in ke[u]:
if f[v] == k - 1 and (b == 0 or hang[v] < hang[b]):
b = v
nxt[u] = b
khoa[u] = a[u] * (n + 1) + (hang[b] if b else 0)
T.sort(key=khoa.__getitem__)
for t in range(len(T)):
hang[T[t]] = t
# 4) In mật thư: bắt đầu từ trạm hạng 0 của tầng K, đi theo nxt
u = tang[K][0]
res = []
for t in range(K):
res.append(a[u])
u = nxt[u]
sys.stdout.write(str(K) + "\n" + " ".join(map(str, res)) + "\n")
main()(1) khoa có thể tới $10^9 \cdot (2 \cdot 10^5 + 1) \approx 2 \cdot 10^{14}$, phải dùng long long và tính phép nhân trên long long – lưu a bằng int rồi nhân là tràn. (2) Khi chọn nxt[u] phải giữ điều kiện f[v] == k - 1: hạng của các trạm ở tầng khác không so sánh được với nhau, và đi theo lối "tắt" thì mật thư bị ngắn đi.
Em có thể chạy tay từng dòng code C++ ở trên (tab Python chạy chính code Python phía trên):
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – thử mọi hành trình | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – tô-pô + tham lam số nhỏ nhất | WA | Đúng | WA | WA | 20 |
| Cách 3 – so sánh trực tiếp theo nxt | Đúng | Đúng | Đúng | TLE | 70 |
| Cách 4 – xếp hạng theo tầng | Đúng | Đúng | Đúng | Đúng | 100 |
| Chỉ nhìn trước 2 trạm khi hòa | Đúng | Đúng | WA | WA | 40 |
Khóa a·(N+1) tính bằng int | Đúng | WA | 5/8 | 5/8 | 57.5 |
| Bỏ tô-pô, tưởng lối đi từ chỉ số nhỏ sang lớn | 1/8 | WA | WA | WA | 2.5 |
| Quên điều kiện f[v] = f[u] − 1 khi chọn nxt | 1/8 | WA | WA | WA | 2.5 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: 30 test (8 + 6 + 8 + 8), giới hạn 1 giây. Cách 4 chạy tối đa khoảng 0,4 giây; Cách 3 ở subtask 4 cần từ khoảng 8 giây trở lên mỗi test vì hai chuỗi "song sinh" dài 35–55 nghìn trạm; Cách 1 chết ở "cái thang" $2^{40}$ hành trình. Riêng ví dụ của đề được chọn để Cách 2 và mấy lời giải sai vẫn in đúng – nên qua ví dụ chưa có nghĩa là đúng nhé!
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- 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