Tủ sách (Đề tự luyện HSG Tin 12 – Bài 5)
Đề bài
Tủ sách. Có $N$ ấp nối bởi $N - 1$ con lộ tạo thành một cây; ấp $i$ có $c_i$ học trò. Mỗi ấp đặt nhiều nhất một tủ sách; tủ đặt ở ấp $u$ phục vụ ấp $u$ và mọi ấp kề với $u$. Một ấp được phục vụ (nếu có ít nhất một tủ phục vụ nó) thì toàn bộ $c_i$ học trò được phục vụ. Với mỗi $K = 1, 2, \dots, N$: đặt đúng $K$ tủ ở $K$ ấp khác nhau, tổng số học trò được phục vụ lớn nhất là bao nhiêu?
Dữ liệu vào: dòng đầu $N$ ($1 \le N \le 3000$); dòng hai $c_1, \dots, c_N$ ($1 \le c_i \le 10^9$); $N - 1$ dòng $u, v$ là các con lộ.
Kết quả: một dòng $N$ số, số thứ $K$ là đáp án khi đặt đúng $K$ tủ.
- Subtask 1 (10%): $N \le 15$.
- Subtask 2 (20%): con lộ thứ $i$ nối ấp $i$ với ấp $i + 1$.
- Subtask 3 (30%): $N \le 300$.
- Subtask 4 (40%): không có ràng buộc gì thêm.
9
3 2 5 2 8 8 8 7 4
3 1
1 9
4 7
6 5
1 2
9 6
3 8
3 420 37 45 47 47 47 47 47 47Tổng cộng $47$ học trò. $K = 1$: tủ ở ấp $6$ phục vụ ấp $6, 5, 9$ ($20$ học trò). $K = 2$: thêm tủ ở ấp $3$ phục vụ ấp $3, 1, 8, 4$ ($+17$). $K = 3$: tủ ở ấp $6, 3, 7$, chỉ ấp $2$ chưa được phục vụ ($45$). Từ $K = 4$ phục vụ được hết (ví dụ tủ ở ấp $6, 3, 7, 1$).
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 Tủ sáchLời mở đầu
Đây là bài phân loại cuối đề. Nhìn ví dụ, rất dễ nghĩ tới tham lam: mỗi lần đặt thêm một tủ ở ấp phục vụ thêm được nhiều học trò nhất. Với ví dụ của đề, tham lam cho đúng $20, 37, 45, 47, \dots$ — nhưng đó chỉ là may mắn. Xét $5$ ấp nằm trên một con lộ thẳng với số học trò lần lượt $1, 6, 5, 3, 3$:
Phương án tốt nhất với $K = 1$ (tủ ở C) không nằm trong phương án tốt nhất với $K = 2$ (tủ ở B và D). Vì thế không thể "thêm dần từng tủ".
Vậy phải quy hoạch động. Treo cây ở ấp $1$. Khó khăn là một ấp $u$ có thể được phục vụ theo ba kiểu: tủ đặt ngay ở $u$, tủ đặt ở một con của $u$, hoặc tủ đặt ở cha của $u$. Kiểu thứ ba chưa biết được khi đang xét cây con của $u$ — nên ta giữ lại thông tin "u chưa được phục vụ" để cha quyết định sau. Với mỗi ấp $u$ và mỗi số tủ $j$ đặt trong cây con gốc $u$, ta lưu ba giá trị:
- $A_0[u][j]$: $u$ có tủ;
- $A_1[u][j]$: $u$ không có tủ nhưng đã được một con phục vụ (đã cộng $c_u$);
- $A_2[u][j]$: $u$ không có tủ và chưa được phục vụ (chưa cộng $c_u$; nếu sau này cha của $u$ có tủ thì cộng thêm).
Mỗi giá trị là số học trò được phục vụ nhiều nhất trong cây con của $u$; trạng thái không thể xảy ra lưu là $-1$. Đáp án với $K$ tủ là $\max(A_0[1][K], A_1[1][K], A_2[1][K])$ (ở gốc, trạng thái 2 nghĩa là gốc không được phục vụ — không có cha nào cứu nữa).
Cách 1Thử mọi tập ấp đặt tủ – O(2^N · N) · 10%
Với $N \le 15$ chỉ có $2^{15} = 32\,768$ tập ấp. Với mỗi tập, OR các "mặt nạ phục vụ" nb[i] (bit của ấp $i$ và các ấp kề) để biết những ấp được phục vụ, cộng số học trò, rồi cập nhật kết quả cho $K$ = số phần tử của tập.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
scanf("%d", &n);
vector<ll> c(n);
for (auto &x : c) scanf("%lld", &x);
vector<int> nb(n); // nb[i]: tập các ấp mà tủ ở ấp i phục vụ
for (int i = 0; i < n; i++) nb[i] = 1 << i;
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--; v--;
nb[u] |= 1 << v; nb[v] |= 1 << u;
}
vector<ll> best(n + 1, 0);
for (int mask = 1; mask < (1 << n); mask++) { // thử mọi tập ấp đặt tủ
int cov = 0;
for (int i = 0; i < n; i++) if (mask >> i & 1) cov |= nb[i];
ll s = 0;
for (int i = 0; i < n; i++) if (cov >> i & 1) s += c[i];
int k = __builtin_popcount(mask);
best[k] = max(best[k], s);
}
for (int k = 1; k <= n; k++) printf("%lld%c", best[k], k < n ? ' ' : '\n');
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [int(x) for x in data[1:1 + n]]
nb = [1 << i for i in range(n)] # nb[i]: tập các ấp mà tủ ở ấp i phục vụ
p = 1 + n
for _ in range(n - 1):
u = int(data[p]) - 1; v = int(data[p + 1]) - 1; p += 2
nb[u] |= 1 << v; nb[v] |= 1 << u
best = [0] * (n + 1)
for mask in range(1, 1 << n): # thử mọi tập ấp đặt tủ
cov = 0
k = 0
for i in range(n):
if mask >> i & 1:
cov |= nb[i]
k += 1
s = 0
for i in range(n):
if cov >> i & 1:
s += c[i]
if s > best[k]:
best[k] = s
print(" ".join(map(str, best[1:])))
main()Cách 2Các ấp trên một con lộ thẳng – O(N²) · 20%
Khi các ấp xếp thành dãy $1 - 2 - \dots - N$, ta đi từ trái sang phải. Trạng thái sau khi xét ấp $i$ với $k$ tủ đã đặt: ấp $i$ có tủ (0), không có tủ nhưng được ấp $i - 1$ phục vụ (1), hoặc chưa được phục vụ (2, chưa cộng $c_i$). Sang ấp $i + 1$:
- đặt tủ ở $i + 1$: sang trạng thái 0, cộng $c_{i+1}$, và nếu ấp $i$ đang ở trạng thái 2 thì cộng thêm $c_i$ (ấp $i$ được cứu);
- không đặt tủ: nếu ấp $i$ có tủ thì ấp $i + 1$ được phục vụ (trạng thái 1, cộng $c_{i+1}$), ngược lại sang trạng thái 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
scanf("%d", &n);
vector<ll> c(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
// subtask 2: con lộ thứ i nối ấp i và ấp i + 1 -> các ấp nằm trên một đường thẳng
// f[k][s] sau khi xét ấp i, đã đặt k tủ: s = 0 ấp i có tủ; s = 1 ấp i không có tủ nhưng được ấp i - 1 phục vụ;
// s = 2 ấp i không có tủ và chưa được phục vụ (chưa tính c[i])
const ll NEG = -1;
vector<array<ll, 3>> f(n + 1, {NEG, NEG, NEG}), g(n + 1);
f[1][0] = c[1]; f[0][2] = 0;
for (int i = 2; i <= n; i++) {
for (int k = 0; k <= n; k++) g[k] = {NEG, NEG, NEG};
for (int k = 0; k < i; k++) {
for (int s = 0; s < 3; s++) {
ll x = f[k][s];
if (x < 0) continue;
// đặt tủ ở ấp i
ll y = x + c[i] + (s == 2 ? c[i - 1] : 0);
g[k + 1][0] = max(g[k + 1][0], y);
// không đặt tủ ở ấp i
if (s == 0) g[k][1] = max(g[k][1], x + c[i]);
else g[k][2] = max(g[k][2], x);
}
}
swap(f, g);
}
for (int k = 1; k <= n; k++) printf("%lld%c", max({f[k][0], f[k][1], f[k][2]}), k < n ? ' ' : '\n');
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0] + [int(x) for x in data[1:1 + n]]
# subtask 2: các ấp nằm trên một đường thẳng 1 - 2 - ... - n
# f0/f1/f2[k]: đã xét tới ấp i, đặt k tủ; 0: ấp i có tủ; 1: ấp i không có tủ, được ấp i - 1 phục vụ;
# 2: ấp i không có tủ, chưa được phục vụ (chưa tính c[i])
NEG = -1
f0 = [NEG] * (n + 1); f1 = [NEG] * (n + 1); f2 = [NEG] * (n + 1)
f0[1] = c[1]; f2[0] = 0
for i in range(2, n + 1):
g0 = [NEG] * (n + 1); g1 = [NEG] * (n + 1); g2 = [NEG] * (n + 1)
ci, cp = c[i], c[i - 1]
for k in range(i):
x0, x1, x2 = f0[k], f1[k], f2[k]
# đặt tủ ở ấp i
y = max(x0 + ci if x0 >= 0 else NEG, x1 + ci if x1 >= 0 else NEG, x2 + ci + cp if x2 >= 0 else NEG)
if y > g0[k + 1]:
g0[k + 1] = y
# không đặt tủ ở ấp i
if x0 >= 0 and x0 + ci > g1[k]:
g1[k] = x0 + ci
y = max(x1, x2)
if y > g2[k]:
g2[k] = y
f0, f1, f2 = g0, g1, g2
print(" ".join(str(max(f0[k], f1[k], f2[k])) for k in range(1, n + 1)))
main()Cách 3QHĐ trên cây, gộp cây con "thẳng tay" – O(N³) · 40%
Bây giờ là cây tổng quát. Khởi tạo cho riêng ấp $u$ (chưa tính các con): $A_0[u][1] = c_u$, $A_2[u][0] = 0$, còn lại $-1$. Sau đó lần lượt gộp từng con $v$ vào $u$. Nếu trong phần đã gộp của $u$ có $i$ tủ và cây con $v$ có $t$ tủ thì tổng là $i + t$ tủ. Trước hết tính từ ba mảng của $v$:
- $g_0[t] = \max(C_0[t], C_1[t], C_2[t] + c_v)$ — dùng khi $u$ có tủ: $v$ chắc chắn được phục vụ, nếu $v$ đang "chưa được phục vụ" thì giờ cộng $c_v$;
- $g_1[t] = \max(C_1[t], C_2[t])$ — dùng khi $u$ không có tủ và $v$ cũng không có tủ: $v$ ở trạng thái 2 thì mãi mãi không được phục vụ;
- $C_0[t]$ — $v$ có tủ: nếu $u$ đang "chưa được phục vụ" thì $u$ chuyển sang trạng thái 1 và cộng $c_u$.
Rồi (ký hiệu $X \oplus Y$ là "tích chập max–cộng": $(X \oplus Y)[i + t] = \max (X[i] + Y[t])$):
$$A_0' = A_0 \oplus g_0,\qquad A_1' = \max\big(A_1 \oplus \max(C_0, g_1),\ (A_2 + c_u) \oplus C_0\big),\qquad A_2' = A_2 \oplus g_1.$$Cách viết dễ nhất là cho mọi mảng dài $N + 1$ và cho $i$, $t$ chạy từ $0$ tới $N$. Mỗi lần gộp tốn $O(N^2)$, có $N - 1$ lần gộp nên tổng $O(N^3)$: ổn với $N \le 300$ nhưng quá chậm với $N = 3000$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<ll> c;
vector<vector<int>> adj;
// A[u][s][j]: cây con gốc u, đặt đúng j tủ; s = 0: u có tủ; s = 1: u không có tủ, được con phục vụ;
// s = 2: u không có tủ, chưa được phục vụ. Giá trị -1 = không thể.
vector<array<vector<ll>, 3>> A;
void dfs(int u, int p) {
for (int s = 0; s < 3; s++) A[u][s].assign(n + 1, -1);
A[u][0][1] = c[u]; A[u][2][0] = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
vector<ll> n0(n + 1, -1), n1(n + 1, -1), n2(n + 1, -1);
for (int i = 0; i <= n; i++) // ghép thẳng tay: thử mọi i, mọi t
for (int t = 0; i + t <= n; t++) {
ll c0 = A[v][0][t], c1 = A[v][1][t], c2 = A[v][2][t];
ll g0 = max({c0, c1, c2 >= 0 ? c2 + c[v] : -1}), g1 = max(c1, c2);
if (A[u][0][i] >= 0 && g0 >= 0) n0[i + t] = max(n0[i + t], A[u][0][i] + g0);
if (A[u][1][i] >= 0 && max(c0, g1) >= 0) n1[i + t] = max(n1[i + t], A[u][1][i] + max(c0, g1));
if (A[u][2][i] >= 0 && c0 >= 0) n1[i + t] = max(n1[i + t], A[u][2][i] + c[u] + c0);
if (A[u][2][i] >= 0 && g1 >= 0) n2[i + t] = max(n2[i + t], A[u][2][i] + g1);
}
A[u][0] = n0; A[u][1] = n1; A[u][2] = n2;
}
}
int main() {
scanf("%d", &n);
c.assign(n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
adj.assign(n + 1, {});
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v); adj[v].push_back(u);
}
A.resize(n + 1);
dfs(1, 0);
for (int k = 1; k <= n; k++) printf("%lld%c", max({A[1][0][k], A[1][1][k], A[1][2][k]}), k < n ? ' ' : '\n');
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0] + [int(x) for x in data[1:1 + n]]
adj = [[] for _ in range(n + 1)]
p = 1 + n
for _ in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
# thứ tự DFS không đệ quy; xử lý ngược để con xong trước cha
par = [0] * (n + 1); par[1] = -1
order = []; st = [1]
while st:
u = st.pop(); order.append(u)
for v in adj[u]:
if v != par[u]:
par[v] = u; st.append(v)
# A[u] = [mảng s=0, s=1, s=2], mỗi mảng dài n + 1, -1 = không thể
A = [None] * (n + 1)
for u in reversed(order):
a0 = [-1] * (n + 1); a1 = [-1] * (n + 1); a2 = [-1] * (n + 1)
a0[1] = c[u]; a2[0] = 0
for v in adj[u]:
if v == par[u]:
continue
C0, C1, C2 = A[v]
n0 = [-1] * (n + 1); n1 = [-1] * (n + 1); n2 = [-1] * (n + 1)
for i in range(n + 1): # ghép thẳng tay: thử mọi i, mọi t
for t in range(n + 1 - i):
c0, c1, c2 = C0[t], C1[t], C2[t]
g0 = max(c0, c1, c2 + c[v] if c2 >= 0 else -1)
g1 = max(c1, c2)
if a0[i] >= 0 and g0 >= 0:
n0[i + t] = max(n0[i + t], a0[i] + g0)
if a1[i] >= 0 and max(c0, g1) >= 0:
n1[i + t] = max(n1[i + t], a1[i] + max(c0, g1))
if a2[i] >= 0 and c0 >= 0:
n1[i + t] = max(n1[i + t], a2[i] + c[u] + c0)
if a2[i] >= 0 and g1 >= 0:
n2[i + t] = max(n2[i + t], a2[i] + g1)
a0, a1, a2 = n0, n1, n2
A[u] = (a0, a1, a2)
r = A[1]
print(" ".join(str(max(r[0][k], r[1][k], r[2][k])) for k in range(1, n + 1)))
main()Cách 4Gộp theo kích thước cây con – O(N²) · 100%
Chỉ cần sửa một chi tiết của Cách 3: phần đã gộp của $u$ có $s_u$ ấp thì số tủ trong đó chỉ từ $0$ tới $s_u$; cây con $v$ có $s_v$ ấp thì số tủ chỉ từ $0$ tới $s_v$. Vậy mảng của $u$ chỉ cần dài $s_u + 1$, của $v$ dài $s_v + 1$, và tích chập chỉ tốn $(s_u + 1)(s_v + 1)$ phép tính. Sau khi gộp, mảng mới dài $s_u + s_v + 1$.
Hãy đếm $s_u \cdot s_v$ theo cách khác: đó là số cặp ấp $(x, y)$ với $x$ nằm trong phần đã gộp của $u$, $y$ nằm trong cây con $v$. Một cặp ấp $(x, y)$ bất kỳ chỉ được đếm đúng một lần trong cả quá trình — ở đúng lần gộp mà $x$ và $y$ lần đầu "gặp nhau", tại tổ tiên chung gần nhất của chúng. Vì vậy tổng mọi $s_u \cdot s_v$ không vượt quá số cặp ấp, tức $\frac{N(N-1)}{2}$. Thêm phần "+1" thì tổng vẫn là $O(N^2)$: với $N = 3000$ chỉ cỡ $4 \cdot 4{,}5 \cdot 10^6$ phép tính!
Nhiều bạn chỉ chặn vòng ngoài theo $s_u$ còn vòng trong vẫn chạy tới $N$. Khi đó cây hình sao (một ấp nối với $2999$ ấp khác) tốn $\sum s_u \cdot N \approx N^3 / 2$ phép tính — quá giờ. Bộ test subtask 4 có 8/10 test chứa một ấp nối trực tiếp với hàng nghìn ấp khác (hình sao, hai tâm, hoặc một "tâm" lớn trộn với chổi, sâu bướm, nhị phân, nhện...) để bắt lỗi này.
Mô phỏng sau chạy QHĐ trên cây của ví dụ: lần lượt xử lý từng ấp (con trước, cha sau), mỗi bước cho thấy ba mảng của ấp vừa xử lý xong và số phép tính đã dùng so với cách gộp thẳng tay.
Code chuẩn: duyệt BFS từ gốc rồi xử lý ngược thứ tự BFS (con luôn xong trước cha, không cần đệ quy). Bản Python dùng $-10^{18}$ cho "không thể" và tính tích chập bằng cách duyệt mảng ngắn hơn, xử lý mảng dài hơn cả đoạn bằng list comprehension (cùng số phép tính, chỉ nhanh hơn trong Python).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
// out[i + t] = max(out[i + t], A[i] + B[t]); giá trị âm nghĩa là "không thể"
void conv(const vl &A, const vl &B, vl &out) {
for (size_t i = 0; i < A.size(); i++) {
if (A[i] < 0) continue;
for (size_t t = 0; t < B.size(); t++)
if (B[t] >= 0 && A[i] + B[t] > out[i + t]) out[i + t] = A[i] + B[t];
}
}
int main() {
int n;
scanf("%d", &n);
vector<ll> c(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v); adj[v].push_back(u);
}
// thứ tự BFS từ gốc 1, xử lý ngược lại để con luôn xong trước cha
vector<int> order = {1}, par(n + 1, 0);
par[1] = -1;
for (size_t k = 0; k < order.size(); k++)
for (int v : adj[order[k]]) if (v != par[order[k]]) { par[v] = order[k]; order.push_back(v); }
// A0: u có tủ sách; A1: u không có tủ, được một con phục vụ; A2: u không có tủ, chưa được phục vụ
// Ak[j] = số học trò được phục vụ nhiều nhất trong cây con của u khi đặt đúng j tủ
vector<vl> A0(n + 1), A1(n + 1), A2(n + 1);
for (int k = n - 1; k >= 0; k--) {
int u = order[k];
vl a0 = {-1, c[u]}, a1 = {-1, -1}, a2 = {0, -1};
for (int v : adj[u]) {
if (v == par[u]) continue;
vl &C0 = A0[v], &C1 = A1[v], &C2 = A2[v];
size_t m = C0.size();
vl g0(m), g1(m), h(m);
for (size_t t = 0; t < m; t++) {
g1[t] = max(C1[t], C2[t]); // u không có tủ: v không được u phục vụ
g0[t] = max({C0[t], C1[t], C2[t] >= 0 ? C2[t] + c[v] : -1}); // u có tủ: v chắc chắn được phục vụ
h[t] = max(C0[t], g1[t]);
}
size_t L = a0.size() + m - 1;
vl n0(L, -1), n1(L, -1), n2(L, -1);
conv(a0, g0, n0);
conv(a1, h, n1); // u đã được phục vụ từ trước
vl a2c(a2.size());
for (size_t i = 0; i < a2.size(); i++) a2c[i] = a2[i] >= 0 ? a2[i] + c[u] : -1;
conv(a2c, C0, n1); // v có tủ: u bắt đầu được phục vụ
conv(a2, g1, n2);
a0.swap(n0); a1.swap(n1); a2.swap(n2);
vl().swap(A0[v]); vl().swap(A1[v]); vl().swap(A2[v]);
}
A0[u] = a0; A1[u] = a1; A2[u] = a2;
}
string out;
for (int j = 1; j <= n; j++) {
out += to_string(max({A0[1][j], A1[1][j], A2[1][j]}));
out += (j < n ? ' ' : '\n');
}
fputs(out.c_str(), stdout);
}import sys
def conv(A, B, out):
# tích chập (max, +): out[i + t] = max(out[i + t], A[i] + B[t]); giá trị âm = "không thể".
# Duyệt từng phần tử của mảng ngắn hơn, mảng dài hơn được xử lý cả đoạn bằng list comprehension.
if len(A) > len(B):
A, B = B, A
m = len(B)
for i in range(len(A)):
x = A[i]
if x >= 0:
out[i:i + m] = [s if s >= x + y else x + y for s, y in zip(out[i:i + m], B)]
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = [0] + [int(x) for x in data[1:1 + n]]
adj = [[] for _ in range(n + 1)]
p = 1 + n
for _ in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); p += 2
adj[u].append(v); adj[v].append(u)
# thứ tự BFS từ gốc 1, xử lý ngược lại để con luôn xong trước cha
par = [0] * (n + 1)
par[1] = -1
order = [1]
for u in order:
for v in adj[u]:
if v != par[u]:
par[v] = u
order.append(v)
NEG = -10 ** 18 # "không thể"; mọi giá trị âm đều coi là không thể
# A0: u có tủ sách; A1: u không có tủ, được một con phục vụ; A2: u không có tủ, chưa được phục vụ
A0 = [None] * (n + 1); A1 = [None] * (n + 1); A2 = [None] * (n + 1)
for k in range(n - 1, -1, -1):
u = order[k]
cu = c[u]
a0 = [NEG, cu]; a1 = [NEG, NEG]; a2 = [0, NEG]
for v in adj[u]:
if v == par[u]:
continue
C0 = A0[v]; C1 = A1[v]; C2 = A2[v]
cv = c[v]
g1 = [x if x >= y else y for x, y in zip(C1, C2)] # u không có tủ: v không được u phục vụ
g0 = [x if x >= y else y for x, y in zip(C1, C0)]
g0 = [x if x >= y + cv else y + cv for x, y in zip(g0, C2)] # u có tủ: v chắc chắn được phục vụ
hh = [x if x >= y else y for x, y in zip(C0, g1)]
L = len(a0) + len(C0) - 1
n0 = [NEG] * L; n1 = [NEG] * L; n2 = [NEG] * L
a2c = [x + cu for x in a2] # v có tủ: u bắt đầu được phục vụ
conv(a0, g0, n0)
conv(a1, hh, n1)
conv(a2c, C0, n1)
conv(a2, g1, n2)
a0 = n0; a1 = n1; a2 = n2
A0[v] = A1[v] = A2[v] = None
A0[u] = a0; A1[u] = a1; A2[u] = a2
a0, a1, a2 = A0[1], A1[1], A2[1]
res = [max(a0[j], a1[j], a2[j]) for j in range(1, n + 1)]
sys.stdout.write(" ".join(map(str, res)) + "\n")
main()Tổng số học trò có thể tới $3000 \cdot 10^9 = 3 \cdot 10^{12}$, vượt int: mọi giá trị QHĐ phải là long long.
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 tập ấp | Đúng | TLE | Sai/TLE | TLE | 10 |
| Cách 2 – QHĐ trên con lộ thẳng | 0/8 | Đúng | 0/8 | 0/10 | 20 |
| Cách 3 – QHĐ trên cây, gộp thẳng tay O(N³) | Đúng | TLE | Đúng | TLE | 40 |
| Cách 4 – gộp theo kích thước cây con O(N²) (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | 100 |
| Chậm: chỉ chặn vòng ngoài, vòng trong chạy tới N | Đúng | Đúng | Đúng | 2/10 (TLE) | 68 |
Sai: dùng int | 5/8 | 3/7 | 3/8 | 3/10 | 38,07 |
| Sai: tham lam – mỗi lần đặt tủ ở ấp phục vụ thêm nhiều nhất | 6/8 | 1/7 | 2/8 | 2/10 | 25,86 |
| Sai: khi u có tủ quên cộng học trò của con đang "chưa được phục vụ" | 0/8 | 0/7 | 0/8 | 0/10 | 0 |
| Sai: u được con phục vụ nhưng quên cộng $c_u$ | 0/8 | 0/7 | 0/8 | 0/10 | 0 |
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: 33 test (subtask 1: 8 test, subtask 2: 7 test, subtask 3: 8 test, subtask 4: 10 test), chấm kiểu "đúng test nào được điểm test đó". Mọi test subtask 2 và 4 có $N$ xấp xỉ $3000$, subtask 3 có $N = 300$. Cây trong bộ test có đủ hình dạng: ngẫu nhiên, gần như một đường dài, hình sao, cây nhị phân, chổi, sâu bướm, hai tâm, nhiều nhện chân dài; ở subtask 4, 8/10 test có một (hoặc hai) ấp "tâm" nối trực tiếp với khoảng 78% số ấp, trộn với phần còn lại có hình dạng khác (chổi, sâu bướm, nhị phân, ngẫu nhiên, nhện, đường dài) — để bắt các bạn chỉ chặn một nửa vòng lặp; nhãn các ấp được xáo trộn. Số học trò có loại rất lớn ($10^9$, tổng vượt int), loại nhỏ và loại "vài ấp rất đông". Lời giải chuẩn C++ chạy chưa tới 0,05 giây. Bản Python nên nộp bằng PyPy 3 (giới hạn 5 giây).
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