Trang Trí Tết (Thi thử HSG9 SQRTOJ 2025 – Bài 4)
Đề bài
Câu 4. TRANG TRÍ TẾT (3 điểm)
Người dân thành phố SQRT đang chuẩn bị đón Tết Ất Tỵ 2025.
Năm nay, do kinh tế khó khăn, chính quyền thành phố muốn tái sử dụng những món đồ trang trí Tết từ những năm trước đó. Một trong số đó là một dãy đèn lồng với nhiều màu sắc rực rỡ.
Dãy đèn lồng gồm $n$ chiếc được đánh số từ $1$ đến $n$. Chiếc đèn thứ $i$ có màu $a_i$. Chính quyền muốn chọn ra một đoạn gồm ít nhất $k$ chiếc đèn liên tiếp trong dãy để sử dụng trong năm mới, và thay thế một số chiếc đèn trong đoạn này sang một màu khác sao cho sau khi thay thế thì đoạn gồm tối đa $x$ màu khác nhau. Chi phí để thay thế một chiếc đèn sang màu khác là $1$ đồng.
Chính quyền muốn thử nghiệm $q$ phương án, mỗi phương án là một cặp số $(k, x)$ khác nhau. Với mỗi phương án, họ cần tính toán chi phí tối thiểu để có thể tạo ra đoạn đèn trang trí thỏa mãn yêu cầu.
Yêu cầu: Là một lập trình viên chuyên thực hiện những nhiệm vụ tính toán cho chính quyền thành phố, bạn hãy viết một chương trình giải quyết $q$ phương án thử nghiệm trên trong thời gian ngắn nhất.
Dữ liệu vào: Nhập từ file DECOR.inp:
- Dòng đầu tiên gồm ba số nguyên dương $n, q, c$ $(1 \le c \le n \le 10^5,\ 1 \le q \le 400)$.
- Dòng tiếp theo gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le c)$.
- $q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $k, x$ $(1 \le k \le n,\ 1 \le x \le c)$.
Dữ liệu ra: Ghi ra file DECOR.out:
- Với mỗi phương án thử nghiệm, in ra chi phí nhỏ nhất tìm được trên một dòng.
Ràng buộc bổ sung:
- $20\%$ số điểm có $n \le 200$ và $c = 2$.
- $20\%$ số điểm khác có $c = 2$.
- $20\%$ số điểm khác có $x = 1$ trong mọi phương án.
- $10\%$ số điểm khác có $q = 1$.
- $10\%$ số điểm khác có $k$ giống nhau trong mọi phương án.
- $10\%$ số điểm khác có $q \le 30$.
- $10\%$ số điểm còn lại không có giới hạn gì thêm.
Lưu ý: đề gốc đọc/ghi file DECOR.inp / DECOR.out; nộp trên web (SQRTOJ) thì đọc từ bàn phím và in ra màn hình. Code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng.
5 2 3
1 2 1 2 3
5 2
3 11
1Giải thích (theo đề):
- Với phương án thử nghiệm đầu tiên, chính quyền phải chọn toàn bộ dãy đèn và thay thế đèn số 5 thành màu 1 hoặc 2. Chi phí nhỏ nhất là 1 đồng.
- Với phương án thử nghiệm thứ hai, chính quyền có thể chọn đoạn $(2, 4)$ và thay thế đèn số 3 thành màu 2. Chi phí nhỏ nhất là 1 đồng.
Lời mở đầu
Đây là bài 4 trong đợt thi thử HSG lớp 9 năm 2025 của câu lạc bộ SQRT. Đề bài khá "đời": chọn một đoạn đèn rồi sơn lại cho đẹp với chi phí ít nhất 🏮. Đề có 7 subtask, lời giải của mình đi qua các mốc: duyệt trâu, mảng cộng dồn, cửa sổ trượt kết hợp đếm phân phối, rồi tối ưu dần để duy trì tổng $x$ tần suất lớn nhất trong cửa sổ. Hy vọng mang đến được giá trị cho các bạn 😇.
Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Dãy đèn có màu $1, 2, 1, 2, 3$.
Có 3 màu mà chỉ được giữ tối đa 2 màu → giữ màu 1 (2 đèn) và màu 2 (2 đèn), sơn lại đèn 5 → chi phí 1.
Đoạn $[2, 4]$ có 2 đèn màu 2 và 1 đèn màu 1, chỉ được giữ 1 màu → giữ màu 2, sơn đèn 3 → chi phí 1. Đoạn $[1, 3]$ cũng cho chi phí 1, còn đoạn $[3, 5]$ (3 màu khác nhau) thì tốn 2.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Nhận xét chung cho mọi subtask
Ta có thể thấy được rằng, chúng ta chỉ cần xét các đoạn liên tiếp có độ dài đúng bằng $k$ để tối ưu kết quả. Lý do: với một đoạn bất kỳ, chi phí tốt nhất là giữ nguyên các đèn thuộc $x$ màu xuất hiện nhiều nhất trong đoạn, sơn lại tất cả các đèn còn lại (sơn sang một màu đang được giữ nên không phát sinh màu mới). Nếu đoạn dài hơn $k$, bỏ bớt một đèn ở đầu mút thì độ dài giảm $1$, còn tổng số đèn được giữ giảm nhiều nhất $1$, nên chi phí không tăng. Cứ bỏ dần tới khi còn đúng $k$ đèn.
Các bạn nhập thử dữ liệu vào khung minh hoạ: mỗi bước là một đoạn độ dài $k$, biểu đồ cột là số đèn của từng màu trong đoạn (đã sắp xếp giảm dần), các cột viền xanh là $x$ màu được giữ lại:
Vấn đề bây giờ chỉ là: làm sao tính $T$ cho mọi đoạn thật nhanh. Mỗi subtask dưới đây là một cách làm điều đó.
Subtask 1c = 2, n ≤ 200 – Duyệt trâu từng đoạn, O(q · n · k)
Trong subtask này, ta có $c = 2$, tức là chúng ta chỉ có 2 loại màu khác nhau cho đèn, và số bóng đèn tương đối nhỏ.
Nhận xét: để tối ưu, khi thực hiện thay thế đèn, mỗi đèn được thay thế không quá 1 lần. Có 2 trường hợp:
- Nếu $x = 2 = c$: đoạn nào cũng đã có không quá 2 màu, không cần thay gì cả, đáp án là $0$.
- Nếu $x = 1$: giả sử trong đoạn $[l, r]$ có $op_1$ đèn màu 1 và $op_2$ đèn màu 2, số thao tác thay đèn tối thiểu là $\min(op_1, op_2)$ (sơn hết đèn của màu ít hơn sang màu kia).
Khi này, với mỗi truy vấn, ta có thể duyệt trâu tất cả các đoạn tồn tại có độ dài $k$, đếm số đèn màu 1 và 2, và tính toán được số thao tác tối thiểu cần dùng. Biến i trong code là vị trí cuối của đoạn, đoạn là $[i - k + 1, i]$.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int a[205];
int main()
{
if(fopen("DECOR.inp", "r")){
freopen("DECOR.inp", "r", stdin);
freopen("DECOR.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q, c;
cin >> n >> q >> c;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int test = 0; test < q; test++){
int k, x;
cin >> k >> x;
if(x == c){
cout << 0 << '\n';
continue;
}
int ans = 1e9;
for(int i = k; i <= n; i++){
int op1 = 0, op2 = 0;
for(int j = i-k+1; j <= i; j++){
if(a[j] == 1) op1++;
else op2++;
}
ans = min(ans, min(op1, op2));
}
cout << ans << '\n';
}
}import sys, os
def main():
if os.path.exists("DECOR.inp"):
sys.stdin = open("DECOR.inp")
sys.stdout = open("DECOR.out", "w")
data = sys.stdin.read().split()
n, q, c = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]]
pos = 3 + n
out = []
for test in range(q):
k, x = int(data[pos]), int(data[pos + 1])
pos += 2
if x == c:
out.append("0")
continue
ans = 10**9
for i in range(k, n + 1):
op1 = op2 = 0
for j in range(i - k + 1, i + 1):
if a[j] == 1:
op1 += 1
else:
op2 += 1
ans = min(ans, op1, op2)
out.append(str(ans))
print("\n".join(out))
main()
sys.stdout.flush()Vì code này chỉ dành cho $c = 2$, khung chạy tay bên dưới dùng các test có $c = 2$ (test của đề có $c = 3$ nên không dùng được ở đây):
Đánh giá độ phức tạp: mỗi phương án có $n - k + 1$ đoạn, mỗi đoạn đếm $k$ phần tử: $O(q \cdot n \cdot k)$. Với $n \le 200$, $q \le 400$ là khoảng $400 \cdot 200 \cdot 200 / 4 = 4 \cdot 10^6$ phép tính, chạy vèo vèo. Với thuật toán này, ta có thể AC được subtask 1.
Subtask 2c = 2 – Mảng cộng dồn, O(n + q · n)
Trong subtask này, ta vẫn có $c = 2$, tức là chúng ta chỉ có 2 loại màu khác nhau cho đèn, và không có điều kiện gì thêm về số bóng đèn ($n \le 10^5$).
Ta có thể thấy rằng, do chỉ có 2 loại đèn, ta có thể sử dụng mảng cộng dồn (prefix sum) để tính số đèn màu 1 và màu 2 trong khoảng $[l, r]$ cho trước trong $O(1)$, từ đó giảm được độ phức tạp thuật toán ở subtask 1:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int a[100005], cd[3][100005];
int main()
{
if(fopen("DECOR.inp", "r")){
freopen("DECOR.inp", "r", stdin);
freopen("DECOR.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q, c;
cin >> n >> q >> c;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
cd[1][i] = cd[1][i-1] + (a[i] == 1);
cd[2][i] = cd[2][i-1] + (a[i] == 2);
}
for(int test = 0; test < q; test++){
int k, x;
cin >> k >> x;
if(x == c){
cout << 0 << '\n';
continue;
}
int ans = 1e9;
for(int i = k; i <= n; i++){
ans = min(ans, min(cd[1][i] - cd[1][i-k], cd[2][i] - cd[2][i-k]));
}
cout << ans << '\n';
}
}import sys, os
def main():
if os.path.exists("DECOR.inp"):
sys.stdin = open("DECOR.inp")
sys.stdout = open("DECOR.out", "w")
data = sys.stdin.read().split()
n, q, c = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]]
pos = 3 + n
out = []
cd1 = [0] * (n + 1)
cd2 = [0] * (n + 1)
for i in range(1, n + 1):
cd1[i] = cd1[i - 1] + (a[i] == 1)
cd2[i] = cd2[i - 1] + (a[i] == 2)
for test in range(q):
k, x = int(data[pos]), int(data[pos + 1])
pos += 2
if x == c:
out.append("0")
continue
ans = 10**9
for i in range(k, n + 1):
ans = min(ans, cd1[i] - cd1[i - k], cd2[i] - cd2[i - k])
out.append(str(ans))
print("\n".join(out))
main()
sys.stdout.flush()Đánh giá độ phức tạp: dựng mảng cộng dồn $O(n)$, mỗi phương án duyệt $O(n)$ đoạn với $O(1)$ mỗi đoạn: tổng $O(n + q \cdot n)$, khoảng $4 \cdot 10^7$ phép tính. Với thuật toán này, ta có thể AC được subtask 1 và 2.
Subtask 3x = 1 – Cửa sổ trượt + đếm phân phối, O(q · n)
Ở subtask này, $x = 1$, tức chúng ta cần đổi màu sao cho các bóng đèn trong đoạn cùng một màu.
Dễ thấy rằng, cách tối ưu nhất là chuyển hết bóng đèn về màu có số bóng đèn nhiều nhất, từ đó bài toán chuyển về kiểm tra xem số bóng đèn nhiều nhất cùng một màu trong một đoạn độ dài $k$ là bao nhiêu (đáp án là $k$ trừ đi số đó).
Để làm được điều này, ta sẽ sử dụng kĩ thuật cửa sổ trượt (sliding window):
- $f[v]$ là số lượng bóng đèn hiện tại trong đoạn có màu $v$.
- $f2[t]$ là số lượng giá trị $v$ thỏa mãn $f[v] = t$ (có bao nhiêu màu xuất hiện đúng $t$ lần). Code khởi tạo $f2[0] = n$: coi như ban đầu có $n$ "màu" đều xuất hiện $0$ lần – thừa ra vài màu không có thật cũng không sao, vì chúng luôn ở mức $0$.
Dễ thấy khi trượt cửa sổ (thêm một đèn bên phải, bỏ một đèn bên trái), ta có thể duy trì được mảng $f$ và $f2$ trong $O(1)$. Mặt khác, do mỗi lần trượt cửa sổ đi 1 phần tử, số lần xuất hiện mỗi màu trong đoạn thay đổi không quá $1$, nên mọi phần tử trong mảng $f$ thay đổi không quá $1$, từ đó phần tử lớn nhất trong mảng $f$ cũng thay đổi không quá $1$.
- Thêm một đèn: nếu sau khi thêm có màu đạt $curmax + 1$ lần (tức $f2[curmax + 1] \gt 0$) thì
curmax++. - Bỏ một đèn: nếu sau khi bỏ không còn màu nào đạt $curmax$ lần (tức $f2[curmax] = 0$) thì
curmax--.
Bằng cách duy trì biến số curmax lưu số lớn nhất trong mảng $f$ thông qua mảng $f2$, ta có thể cập nhật lại biến đó trong $O(1)$, từ đó dẫn đến độ phức tạp cho 1 lần sliding window là $O(n)$.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int a[100005], f[100005], f2[100005];
int main()
{
if(fopen("DECOR.inp", "r")){
freopen("DECOR.inp", "r", stdin);
freopen("DECOR.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q, c;
cin >> n >> q >> c;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int test = 0; test < q; test++){
int k, x;
cin >> k >> x;
memset(f, 0, sizeof(f));
memset(f2, 0, sizeof(f2));
f2[0] = n;
int curmax = 0, ans = 0;
for(int i = 1; i <= n; i++){
f2[f[a[i]]]--; f[a[i]]++; f2[f[a[i]]]++;
if(f2[curmax+1] > 0) curmax++;
if(i >= k){
int p = i-k+1;
ans = max(ans, curmax);
f2[f[a[p]]]--; f[a[p]]--; f2[f[a[p]]]++;
if(f2[curmax] == 0) curmax--;
}
}
cout << k-ans << '\n';
}
}import sys, os
def main():
if os.path.exists("DECOR.inp"):
sys.stdin = open("DECOR.inp")
sys.stdout = open("DECOR.out", "w")
data = sys.stdin.read().split()
n, q, c = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]]
pos = 3 + n
out = []
for test in range(q):
k, x = int(data[pos]), int(data[pos + 1])
pos += 2
f = [0] * (n + 2)
f2 = [0] * (n + 2)
f2[0] = n
curmax = ans = 0
for i in range(1, n + 1):
v = a[i]
f2[f[v]] -= 1; f[v] += 1; f2[f[v]] += 1
if f2[curmax + 1] > 0:
curmax += 1
if i >= k:
ans = max(ans, curmax)
u = a[i - k + 1]
f2[f[u]] -= 1; f[u] -= 1; f2[f[u]] += 1
if f2[curmax] == 0:
curmax -= 1
out.append(str(k - ans))
print("\n".join(out))
main()
sys.stdout.flush()Trong code, vòng lặp i thêm đèn $i$ vào cửa sổ; khi i >= k thì cửa sổ $[i - k + 1, i]$ đã đủ $k$ đèn: ghi nhận curmax vào ans rồi bỏ đèn $p = i - k + 1$ ra để chuẩn bị cho cửa sổ kế tiếp. Lưu ý code này bỏ qua giá trị $x$ (vì subtask này luôn có $x = 1$):
Đánh giá độ phức tạp: mỗi phương án: 2 lần memset $O(n)$ và một lần trượt cửa sổ $O(n)$: tổng $O(q \cdot n)$. Với thuật toán này, ta có thể AC được subtask 3.
Subtask 6q ≤ 30 – Mảng tần suất đã sắp xếp + chặt nhị phân, O(q · n · log n)
Ở subtask này, $q \le 30$, cho phép ta có độ phức tạp lớn hơn một chút so với lời giải subtask 7.
Ta có thể tham lam như sau: ta sẽ không thay đổi màu các đèn có màu nằm trong $x$ màu có số lần xuất hiện lớn nhất trong đoạn, và ta thay đổi màu tất cả các đèn còn lại. Dễ thấy đây chính là cách giải tối ưu (như phần nhận xét chung ở trên). Vậy ta cần duy trì cursum = tổng $x$ phần tử lớn nhất của mảng $f$ khi trượt cửa sổ.
Ta sẽ thực hiện sliding window như lời giải của subtask 3, tuy nhiên ở đây ta sẽ lưu thêm 1 mảng $b$, là các phần tử của mảng $f$ khi đã sắp xếp theo thứ tự không giảm ($b[1] \le b[2] \le \ldots \le b[n]$). Khi đó $x$ phần tử lớn nhất là $b[n - x + 1], \ldots, b[n]$. Đến đây, ta sẽ cố thực hiện trượt 1 phần tử trong $O(\log n)$:
- Mỗi lần ta thực hiện tăng 1 phần tử của mảng $f$ (có giá trị $y$) thêm 1, ta sẽ thực hiện chặt nhị phân tìm vị trí cuối cùng xuất hiện giá trị $y$ trong mảng $b$ (
upper_bound - 1), và tăng giá trị đó lên 1. Tăng phần tử cuối cùng của một khối bằng nhau thì mảng vẫn không giảm. - Ngược lại, khi giảm 1 phần tử của mảng $f$ đi 1, ta sẽ thực hiện chặt nhị phân tìm vị trí đầu tiên xuất hiện giá trị $y$ trong mảng $b$ (
lower_bound), và giảm giá trị đó đi 1.
Có thể thấy được, bằng cách này, ta vẫn có thể giữ được tính không giảm cho mảng $b$. Mặt khác, nếu phần tử được tăng / giảm nằm trong $x$ phần tử lớn nhất của mảng $b$ (vị trí $p \gt n - x$), ta sẽ cập nhật cursum tương ứng (cộng hoặc trừ 1). Nhờ đó, ta đã có thể thực hiện sliding window trong $O(n \log n)$.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int a[100005], f[100005], b[100005];
int main()
{
if(fopen("DECOR.inp", "r")){
freopen("DECOR.inp", "r", stdin);
freopen("DECOR.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q, c;
cin >> n >> q >> c;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int test = 0; test < q; test++){
int k, x;
cin >> k >> x;
memset(f, 0, sizeof(f));
memset(b, 0, sizeof(b));
int cursum = 0, ans = 0;
for(int i = 1; i <= n; i++){
int y = f[a[i]];
int p = upper_bound(b+1, b+n+1, y)-b-1;
if(p > n-x) cursum++;
b[p]++; f[a[i]]++;
if(i >= k){
ans = max(ans, cursum);
y = f[a[i-k+1]];
p = lower_bound(b+1, b+n+1, y)-b;
if(p > n-x) cursum--;
b[p]--; f[a[i-k+1]]--;
}
}
cout << k-ans << '\n';
}
}from bisect import bisect_left, bisect_right
import sys, os
def main():
if os.path.exists("DECOR.inp"):
sys.stdin = open("DECOR.inp")
sys.stdout = open("DECOR.out", "w")
data = sys.stdin.read().split()
n, q, c = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]]
pos = 3 + n
out = []
for test in range(q):
k, x = int(data[pos]), int(data[pos + 1])
pos += 2
f = [0] * (n + 2)
b = [0] * (n + 1) # b[1..n] không giảm, b[0] không dùng
cursum = ans = 0
for i in range(1, n + 1):
y = f[a[i]]
p = bisect_right(b, y, 1, n + 1) - 1
if p > n - x:
cursum += 1
b[p] += 1; f[a[i]] += 1
if i >= k:
ans = max(ans, cursum)
y = f[a[i - k + 1]]
p = bisect_left(b, y, 1, n + 1)
if p > n - x:
cursum -= 1
b[p] -= 1; f[a[i - k + 1]] -= 1
out.append(str(k - ans))
print("\n".join(out))
main()
sys.stdout.flush()Đánh giá độ phức tạp: mỗi lần thêm / bỏ một đèn tốn $O(\log n)$ cho chặt nhị phân, mỗi phương án $O(n \log n)$: tổng $O(q \cdot n \log n)$. Với thuật toán này, ta có thể AC được subtask 1, 4 và 6 (và về lý thuyết đúng cho mọi test, chỉ là chậm hơn khi $q$ lớn).
Subtask 7Duy trì ngưỡng minval – O(q · n), lời giải đầy đủ
Ta sẽ cố gắng tối ưu thuật toán ở subtask 6, bằng cách khai thác mảng $f2$ từ ý tưởng của subtask 3. Thay vì giữ cả mảng $b$ đã sắp xếp, ta chỉ cần biết "ranh giới" của nhóm $x$ phần tử lớn nhất.
Ta sẽ sử dụng 3 biến:
cursum: là tổng của $x$ phần tử lớn nhất trong mảng $f$.minval: là giá trị nhỏ nhất trong $x$ giá trị lớn nhất trong mảng $f$ (nói cách khác,minvallà giá trị lớn thứ $x$ trong mảng $f$).curhold: là số phần tử trong mảng $f$ mà có giá trị $\ge minval$.
Ta sẽ có nhu cầu duy trì sao cho: số phần tử có giá trị $\gt minval$ thì nhỏ hơn $x$, còn $curhold \ge x$ – đúng nghĩa "giá trị lớn thứ $x$ là $minval$".
Vì mỗi thao tác trượt cửa sổ 1 phần tử, mọi giá trị trong mảng $f$ đều thay đổi không quá 1, vậy nên minval thay đổi không quá 1 và cursum thay đổi không quá 1. Từ đó ta có thể cập nhật minval trong $O(1)$ (nhờ mảng $f2$ cho biết có bao nhiêu màu đang ở đúng mức $minval$), và cập nhật cursum bằng cách kiểm tra xem phần tử thay đổi giá trị có nằm trong các phần tử có giá trị $\ge minval$ hay không:
- Nếu $y = minval - 1$: màu này vừa leo lên đúng mức $minval$ →
curhold++. Tổng $x$ số lớn nhất không đổi. - Nếu $y \ge minval$: màu này thuộc nhóm lớn nhất →
cursum++. Thêm nữa, nếu $y = minval$ và số phần tử $\ge minval + 1$ sau khi tăng, tức $curhold - (f2[minval] - 1)$, vẫn $\ge x$ thì ngưỡng nâng lên:curholdgiảm $f2[minval] - 1$ vàminval++.
- Nếu $y = minval$: màu này rơi khỏi mức $minval$ →
curhold--. - Nếu $y \gt minval$ (chắc chắn nằm trong nhóm lớn nhất), hoặc $y = minval$ mà giờ
curhold < x(không còn ai ở mức $minval$ thay thế được) →cursum--. Nếucurhold < xthì ngưỡng phải hạ xuống:minval--, vàcurholdcộng thêm số màu ở mức mới $f2[minval]$, cộng 1 cho chính màu vừa giảm (vì $f2$ chưa được cập nhật).
Nhờ đó, thuật toán của chúng ta đã đủ nhanh để giành điểm tuyệt đối cho bài tập này. Khung minh hoạ dưới đây cho các bạn xem từng thao tác thêm / bỏ: biểu đồ cột là $f$ của từng màu, đường nét đứt là mức minval; dòng cuối mình so cursum với tổng $x$ cột cao nhất tính trực tiếp để các bạn thấy nó luôn khớp:
Ghi chú nhỏ: curhold tính cả những "màu ảo" có tần suất $0$ (vì $f2[0] = n$), nên khi $minval = 0$ thì curhold có thể lớn hơn số màu thật – không sao cả, vì lúc đó mọi màu thật đều nằm trong nhóm lớn nhất.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int a[100005], f[100005], f2[100005];
int main()
{
if(fopen("DECOR.inp", "r")){
freopen("DECOR.inp", "r", stdin);
freopen("DECOR.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q, c;
cin >> n >> q >> c;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int test = 0; test < q; test++){
int k, x;
cin >> k >> x;
memset(f, 0, sizeof(f));
memset(f2, 0, sizeof(f2));
f2[0] = n;
int cursum = 0, minval = 0, curhold = n;
int ans = 0;
for(int i = 1; i <= n; i++){
if(f[a[i]] == minval-1) curhold++;
if(f[a[i]] >= minval){
cursum++;
if(f[a[i]] == minval && curhold - (f2[minval] - 1) >= x){
curhold -= f2[minval] - 1;
minval++;
}
}
f2[f[a[i]]]--; f[a[i]]++; f2[f[a[i]]]++;
if(i >= k){
ans = max(ans, cursum);
int p = i-k+1;
if(f[a[p]] == minval) curhold--;
if(f[a[p]] > minval || (f[a[p]] == minval && curhold < x)){
cursum--;
if(curhold < x){
minval--;
curhold += f2[minval]+1;
}
}
f2[f[a[p]]]--; f[a[p]]--; f2[f[a[p]]]++;
}
}
cout << k-ans << '\n';
}
}import sys, os
def main():
if os.path.exists("DECOR.inp"):
sys.stdin = open("DECOR.inp")
sys.stdout = open("DECOR.out", "w")
data = sys.stdin.read().split()
n, q, c = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(v) for v in data[3:3 + n]]
pos = 3 + n
out = []
for test in range(q):
k, x = int(data[pos]), int(data[pos + 1])
pos += 2
f = [0] * (n + 2)
f2 = [0] * (n + 2)
f2[0] = n
cursum = minval = 0
curhold = n
ans = 0
for i in range(1, n + 1):
v = a[i]
fv = f[v]
if fv == minval - 1:
curhold += 1
if fv >= minval:
cursum += 1
if fv == minval and curhold - (f2[minval] - 1) >= x:
curhold -= f2[minval] - 1
minval += 1
f2[fv] -= 1; f[v] = fv + 1; f2[fv + 1] += 1
if i >= k:
if cursum > ans:
ans = cursum
u = a[i - k + 1]
fu = f[u]
if fu == minval:
curhold -= 1
if fu > minval or (fu == minval and curhold < x):
cursum -= 1
if curhold < x:
minval -= 1
curhold += f2[minval] + 1
f2[fu] -= 1; f[u] = fu - 1; f2[fu - 1] += 1
out.append(str(k - ans))
print("\n".join(out))
main()
sys.stdout.flush()Đánh giá độ phức tạp của cách làm này:
- Không gian: các mảng $a, f, f2$: $O(n)$.
- Thời gian: mỗi phương án: 2 lần
memsetvà một lần trượt cửa sổ, mỗi bước $O(1)$: $O(n)$. Tổng $O(q \cdot n) = 400 \cdot 10^5 = 4 \cdot 10^7$.
- 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