Văn nghệ (Đề tự luyện HSG Tin 12 – Bài 4)
Đề bài
Văn nghệ. Dàn đèn có $20$ bóng, bóng $j$ khi sáng đóng góp $2^j$ điểm rực rỡ. Có $N$ tiết mục; khi tiết mục $i$ kết thúc, mọi bóng $j$ mà bit $j$ của $a_i$ bằng $1$ được bấm công tắc (đổi trạng thái). Chọn một dãy liên tiếp các tiết mục $l..r$ với $L \le r - l + 1 \le R$, diễn lại từ lúc mọi bóng đều tắt. Tìm độ rực rỡ (tổng điểm các bóng đang sáng) lớn nhất sau tiết mục $r$.
Dữ liệu vào: dòng đầu $N, L, R$ ($1 \le L \le R \le N \le 5 \cdot 10^5$); dòng hai $a_1, \dots, a_N$ ($0 \le a_i < 2^{20}$).
Kết quả: độ rực rỡ lớn nhất.
- Subtask 1 (20%): $N \le 3000$.
- Subtask 2 (20%): $L = 1$ và $R = N$.
- Subtask 3 (25%): $a_i < 2^8 = 256$.
- Subtask 4 (35%): không có ràng buộc gì thêm.
8 3 4
17 21 12 31 20 17 22 2126Chọn tiết mục $4, 5, 6$ ($a = 31, 20, 17$, nhị phân $11111, 10100, 10001$): sau tiết mục $6$ còn sáng các bóng $1, 3, 4$, độ rực rỡ $2 + 8 + 16 = 26$. Không trích đoạn $3$ hoặc $4$ tiết mục nào tốt hơn.
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 Văn nghệLời mở đầu
Đọc kĩ câu chuyện về bóng đèn, ta thấy ba điều quen thuộc của phép XOR (kí hiệu $\oplus$, trong C++ là ^):
- Trạng thái dàn đèn chính là một số. Bóng $j$ sáng ứng với bit $j$ bằng $1$, và độ rực rỡ $\sum 2^j$ (trên các bóng sáng) chính là giá trị của số đó. Bấm công tắc theo $a_i$ là đổi các bit có trong $a_i$, tức là phép $\oplus\, a_i$. Vậy sau trích đoạn $l..r$ (bắt đầu từ $0$), dàn đèn là $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$ và ta cần XOR của đoạn con lớn nhất, với độ dài trong $[L, R]$.
- XOR tiền tố. Đặt $p_0 = 0$, $p_i = a_1 \oplus \dots \oplus a_i$. Vì $x \oplus x = 0$ nên XOR của đoạn $l..r$ bằng $p_r \oplus p_{l-1}$ (giống tổng đoạn = hiệu hai tổng tiền tố). Đặt $j = l - 1$, điều kiện độ dài trở thành $r - R \le j \le r - L$.
- So sánh hai số theo bit cao nhất. Số nào có bit cao nhất (khác nhau) bằng $1$ thì lớn hơn — đúng như "bóng số lớn quan trọng nhất". Vì vậy khi tìm $y$ để $x \oplus y$ lớn nhất, ta tham lam từ bit $19$ xuống bit $0$: ở mỗi bit, cố chọn $y$ có bit ngược với $x$ (để bit đó của kết quả bằng $1$) nếu còn ứng viên như thế.
Đoạn $l..r$ ứng với cặp tiền tố $(j, r)$, $j = l - 1$; các $j$ hợp lệ tạo thành một cửa sổ trượt.
Ghép lại: duyệt $r$ tăng dần, giữ một tập các giá trị $p_j$ trong cửa sổ, và hỏi "phần tử nào của tập cho XOR với $p_r$ lớn nhất". Cấu trúc trả lời câu hỏi đó trong $O(20)$ là cây nhị phân (trie); để cửa sổ trượt được, cây phải xóa được giá trị — ta lưu ở mỗi nút số giá trị đi qua nó. Mình đi qua 4 cách:
Cách 1Thử mọi cặp tiền tố – O(N · (R − L + 1)) · 20%
Tính mảng $p$, rồi với mỗi $r$ từ $L$ tới $N$ thử mọi $j$ từ $\max(0, r - R)$ tới $r - L$, lấy $\max p_r \oplus p_j$. Với $N \le 3000$ chỉ khoảng $4{,}5 \cdot 10^6$ cặp. (Nếu không dùng XOR tiền tố mà tính XOR từng đoạn từ đầu thì mất $O(N^3)$ — vẫn qua được $N$ nhỏ hơn nhiều.)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, L, R;
scanf("%d %d %d", &n, &L, &R);
vector<int> p(n + 1, 0); // p[i] = a[1] ^ ... ^ a[i]
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
p[i] = p[i - 1] ^ a;
}
int best = 0;
for (int r = L; r <= n; r++) // đoạn [l, r]: XOR = p[r] ^ p[l - 1]
for (int j = max(0, r - R); j <= r - L; j++)
best = max(best, p[r] ^ p[j]);
printf("%d\n", best);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); L = int(data[1]); R = int(data[2])
p = [0] * (n + 1) # p[i] = a[1] ^ ... ^ a[i]
for i in range(1, n + 1):
p[i] = p[i - 1] ^ int(data[2 + i])
best = 0
for r in range(L, n + 1): # đoạn [l, r]: XOR = p[r] ^ p[l - 1]
x = p[r]
for j in range(max(0, r - R), r - L + 1):
if x ^ p[j] > best:
best = x ^ p[j]
print(best)
main()Cách 2Không giới hạn độ dài: cây nhị phân – O(20 · N) · 20%
Khi $L = 1$, $R = N$, mọi $j < r$ đều được phép: đây là bài kinh điển "XOR đoạn con lớn nhất". Ta xây cây nhị phân: mỗi giá trị $p_j$ được viết thành $20$ bit từ bit $19$ xuống bit $0$ và đi từ gốc xuống, bit $0$ rẽ trái, bit $1$ rẽ phải. Các giá trị có chung các bit đầu sẽ đi chung một đoạn đường.
Để tìm $y$ trong cây làm $x \oplus y$ lớn nhất: từ gốc, ở bit $b$, nếu bit $b$ của $x$ là $c$ thì ưu tiên rẽ sang nhánh $1 - c$ (bit $b$ của kết quả bằng $1$); nhánh đó không có thì đành rẽ nhánh $c$. Vì bit cao "nặng" hơn tổng tất cả các bit thấp cộng lại ($2^b > 2^{b-1} + \dots + 1$), lựa chọn tham lam này là tối ưu. Duyệt $r = 1..N$: hỏi với $p_r$ rồi mới thêm $p_r$ vào cây (ban đầu cây có sẵn $p_0 = 0$).
Mô phỏng phép hỏi: nhập một tập giá trị và $x$, xem từng bit ta giữ lại những ứng viên nào (đúng bằng các giá trị nằm trong nhánh cây đang đứng).
#include <bits/stdc++.h>
using namespace std;
const int B = 20;
int ch[2][500001 * B + 1], nodes = 1; // nút 0 là gốc
void insert(int x) {
int u = 0;
for (int b = B - 1; b >= 0; b--) {
int c = (x >> b) & 1;
if (!ch[c][u]) ch[c][u] = nodes++;
u = ch[c][u];
}
}
int query(int x) { // max x ^ y, y đã có trong cây
int u = 0, res = 0;
for (int b = B - 1; b >= 0; b--) {
int c = (x >> b) & 1;
if (ch[c ^ 1][u]) { res |= 1 << b; u = ch[c ^ 1][u]; }
else u = ch[c][u];
}
return res;
}
int main() {
int n, L, R;
scanf("%d %d %d", &n, &L, &R); // subtask 2: L = 1, R = N
int p = 0, best = 0;
insert(0); // p[0] = 0
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
p ^= a;
best = max(best, query(p)); // ghép với mọi p[j], j < i
insert(p);
}
printf("%d\n", best);
return 0;
}import sys
from array import array
B = 20
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]) # subtask 2: L = 1, R = N
size = (n + 1) * B + 1
ch0 = array('i', bytes(4 * size))
ch1 = array('i', bytes(4 * size))
nodes = 1
bits = [1 << b for b in range(B - 1, -1, -1)]
p = 0; best = 0
for i in range(n + 1):
if i > 0:
p ^= int(data[2 + i])
u = 0; res = 0 # truy vấn max p ^ y
for m in bits:
if p & m:
w = ch0[u]
if w:
res |= m; u = w
else:
u = ch1[u]
else:
w = ch1[u]
if w:
res |= m; u = w
else:
u = ch0[u]
if res > best:
best = res
u = 0 # thêm p vào cây
for m in bits:
if p & m:
w = ch1[u]
if not w:
w = nodes; ch1[u] = w; nodes += 1
else:
w = ch0[u]
if not w:
w = nodes; ch0[u] = w; nodes += 1
u = w
print(best)
main()Cách 3Giá trị nhỏ: đếm theo giá trị – O(256 · N) · 25%
Khi $a_i < 256$ thì mọi $p_j < 256$. Thay cho cây, ta giữ mảng $c[v]$ = số chỉ số $j$ trong cửa sổ có $p_j = v$. Khi $r$ tăng: $c[p_{r-L}]$ tăng $1$, $c[p_{r-R-1}]$ giảm $1$ (nếu $r - R - 1 \ge 0$); rồi thử cả $256$ giá trị $v$ có $c[v] > 0$. Cách này đã có đủ ý "cửa sổ trượt có xóa" — chỉ thiếu một cấu trúc hỏi nhanh.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, L, R;
scanf("%d %d %d", &n, &L, &R);
vector<int> p(n + 1, 0);
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
p[i] = p[i - 1] ^ a;
}
// subtask 3: a[i] < 256 nên p[i] < 256; c[v] = số chỉ số j trong cửa sổ có p[j] = v
vector<int> c(256, 0);
int best = 0;
for (int r = L; r <= n; r++) {
c[p[r - L]]++;
if (r - R - 1 >= 0) c[p[r - R - 1]]--;
for (int v = 0; v < 256; v++)
if (c[v] > 0) best = max(best, p[r] ^ v);
}
printf("%d\n", best);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); L = int(data[1]); R = int(data[2])
p = [0] * (n + 1)
for i in range(1, n + 1):
p[i] = p[i - 1] ^ int(data[2 + i])
# subtask 3: p[i] < 256; c[v] = số chỉ số j trong cửa sổ có p[j] = v
c = [0] * 256
best = 0
for r in range(L, n + 1):
c[p[r - L]] += 1
if r - R - 1 >= 0:
c[p[r - R - 1]] -= 1
x = p[r]
for v in range(256):
if c[v] and x ^ v > best:
best = x ^ v
print(best)
main()Cách 4Cây nhị phân có đếm trên cửa sổ trượt – O(20 · N) · 100%
Ghép Cách 2 và Cách 3: vẫn là cây nhị phân, nhưng mỗi nút lưu cnt = số giá trị trong cửa sổ đi qua nút đó.
- Thêm $x$: đi theo các bit của $x$ (tạo nút nếu chưa có), cộng
cntcác nút trên đường đi thêm $1$. - Xóa $x$: đi đúng đường đó, trừ
cntđi $1$. Nút không bị xóa thật, chỉ "rỗng" khicnt = 0. - Hỏi với $x$: như Cách 2, nhưng chỉ rẽ sang nhánh ngược bit khi nhánh đó tồn tại và
cnt > 0.
Với mỗi $r$ từ $L$ tới $N$: thêm $p_{r-L}$ (vừa đủ độ dài $L$), xóa $p_{r-R-1}$ nếu $r - R - 1 \ge 0$ (đoạn sẽ dài $R + 1$), rồi hỏi với $p_r$. Cây có tối đa $20 \cdot N + 1$ nút.
- Lệch một ở cửa sổ: đoạn $l..r$ ứng với $j = l - 1$, nên phải xóa $p_{r-R-1}$, không phải $p_{r-R}$ (xóa sớm làm mất các đoạn dài đúng $R$).
- Quên xóa (bỏ qua $R$): chỉ đúng khi $R = N$.
- Đánh dấu có/không thay vì đếm: nhiều giá trị đi chung một nút; xóa một giá trị mà đặt nút về "không có" sẽ làm "biến mất" cả những giá trị khác cùng nhánh.
Ví dụ của đề có đoạn tốt nhất dài $3 < R$ và bỏ $R$ thì đáp án không đổi, nên cả ba lỗi đều vẫn in $26$!
Vì các $p_j$ được thêm theo thứ tự $j$ tăng, có thể lưu ở mỗi nút chỉ số $j$ lớn nhất đi qua nó; khi hỏi chỉ rẽ vào nhánh có chỉ số lớn nhất $\ge r - R$. Cách này cũng $O(20 \cdot N)$.
Mô phỏng: xem cửa sổ trượt, tập giá trị đang có trong cây và kết quả tốt nhất với từng $r$.
#include <bits/stdc++.h>
using namespace std;
const int B = 20; // 20 bóng đèn: bit 19 .. bit 0
int ch[2][500001 * B + 1], cnt[500001 * B + 1], nodes = 1; // nút 0 là gốc
// thêm (d = 1) hoặc xóa (d = -1) giá trị x khỏi cây nhị phân
void update(int x, int d) {
int u = 0;
for (int b = B - 1; b >= 0; b--) {
int c = (x >> b) & 1;
if (!ch[c][u]) ch[c][u] = nodes++;
u = ch[c][u];
cnt[u] += d;
}
}
// giá trị lớn nhất của x XOR y với y đang có trong cây (cây khác rỗng)
int query(int x) {
int u = 0, res = 0;
for (int b = B - 1; b >= 0; b--) {
int c = (x >> b) & 1;
int v = ch[c ^ 1][u];
if (v && cnt[v] > 0) { res |= 1 << b; u = v; } // đi nhánh ngược bit để bit b của XOR bằng 1
else u = ch[c][u];
}
return res;
}
int main() {
int n, L, R;
scanf("%d %d %d", &n, &L, &R);
vector<int> p(n + 1, 0); // p[i] = a[1] ^ ... ^ a[i]
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
p[i] = p[i - 1] ^ a;
}
// đoạn [l, r] có XOR = p[r] ^ p[l - 1]; độ dài trong [L, R] <=> r - R <= l - 1 <= r - L
int best = 0;
for (int r = L; r <= n; r++) {
update(p[r - L], 1); // l - 1 = r - L vừa được phép
if (r - R - 1 >= 0) update(p[r - R - 1], -1); // l - 1 = r - R - 1 hết được phép
best = max(best, query(p[r]));
}
printf("%d\n", best);
return 0;
}import sys
from array import array
B = 20 # 20 bóng đèn: bit 19 .. bit 0
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); L = int(data[1]); R = int(data[2])
p = [0] * (n + 1) # p[i] = a[1] ^ ... ^ a[i]
x = 0
for i in range(1, n + 1):
x ^= int(data[2 + i])
p[i] = x
size = (n - L + 2) * B + 1
ch0 = array('i', bytes(4 * size))
ch1 = array('i', bytes(4 * size))
cnt = array('i', bytes(4 * size))
nodes = 1
bits = [1 << b for b in range(B - 1, -1, -1)]
best = 0
for r in range(L, n + 1):
# thêm p[r - L]
v = p[r - L]; u = 0
for m in bits:
if v & m:
w = ch1[u]
if not w:
w = nodes; ch1[u] = w; nodes += 1
else:
w = ch0[u]
if not w:
w = nodes; ch0[u] = w; nodes += 1
u = w
cnt[u] += 1
# xóa p[r - R - 1]
if r - R - 1 >= 0:
v = p[r - R - 1]; u = 0
for m in bits:
u = ch1[u] if v & m else ch0[u]
cnt[u] -= 1
# truy vấn: max p[r] ^ y
v = p[r]; u = 0; res = 0
for m in bits:
if v & m:
w = ch0[u]
if w and cnt[w]:
res |= m; u = w
else:
u = ch1[u]
else:
w = ch1[u]
if w and cnt[w]:
res |= m; u = w
else:
u = ch0[u]
if res > best:
best = res
print(best)
main()Ba mảng của cây dùng array('i') (mỗi ô 4 byte) thay vì list để tiết kiệm bộ nhớ (hơn $10^7$ nút); vòng lặp theo bit dùng sẵn danh sách mặt nạ 1 << b. Nộp bằng PyPy 3.
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 cặp (j, r) | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – trie không xóa (chỉ đúng khi L = 1, R = N) | 0/9 | Đúng | 0/7 | 0/9 | 20 |
| Cách 3 – đếm theo giá trị (chỉ đúng khi a < 256) | Lỗi | Lỗi | Đúng | Lỗi | 25 |
| Cách 4 – trie có đếm + cửa sổ trượt (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: quên xóa (bỏ qua R) | 0/9 | Đúng | 0/7 | 0/9 | 20 |
| Sai: xóa $p_{r-R}$ thay vì $p_{r-R-1}$ | 2/9 | Đúng | 1/7 | 1/9 | 31,90 |
| Sai: đánh dấu có/không thay vì đếm | 4/9 | Đúng | 2/7 | 2/9 | 43,81 |
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: 31 test (subtask 1: 9 test, subtask 2: 6 test, subtask 3: 7 test, subtask 4: 9 test), chấm kiểu "đúng test nào được điểm test đó". Subtask 2–4 có $N \approx 5 \cdot 10^5$ và cửa sổ rất rộng (Cách 1 cần tới hàng chục tỉ phép tính). Dữ liệu được dựng có chủ đích: hầu hết tiền tố chỉ khác nhau ở các bit thấp, một vài "tiết mục đặc biệt" đổi các bit cao, và cặp tốt nhất được đặt đúng ở khoảng cách $R$, $R + 1$ hoặc $L$ — nên lệch một ở cửa sổ hay quên xóa đều bị phát hiện; có test trích đoạn phải dài đúng $L = R$, test $L = R = 1$, test mọi đoạn có XOR bằng $0$. Lời giải chuẩn C++ chạy dưới 0,4 giây; bản Python 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