Trò Chơi (HSG12 Hà Nội 2025 – Bài 4)
Đề bài
Bài IV. Trò chơi (3,0 điểm)
Công ty của Chiến tổ chức trò chơi chọn số trong buổi tiệc cuối năm. Ban tổ chức chuẩn bị sẵn một bộ số gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$ và $N$ tấm thẻ. Trên mỗi tấm thẻ ghi một số tự nhiên có giá trị từ $1$ đến $N$, các giá trị trên thẻ đôi một khác nhau. Ban tổ chức sẽ phát cho mỗi người chơi một tấm thẻ bất kỳ trong $N$ tấm thẻ trên. Luật chơi đưa ra như sau:
- Giả sử người chơi nhận được tấm thẻ ghi số nguyên $K$;
- Sau đó, người chơi chọn ra tối đa $K$ đoạn con trên bộ số ban đầu mà Ban tổ chức đã chuẩn bị, mỗi đoạn gồm một hoặc nhiều phần tử liên tiếp, các đoạn con không có phần tử chung. Người chơi có quyền không chọn đoạn con nào;
- Điểm của người chơi là tổng các số trong các đoạn đã chọn. Ban tổ chức sẽ trao phần thưởng tương ứng với số điểm mà người chơi đạt được.
Yêu cầu: Có $Q$ người chơi khác nhau. Em hãy lập trình đưa ra số điểm lớn nhất mà mỗi người chơi có thể nhận được.
Dữ liệu vào từ file văn bản TROCHOI.INP:
- Dòng đầu tiên chứa hai số nguyên $N, Q$ $(1 \le Q \le N \le 10^5)$ tương ứng số lượng phần tử trong bộ số và số lượng người tham gia trò chơi;
- Dòng thứ hai chứa $N$ số nguyên, số nguyên thứ $i$ biểu diễn giá trị của $A_i$ $(-10^4 \le A_i \le 10^4)$;
- Dòng thứ ba chứa $Q$ số nguyên, số nguyên thứ $i$ là $K_i$ $(1 \le K_i \le N)$ mô tả số ghi trên tấm thẻ của người chơi thứ $i$. Các $K_i$ đảm bảo phân biệt và được sắp xếp theo thứ tự tăng dần.
Kết quả ghi ra file văn bản TROCHOI.OUT: Gồm $Q$ dòng, dòng thứ $i$ tương ứng là kết quả của người chơi thứ $i$ khi được phát tấm thẻ ghi số $K_i$.
Ràng buộc:
- Có 20% số test ứng với 20% số điểm có $N \le 10^5$; $Q = 1$; $K = 1$;
- 20% số test khác ứng với 20% số điểm có $N \le 10^5$; $Q = 1$; $K \le 2$;
- 20% số test khác ứng với 20% số điểm có $N \le 10^5$; $Q = 1$; $K \le 50$;
- 20% số test khác ứng với 20% số điểm có $N \le 10^5$; $Q = 1$; $K \le N$;
- 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.
Lưu ý: đề gốc đọc/ghi file TROCHOI.INP / TROCHOI.OUT; trên CLUE OJ thì đọc từ bàn phím, in ra màn hình (giới hạn trên CLUE: 1 giây, 1 GB).
5 3
1 -1 2 -2 3
1 2 53
5
6– Với $K_2 = 2$, chọn đoạn $[3, 3]$ và đoạn $[5, 5]$;
– Với $K_3 = 5$, chọn đoạn $[1, 1]$, $[3, 3]$ và $[5, 5]$.
Lời mở đầu
Đây là bài 4 – bài cuối và cũng là bài khó nhất trong đề thi học sinh giỏi Tin học lớp 12 thành phố Hà Nội năm 2025. Đề bài phát biểu rất gọn: chọn tối đa $K$ đoạn con không giao nhau sao cho tổng lớn nhất, nhưng để ăn trọn 100% điểm thì cần tới kỹ thuật chia để trị kết hợp tổng Minkowski của hàm lồi – một kỹ thuật khá "nặng đô" với học sinh. Vì vậy mình viết lời giải đi từng bậc theo subtask: subtask 1 là bài toán đoạn con có tổng lớn nhất quen thuộc, subtask 2 mở rộng ra 2 đoạn, subtask 3 dùng quy hoạch động, và cuối cùng là lời giải đầy đủ. Bạn nào đi thi chỉ cần làm chắc 3 subtask đầu là đã có 60% điểm bài này rồi. Hy vọng mang đến được giá trị cho các bạn 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJMình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Dãy số là $1, -1, 2, -2, 3$ (vị trí từ $1$ đến $5$):
| Thẻ K | Cách chọn tốt nhất | Điểm |
|---|---|---|
| $K = 1$ | Chỉ 1 đoạn: $[5, 5]$ (chỉ lấy số $3$). Các đoạn dài hơn như $[1, 5]$ chỉ được $1 - 1 + 2 - 2 + 3 = 3$, không hơn. | $3$ |
| $K = 2$ | $[3, 3]$ và $[5, 5]$: $2 + 3$. | $5$ |
| $K = 5$ | $[1, 1]$, $[3, 3]$, $[5, 5]$: $1 + 2 + 3$. Dù được chọn tới $5$ đoạn, nhưng chọn thêm đoạn nào chứa số âm cũng chỉ làm giảm điểm, nên chỉ chọn $3$ đoạn (đề cho phép chọn tối đa $K$ đoạn). | $6$ |
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Trong cả bài, mình dùng mảng cộng dồn $pre[i] = A_1 + A_2 + \cdots + A_i$ (với $pre[0] = 0$). Khi đó tổng đoạn $[l, r]$ là $pre[r] - pre[l - 1]$.
Subtask 1K = 1: đoạn con có tổng lớn nhất – O(N)
Với $K = 1$, bài toán chuyển về tìm đoạn con có tổng lớn nhất trong mảng $A$. Đối với mỗi vị trí $i$ $(1 \le i \le n)$ là điểm kết thúc của đoạn, ta sẽ tìm vị trí bắt đầu $j$ sao cho $pre[i] - pre[j - 1]$ là lớn nhất có thể.
Vì $pre[i]$ đã cố định, muốn hiệu lớn nhất thì $pre[j - 1]$ phải nhỏ nhất. Nghĩa là $j$ tối ưu sẽ có $pre[j - 1]$ nhỏ nhất trong khoảng $j - 1$ từ $0$ đến $i - 1$. Giá trị nhỏ nhất này rất dễ cập nhật sau mỗi lần tăng $i$: chỉ cần một biến mn, xét xong vị trí $i$ thì mn = min(mn, pre[i]).
Minh hoạ: quét mảng cộng dồn
Các bạn nhập dãy $A$ rồi bấm Tiếp. Ô viền cam là $pre[i]$ đang xét, ô tím là $pre[t]$ nhỏ nhất phía trước, các ô xanh trên hàng $A$ là đoạn tốt nhất tìm được đến lúc này:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q;
int a[100005];
int k[100005];
int pre[100005];
namespace sub1{
void solve(){
for (int i = 1; i <= q; i ++){
int res = 0; // được phép không chọn đoạn nào
int mn = 0;
for (int j = 1; j <= n; j ++){
res = max(res, pre[j] - mn);
mn = min(mn, pre[j]);
}
cout << res << endl;
}
}
};
signed main(){
if(fopen("TROCHOI.INP", "r")){
freopen("TROCHOI.INP", "r", stdin);
freopen("TROCHOI.OUT", "w", stdout);
}
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= q; i ++){
cin >> k[i];
}
for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + a[i];
sub1::solve();
}import sys
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
k = [0] + [int(x) for x in data[2 + n:2 + n + q]]
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + a[i]
out = []
for i in range(1, q + 1):
res = 0 # được phép không chọn đoạn nào
mn = 0
for j in range(1, n + 1):
res = max(res, pre[j] - mn)
mn = min(mn, pre[j])
out.append(res)
print("\n".join(map(str, out)))res được khởi tạo bằng -1e18, nên nếu dãy toàn số âm thì code in ra số âm lớn nhất (ví dụ -2 với dãy -5 -2 -7). Nhưng đề cho phép không chọn đoạn nào, nên đáp án đúng là 0. Khi soạn lại bài này mình đã sửa thành res = 0. Code này chỉ dành cho $K = 1$ (nó không đọc tới giá trị $K$).Đánh giá độ phức tạp của cách làm này: mỗi truy vấn duyệt mảng một lần, mà subtask 1 có $Q = 1$.
Subtask 2K ≤ 2: hai đoạn không giao nhau – O(N)
Với $K = 2$, chúng ta cần tìm (tối đa) hai đoạn con không giao nhau sao cho có tổng lớn nhất. Vậy đối với mỗi $i$, ta sẽ coi $i$ là vị trí bắt đầu của đoạn con thứ 2. Khi này, tổng tối ưu có thể đạt được bằng:
- Vế 1: tổng của đoạn con lớn nhất mà đầu cuối của nó nhỏ hơn $i$ (nằm gọn trong $[1, i - 1]$). Vế này giống hệt subtask 1: ta duy trì biến
mx_sum= tổng đoạn con lớn nhất trong $[1, i - 1]$, cập nhật sau mỗi lần tăng $i$. - Vế 2: tổng của đoạn con lớn nhất mà bắt đầu tại $i$, tức là ta cần tìm $j$ trong khoảng từ $i$ đến $n$ sao cho $pre[j] - pre[i - 1]$ lớn nhất. Đến đây ta tính trước $mx\_pre[i] = \max(pre[i], pre[i + 1], \ldots, pre[n])$ bằng cách duyệt ngược từ $n$ về và cập nhật mỗi lần giảm chỉ số.
Cuối cùng còn phải so với trường hợp chỉ chọn 1 đoạn và không chọn đoạn nào.
- Bản đầu mình viết
mx_pre[j + 1] - pre[j - 1]và đểmx_pre[n + 1] = 0(mảng toàn cục). Như vậy đoạn thứ 2 bắt đầu tại $j$ nhưng lại kết thúc từ $j + 1$ trở đi, và còn "kết thúc tại $n + 1$" với giá trị $0$ – sai. Ví dụ dãy5 -100 3, $K = 2$: đúng là $8$ nhưng code cũ in $100$. Đúng theo phân tích phải làmx_pre[j]vàmx_pre[n + 1] = -1e18. - Subtask 2 có $K \le 2$, tức là có cả test $K = 1$; code cũ luôn ghép 2 đoạn. Giờ chỉ ghép khi
k[i] >= 2. - Được chọn ít hơn $K$ đoạn (1 đoạn hoặc không đoạn nào), nên
resbắt đầu từ $0$ và cuối cùng lấy thêmmax(res, mx_sum).
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q;
int a[100005];
int k[100005];
int pre[100005];
namespace sub2{
int mx_pre[100005];
void solve(){
for (int i = 1; i <= q; i ++){
int res = 0; // được phép không chọn đoạn nào
int mn = 0;
int mx_sum = -1e18;
mx_pre[n + 1] = -1e18;
for (int j = n; j >= 1; j --){
mx_pre[j] = max(mx_pre[j + 1], pre[j]);
}
for (int j = 1; j <= n; j ++){
if (k[i] >= 2) res = max(res, mx_sum + mx_pre[j] - pre[j - 1]);
mx_sum = max(mx_sum, pre[j] - mn);
mn = min(mn, pre[j]);
}
res = max(res, mx_sum); // chỉ chọn 1 đoạn
cout << res << endl;
}
}
};
signed main(){
if(fopen("TROCHOI.INP", "r")){
freopen("TROCHOI.INP", "r", stdin);
freopen("TROCHOI.OUT", "w", stdout);
}
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= q; i ++){
cin >> k[i];
}
for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + a[i];
sub2::solve();
}import sys
NEG = -10**18
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
k = [0] + [int(x) for x in data[2 + n:2 + n + q]]
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + a[i]
out = []
mx_pre = [NEG] * (n + 2)
for i in range(1, q + 1):
res = 0 # được phép không chọn đoạn nào
mn = 0
mx_sum = NEG
for j in range(n, 0, -1):
mx_pre[j] = max(mx_pre[j + 1], pre[j])
for j in range(1, n + 1):
if k[i] >= 2:
res = max(res, mx_sum + mx_pre[j] - pre[j - 1])
mx_sum = max(mx_sum, pre[j] - mn)
mn = min(mn, pre[j])
res = max(res, mx_sum) # chỉ chọn 1 đoạn
out.append(res)
print("\n".join(map(str, out)))Đánh giá độ phức tạp của cách làm này: một vòng duyệt ngược để tính $mx\_pre$ và một vòng duyệt xuôi, mỗi vòng $O(N)$.
Subtask 3K ≤ 50: quy hoạch động – O(N·K)
Khi $K$ lớn hơn thì cách "ghép" ở trên không dùng được nữa, ta chuyển sang quy hoạch động.
Giả sử đoạn thứ $j$ là $[s, i]$, còn $j - 1$ đoạn trước đó kết thúc tại $u$ nào đó với $u \lt s$. Tổng là $f[u][j - 1] + pre[i] - pre[s - 1]$. Với $u$ cố định, $s - 1$ có thể là bất kỳ vị trí nào trong $[u, i - 1]$, nên ta chọn $pre[s - 1]$ nhỏ nhất:
(quy ước "chọn $0$ đoạn" có giá trị $0$, ứng với $u = 0$, $j - 1 = 0$).
Tính thẳng công thức này là $O(N^2 K)$ – quá chậm. Để tối ưu hoá, ta tạo thêm hai mảng:
- $mx[j]$: max của các giá trị $f[x][j]$ với $x \le i$ (vị trí đang xét hiện tại) – tức là tổng lớn nhất khi chọn đúng $j$ đoạn trong $i$ phần tử đầu. Có thể dễ dàng cập nhật sau mỗi lần duyệt $i$. Riêng $mx[0] = 0$.
- $cur[j]$: max của các giá trị $mx[j]$ tại thời điểm $t$ trừ đi $pre[t]$, với mọi $t \le i - 1$. Hiểu nôm na: "$j$ đoạn đã chốt xong trong $[1, t]$, đoạn tiếp theo sẽ bắt đầu từ $t + 1$".
Ở đây, có thể thấy rằng trạng thái $f[i][j] = cur[j - 1] + pre[i]$. Việc của chúng ta bây giờ là tìm cách cập nhật $cur[j]$: sau khi xét xong vị trí $i$, có thêm một lựa chọn mới là "đoạn tiếp theo bắt đầu từ $i + 1$", giá trị của nó là $mx[j] - pre[i]$. Ta so với $cur[j]$ hiện có để xem ai lớn hơn mà lấy:
2. $mx[j] = \max(mx[j], f[i][j])$.
3. $cur[j] = \max(cur[j], mx[j] - pre[i])$ với $j = 0..50$.
Đáp án với thẻ $K$: $\max(mx[0], mx[1], \ldots, mx[K])$ – lấy max vì được chọn tối đa $K$ đoạn.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q;
int a[100005];
int k[100005];
int pre[100005];
namespace sub3{
int f[100005][55];
int mx[55];
int cur[55];
void solve(){
for (int j = 0; j <= 50; j ++){
mx[j] = cur[j] = -1e18;
}
mx[0] = 0;
cur[0] = 0;
for (int i = 0; i <= n; i ++){
for (int j = 1; j <= 50; j ++) f[i][j] = -1e18;
}
f[0][0] = 0;
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= 50; j ++){
f[i][j] = cur[j - 1] + pre[i];
}
for (int j = 1; j <= 50; j ++){
mx[j] = max(mx[j], f[i][j]);
}
for (int j = 0; j <= 50; j ++){
cur[j] = max(cur[j], mx[j] - pre[i]);
}
}
for (int i = 1; i <= q; i ++){
int res = -1e18;
for (int j = 0; j <= k[i]; j ++){
res = max(res, mx[j]);
}
cout << res << endl;
}
}
};
signed main(){
if(fopen("TROCHOI.INP", "r")){
freopen("TROCHOI.INP", "r", stdin);
freopen("TROCHOI.OUT", "w", stdout);
}
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= q; i ++){
cin >> k[i];
}
for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + a[i];
sub3::solve();
}import sys
NEG = -10**18
K = 50
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
k = [0] + [int(x) for x in data[2 + n:2 + n + q]]
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + a[i]
mx = [NEG] * (K + 1)
cur = [NEG] * (K + 1)
mx[0] = 0
cur[0] = 0
for i in range(1, n + 1):
p = pre[i]
# f[i][j] = cur[j - 1] + pre[i] (chỉ cần hàng hiện tại)
f = [NEG] + [cur[j - 1] + p for j in range(1, K + 1)]
for j in range(1, K + 1):
if f[j] > mx[j]:
mx[j] = f[j]
for j in range(K + 1):
if mx[j] - p > cur[j]:
cur[j] = mx[j] - p
out = []
for i in range(1, q + 1):
out.append(max(mx[0:k[i] + 1]))
print("\n".join(map(str, out)))f[100005][50], mx[50], cur[50] nhưng lại duyệt j tới 50, tức là truy cập phần tử thứ 51 – ra ngoài mảng (chạy với -fsanitize sẽ báo lỗi ngay). Mình đã sửa kích thước thành 55. Ngoài ra mảng $f$ thực ra chỉ cần hàng hiện tại (bản Python mình chỉ giữ một hàng), nhưng bản C++ mình vẫn giữ nguyên mảng 2 chiều cho dễ hiểu. Code này chỉ đúng khi $K \le 50$.Trong khung chạy tay, để đỡ dài mình chỉ chạy tay từng $j$ từ $0$ tới $n$ (với $j \gt n$ không thể chọn đủ $j$ đoạn nên giá trị vẫn là $-10^{18}$, ghi là −∞) và gom các $j$ còn lại tới $50$ thành 1 bước.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N \cdot 50)$ cho mảng $f$ (khoảng 44 MB với
long long; nếu chỉ giữ một hàng thì còn $O(N + 50)$). - Thời gian: mỗi $i$ duyệt $j$ tới $50$ ba lần, nên $O(N \cdot K)$ với $K = 50$. Cách này giải được cả subtask 1, 2, 3 (60% điểm).
Subtask 4 + 5Chia để trị + tổng Minkowski của hàm lồi – O(N log N)
Phần này khá nặng, mình đi từng bước nha.
Bước 1: Định nghĩa hàm f
Gọi $f^{a,b}(l, r, x)$ là tổng tối đa khi ta chọn không quá $x$ đoạn liên tiếp không giao nhau trong $A[l..r]$, khi:
- Nếu $a = 1$ thì phần tử $l$ có nằm trong 1 trong các đoạn, $a = 0$ thì ngược lại (phần tử $l$ không được chọn);
- Nếu $b = 1$ thì phần tử $r$ có nằm trong 1 trong các đoạn, $b = 0$ thì ngược lại.
Để cho thuận tiện, ở phần sau nếu mình viết $f(l, r)$ thì có thể hiểu là biểu thức đúng với mọi cặp giá trị $(a, b)$, và $f(l, r)$ được coi như một dãy số $f(l, r, 0), f(l, r, 1), \ldots, f(l, r, r - l + 1)$ (chọn nhiều hơn $r - l + 1$ đoạn thì không thể có thêm gì nữa). Trong code, đây chính là vector dp[a][b] của struct Answer. Trạng thái không thể xảy ra (ví dụ $a = 1$ mà $x = 0$) có giá trị $-\infty$ (code dùng $-10^9$).
Đáp án của truy vấn $K$ là $\max\limits_{a, b} f^{a,b}(1, n, K)$.
Bước 2: Chia để trị – ghép hai nửa
Gọi $m = \left\lfloor \frac{l + r}{2} \right\rfloor$. Giả sử ta đã tính được $f(l, m)$ và $f(m + 1, r)$ (bằng đệ quy). Một cách chọn đoạn trên $[l, r]$ "cắt" ở giữa $m \mid m + 1$ sẽ thành một cách chọn trên nửa trái và một cách chọn trên nửa phải. Chỉ có một điểm cần chú ý: nếu có một đoạn vắt qua chỗ cắt, nó bị tách thành 2 mảnh (một mảnh kết thúc tại $m$, một mảnh bắt đầu tại $m + 1$), nên khi ghép lại số đoạn phải trừ đi 1.
Vì vậy ta cần biết ô $m$ và ô $m + 1$ có được chọn hay không – đó là lý do phải lưu thêm 2 chỉ số $a, b$. Gọi $c$ là trạng thái của ô $m$ (bên trái), $d$ là trạng thái của ô $m + 1$ (bên phải). Có 4 trường hợp:
Phép toán "$\max\limits_{x' + y' = x} \big(P[x'] + Q[y']\big)$" của hai dãy $P, Q$ được gọi là tích chập max-plus. Tính trực tiếp thì mất $O(|P| \cdot |Q|)$, cả thuật toán sẽ thành $O(N^2)$ – vẫn chậm. Ta cần thêm 2 bổ đề.
Bước 3: Bổ đề 1 – f là hàm lồi
Tức là: "lợi nhuận" khi được phép chọn thêm đoạn thứ $x$ không nhỏ hơn lợi nhuận khi chọn thêm đoạn thứ $x + 1$.
Nhìn vào ví dụ của đề: với cả dãy $1, -1, 2, -2, 3$ ta có $f(0..5) = 0, 3, 5, 6, 6, 6$; dãy hiệu là $3, 2, 1, 0, 0$ – giảm dần. Đoạn thứ nhất lời $3$, cho phép thêm đoạn thứ hai lời thêm $2$, thêm đoạn thứ ba lời thêm $1$, sau đó hết lời.
- cạnh $s \to i$ và cạnh $i \to t$ với mọi $i$, khả năng thông qua $1$, giá trị $0$;
- cạnh $i \to i + 1$ với $1 \le i \le n$, khả năng thông qua $1$, giá trị $A_i$.
Bước 4: Bổ đề 2 – tích chập hai dãy lồi = trộn hai dãy hiệu
Đặt $p_i = P[i] - P[i - 1]$ và $q_i = Q[i] - Q[i - 1]$ (dãy hiệu). Theo bổ đề 1, cả hai dãy hiệu đều giảm dần. Gọi $c$ là dãy gồm tất cả các phần tử của $p$ và $q$, sắp xếp giảm dần.
Hiểu nôm na theo kiểu tham lam: ban đầu $x' = y' = 0$. Mỗi lần tăng $x$ thêm $1$, ta được chọn tăng $x'$ hoặc $y'$ thêm $1$, và ta chọn bên nào cho "lời" nhiều hơn (bước hiệu lớn hơn). Vì các bước hiệu mỗi bên đều giảm dần, nên lấy cái lớn trước luôn không thiệt. Về mặt hình học: gọi đa giác $A$ chứa các đỉnh $(i, P[i])$, đa giác $B$ chứa các đỉnh $(i, Q[i])$ – đều là đa giác lồi. Kết quả chính là tổng Minkowski của $A$ và $B$, và thuật toán trên mô phỏng lại thuật toán tính tổng Minkowski hai đa giác lồi (trộn các cạnh theo độ dốc).
Và vì $p$, $q$ đã sắp xếp giảm dần sẵn, ta không cần sort mà chỉ cần trộn như bước trộn của Merge sort, mất $O(|P| + |Q|)$. Đó chính là hàm convolute trong code.
Minh hoạ: trộn hai dãy hiệu
Các bạn nhập 2 dãy lồi $P$, $Q$ (dãy hiệu giảm dần) rồi bấm Tiếp. Mỗi bước lấy bước hiệu lớn hơn ở đầu 2 dãy hiệu. Bước cuối mình so luôn với cách thử mọi cặp $(x', y')$ để các bạn thấy kết quả khớp:
Bước 5: Ghép lại và đánh giá độ phức tạp
Ta có thêm nhận xét: khi tính $f(l, m, x)$ ta chỉ cần quan tâm các giá trị $0 \le x \le m - l + 1$, tương tự với $f(m + 1, r)$ và $f(l, r)$. Nên mỗi lần ghép chỉ mất $O(r - l)$. Thuật toán chia để trị: gọi đệ quy tính $f(l, m)$ và $f(m + 1, r)$, sau đó ghép ra $f(l, r)$. Độ phức tạp $T(n) = 2T(n/2) + O(n) = O(n \log n)$.
sort thì mỗi lần ghép mất $O((r - l) \log n)$ và cả thuật toán là $O(n \log^2 n)$ – vẫn hơi chậm: cài đặt mẫu theo cách này bị TLE 4 test trên bộ test của SQRTOJ. Nhờ bổ đề 1, hai dãy hiệu đã sắp xếp giảm dần sẵn nên chỉ cần trộn kiểu Merge sort, giảm bước này về $O(n)$, độ phức tạp cuối cùng là $O(n \log n)$ – đủ nhanh để giải quyết bài toán.Source code của tất cả các phân tích ở trên để các bạn tham khảo:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q;
int a[100005];
int k[100005];
int pre[100005];
namespace sub5{
vector<int> convolute(vector<int> a, vector<int> b)
{
vector<int> sus;
int j = 1;
for(int i = 1; i < a.size(); i++){
while(j < b.size() && b[j]-b[j-1] > a[i]-a[i-1]){
sus.push_back(b[j]-b[j-1]); j++;
}
sus.push_back(a[i]-a[i-1]);
}
while(j < b.size()){
sus.push_back(b[j]-b[j-1]); j++;
}
int cur = a[0] + b[0];
vector<int> ans = {cur};
for(int i : sus){
cur += i; ans.push_back(cur);
}
return ans;
}
vector<int> combine(vector<int> a, vector<int> b)
{
vector<int> ans(a.size());
for(int i = 0; i < a.size(); i++) ans[i] = max(a[i], b[i]);
return ans;
}
vector<int> reduce(vector<int> a)
{
for(int i = 0; i+1 < a.size(); i++) a[i] = max(a[i], a[i+1]);
return a;
}
struct Answer
{
vector<int> dp[2][2];
};
Answer solve(int l, int r)
{
if(l == r){
Answer ans;
ans.dp[0][0] = {0, 0};
ans.dp[1][1] = {-1000000000, a[l]};
ans.dp[0][1] = {-1000000000, -1000000000};
ans.dp[1][0] = {-1000000000, -1000000000};
return ans;
}
Answer ans;
Answer x = solve(l, (l+r)/2), y = solve((l+r)/2+1, r);
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
ans.dp[i][j] = convolute(x.dp[i][0], y.dp[0][j]);
ans.dp[i][j] = combine(ans.dp[i][j], convolute(x.dp[i][0], y.dp[1][j]));
ans.dp[i][j] = combine(ans.dp[i][j], convolute(x.dp[i][1], y.dp[0][j]));
ans.dp[i][j] = combine(ans.dp[i][j], reduce(convolute(x.dp[i][1], y.dp[1][j])));
}
}
return ans;
}
void solve(){
Answer ans = solve(1, n);
for (int i = 1; i <= q; i ++){
cout<<max(max(ans.dp[0][0][k[i]], ans.dp[0][1][k[i]]), max(ans.dp[1][0][k[i]], ans.dp[1][1][k[i]]))<<'\n';
}
}
};
signed main(){
if(fopen("TROCHOI.INP", "r")){
freopen("TROCHOI.INP", "r", stdin);
freopen("TROCHOI.OUT", "w", stdout);
}
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= q; i ++){
cin >> k[i];
}
for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + a[i];
sub5::solve();
}import sys
from operator import sub
NEG = -1000000000
def convolute(a, b):
# trộn 2 dãy hiệu (đều giảm dần) giống bước trộn của Merge sort
da = list(map(sub, a[1:], a[:-1]))
db = list(map(sub, b[1:], b[:-1]))
sus = []
j = 0
for x in da:
while j < len(db) and db[j] > x:
sus.append(db[j])
j += 1
sus.append(x)
sus.extend(db[j:])
cur = a[0] + b[0]
ans = [cur]
for d in sus:
cur += d
ans.append(cur)
return ans
def combine(a, b):
return list(map(max, a, b))
def reduce_(a):
return list(map(max, a, a[1:])) + a[-1:]
def solve(l, r):
if l == r:
return [[[0, 0], [NEG, NEG]],
[[NEG, NEG], [NEG, A[l]]]]
m = (l + r) // 2
x = solve(l, m)
y = solve(m + 1, r)
ans = [[None, None], [None, None]]
for i in range(2):
for j in range(2):
t = convolute(x[i][0], y[0][j])
t = combine(t, convolute(x[i][0], y[1][j]))
t = combine(t, convolute(x[i][1], y[0][j]))
t = combine(t, reduce_(convolute(x[i][1], y[1][j])))
ans[i][j] = t
return ans
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
A = [0] + [int(x) for x in data[2:2 + n]]
k = [int(x) for x in data[2 + n:2 + n + q]]
dp = solve(1, n)
out = []
for kk in k:
out.append(max(dp[0][0][kk], dp[0][1][kk], dp[1][0][kk], dp[1][1][kk]))
print("\n".join(map(str, out)))Giải thích 1 số chỗ trong code ở trên:
convolute(a, b): tích chập max-plus của 2 dãy lồi bằng cách trộn 2 dãy hiệu (bổ đề 2). Biếnsuslà dãy $c$ sau khi trộn, rồi cộng dồn từa[0] + b[0].combine(a, b): lấy max từng vị trí của 2 dãy – dùng để lấy max giữa 4 trường hợp $(c, d)$.reduce(a):a[i] = max(a[i], a[i + 1])– dùng cho trường hợp $c = d = 1$: dùng $i + 1$ "mảnh" nhưng 2 mảnh ở giữa nối lại thành 1 đoạn, nên chỉ tính là $i$ đoạn.- Ở lá $l = r$:
dp[0][0] = {0, 0}(không chọn ô $l$, được $0$ dù cho phép 0 hay 1 đoạn);dp[1][1] = {-1e9, a[l]}(chọn ô $l$: cần ít nhất 1 đoạn);dp[0][1],dp[1][0]là trạng thái mâu thuẫn (ô $l$ cũng chính là ô $r$) nên đều là $-\infty$. ans.dp[i][j](với $i = a$, $j = b$) là max của 4 trường hợp ghépx.dp[i][c]vớiy.dp[d][j]. Đáp án truy vấn $K$ là max của 4 trạng thái của cả dãy tại vị trí $K$.
Trong khung chạy tay, mình gom mỗi lời gọi convolute / combine / reduce thành 1 bước (bên trong convolute chính là quá trình trộn ở khung minh hoạ phía trên). Bảng "Dữ liệu" hiện 4 dãy dp[a][b] của nửa trái x, nửa phải y và kết quả ans đang ghép; −∞ là giá trị $-10^9$ (trạng thái không thể xảy ra, hoặc $-10^9$ cộng thêm vài số nhỏ).
Đánh giá độ phức tạp của cách làm này:
- Không gian: các lời gọi đang mở trên ngăn xếp đệ quy giữ các
vectorcó độ dài $N/2, N/4, \ldots$ (giảm một nửa mỗi tầng), cộng lại vẫn là $O(N)$. - Thời gian: mỗi lần ghép $[l, r]$ làm 16 lần
convolute/combine, mỗi lần $O(r - l)$; có $\log N$ tầng, mỗi tầng tổng độ dài $N$ ⇒ $O(N \log N)$. Mỗi truy vấn trả lời $O(1)$.
vector liên tục). Mình đo bản C++ với $N = Q = 10^5$ mất khoảng 0.6 giây, còn bản Python mất khoảng 7.5 giây – chắc chắn TLE. Bài này các bạn nên nộp C++.- 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