Quạt nước (Đề tự luyện HSG Tin 12 – Bài 3)
Đề bài
Quạt nước. $N$ máy quạt xếp vòng tròn, trạng thái cho bởi xâu $s$ ($\texttt{1}$ = chạy, $\texttt{0}$ = tắt). Gạt cầu dao $i$ thì $K$ máy liên tiếp $i, i+1, \ldots, i+K-1$ (tính vòng) đảo trạng thái. Tìm số lần gạt ít nhất để mọi máy cùng chạy, hoặc $-1$ nếu không thể.
Dữ liệu vào: dòng đầu $N, K$ ($1 \le K \le N \le 5 \cdot 10^5$); dòng hai là xâu $s$.
Kết quả: số lần gạt ít nhất hoặc $-1$.
- Subtask 1 (20%): $N \le 16$.
- Subtask 2 (30%): $K \le 8$ và $N \le 5 \cdot 10^4$.
- Subtask 3 (50%): không có ràng buộc gì thêm.
10 3
01010000114Gạt các cầu dao 1, 2, 3, 6: máy 1, 3, 5 bị đảo lẻ lần (tắt → chạy), máy 2, 4 bị đảo chẵn lần (vẫn chạy), máy 6, 7, 8 bị đảo một lần, máy 9, 10 giữ nguyên. Không thể dùng ít hơn 4 lần.
8 4
01011011-1Không có cách gạt nào làm cả 8 máy cùng chạy.
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 Quạt nướcLời mở đầu
Bài này trông như một trò chơi "bật tắt đèn", và cách làm quen thuộc với dãy thẳng là tham lam từ trái sang phải. Nhưng các máy xếp vòng tròn, và chính cái vòng tròn đó sinh ra những điều rất thú vị. Mình đi từng bước nhé (đánh số máy và cầu dao từ $0$ cho gọn).
Nhận xét 1 – chỉ cần biết gạt hay không. Thứ tự gạt không ảnh hưởng kết quả (mỗi máy chỉ quan tâm bị đảo chẵn hay lẻ lần), và gạt một cầu dao hai lần thì như không gạt. Vậy ta chỉ chọn một tập cầu dao: $x_i = 1$ nếu gạt cầu dao $i$. Gọi $b_i = 1$ nếu máy $i$ đang tắt (cần đảo lẻ lần). Máy $i$ chịu tác động của các cầu dao $i-K+1, \ldots, i$ (mod $N$), nên điều kiện là
$$x_{i-K+1} \oplus x_{i-K+2} \oplus \cdots \oplus x_i = b_i \quad \text{với mọi } i,$$
trong đó $\oplus$ là phép XOR (cộng theo modulo 2). Ta cần nghiệm có ít số $1$ nhất.
Nhận xét 2 – XOR hai phương trình kề nhau. Phương trình của máy $i$ và máy $i-1$ có chung $K-1$ ẩn, chỉ khác $x_i$ (có ở máy $i$) và $x_{i-K}$ (có ở máy $i-1$). XOR hai phương trình:
$$x_i \oplus x_{i-K} = b_i \oplus b_{i-1} =: d_i \pmod N.$$
Ngược lại, nếu đủ $N$ phương trình "hiệu" này đúng và phương trình của một máy (chẳng hạn máy $0$) đúng thì mọi phương trình gốc đều đúng (cộng dồn dần từ máy $0$).
Hình 1. Quan hệ $x_i \oplus x_{i-K} = d_i$ nối các vị trí thành $g = \gcd(N, K)$ vòng.
Nhận xét 3 – các vòng theo ƯCLN. Đi từ $j$ theo bước $+K$ (mod $N$), ta đi qua đúng các vị trí có cùng số dư với $j$ khi chia cho $g = \gcd(N, K)$, rồi quay về $j$ sau $N/g$ bước. Trên mỗi vòng, chọn $x_j$ thì các $x$ còn lại bị suy ra. Khi quay về $j$, nếu giá trị suy ra khác $x_j$ (XOR các $d$ trên vòng bằng 1) thì vô nghiệm. Mỗi vòng chỉ có đúng hai lựa chọn: "gốc" ($x_j = 0$) với $a_j$ cầu dao, hoặc "đảo cả vòng" với $N/g - a_j$ cầu dao.
Nhận xét 4 – đừng quên phương trình còn lại! Máy $0$ chịu $K$ cầu dao liên tiếp, gồm đúng $t = K/g$ cầu dao của mỗi vòng. Đảo một vòng thì vế trái của máy $0$ đổi $t$ lần. Vì thế:
- $t$ chẵn: lựa chọn các vòng không ảnh hưởng máy $0$. Nếu máy $0$ sai thì $-1$, còn không thì mỗi vòng chọn rẻ hơn.
- $t$ lẻ: số vòng bị đảo phải có chẵn lẻ cố định. Tham lam chọn rẻ hơn ở từng vòng; nếu sai chẵn lẻ thì đổi lựa chọn ở vòng có $|N/g - 2a_j|$ nhỏ nhất.
Cách 1Thử mọi tập cầu dao – O(2^N · N · K) · 20%
Theo Nhận xét 1, chỉ cần thử mọi tập con các cầu dao ($2^N$ tập), mô phỏng việc đảo trạng thái và kiểm tra mọi máy chạy. Với $N \le 16$ là khoảng $65\,536$ tập.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
string s;
cin >> n >> k >> s;
int ans = -1;
for (int mask = 0; mask < (1 << n); mask++) { // thu moi tap cau dao
string cur = s;
for (int i = 0; i < n; i++)
if (mask >> i & 1)
for (int j = 0; j < k; j++) {
char &c = cur[(i + j) % n];
c = (c == '0') ? '1' : '0';
}
if (cur == string(n, '1')) {
int cnt = __builtin_popcount(mask);
if (ans == -1 || cnt < ans) ans = cnt;
}
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1]); s = data[2]
start = 0
for i in range(n):
if s[i] == '1':
start |= 1 << i
full = (1 << n) - 1
T = [0] * n # T[i]: cac may bi cau dao i dao trang thai
for i in range(n):
for j in range(k):
T[i] |= 1 << ((i + j) % n)
ans = -1
for mask in range(1 << n): # thu moi tap cau dao
cur = start
m = mask; i = 0
while m:
if m & 1:
cur ^= T[i]
m >>= 1; i += 1
if cur == full:
c = bin(mask).count("1")
if ans == -1 or c < ans:
ans = c
print(ans)
main()Cách 2Đoán K − 1 cầu dao đầu, suy ra phần còn lại – O(2^(K−1) · N) · 50%
Nếu là dãy thẳng, ta tham lam: xét máy từ trái sang, máy nào sai thì gạt cầu dao bắt đầu tại nó. Trên vòng tròn, cái khó là các cầu dao $0..K-2$ còn tác động lên những máy "đầu dãy" qua đường vòng. Nhưng nếu đã đoán trước $x_0, \ldots, x_{K-2}$ thì với $i = K-1, K, \ldots, N-1$: máy $i$ chịu các cầu dao $i-K+1..i$, trong đó chỉ $x_i$ chưa biết, nên
$$x_i = b_i \oplus x_{i-K+1} \oplus \cdots \oplus x_{i-1}$$
(giữ XOR của cửa sổ trượt để tính $O(1)$). Cuối cùng kiểm tra $K-1$ máy $0..K-2$ – chúng còn chịu các cầu dao vòng $N-K+1..N-1$. Thử đủ $2^{K-1}$ cách đoán, lấy nghiệm ít cầu dao nhất. Với $K \le 8$ là $128 \cdot 5 \cdot 10^4 \approx 6{,}4 \cdot 10^6$ phép.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
string s;
cin >> n >> k >> s;
vector<int> b(n), x(n);
for (int i = 0; i < n; i++) b[i] = (s[i] == '0'); // b[i] = 1: may i can doi trang thai
int ans = -1;
for (int mask = 0; mask < (1 << (k - 1)); mask++) { // doan k-1 cau dao dau tien 0..k-2
for (int i = 0; i < k - 1; i++) x[i] = mask >> i & 1;
int w = 0; // w = x[i-k+1] ^ ... ^ x[i-1]
for (int i = 0; i < k - 1; i++) w ^= x[i];
for (int i = k - 1; i < n; i++) {
x[i] = b[i] ^ w; // may i: cau dao i la cau dao cuoi cung tac dong
w ^= x[i];
w ^= x[i - k + 1]; // truot cua so sang i+1
}
bool ok = true; // kiem tra may 0..k-2 (bi cac cau dao vong tac dong)
for (int i = 0; i < k - 1 && ok; i++) {
int c = 0;
for (int j = 0; j < k; j++) c ^= x[((i - j) % n + n) % n];
if (c != b[i]) ok = false;
}
if (!ok) continue;
int cnt = 0;
for (int i = 0; i < n; i++) cnt += x[i];
if (ans == -1 || cnt < ans) ans = cnt;
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1]); s = data[2]
b = [1 - (c - 48) for c in s] # b[i] = 1: may i can doi trang thai
ans = -1
for mask in range(1 << (k - 1)): # doan k-1 cau dao dau tien 0..k-2
x = [(mask >> i) & 1 for i in range(k - 1)] + [0] * (n - k + 1)
w = 0 # w = x[i-k+1] ^ ... ^ x[i-1]
for i in range(k - 1):
w ^= x[i]
for i in range(k - 1, n):
xi = b[i] ^ w # may i: cau dao i la cau dao cuoi cung tac dong
x[i] = xi
w ^= xi ^ x[i - k + 1] # truot cua so sang i+1
ok = True # kiem tra may 0..k-2 (bi cac cau dao vong tac dong)
for i in range(k - 1):
c = 0
for j in range(k):
c ^= x[(i - j) % n]
if c != b[i]:
ok = False
break
if ok:
cnt = sum(x)
if ans == -1 or cnt < ans:
ans = cnt
print(ans)
main()Cách 3Hiệu kề nhau + vòng theo ƯCLN + tham lam chẵn lẻ – O(N) · 100%
Ghép bốn nhận xét lại:
- Tính $b_i$ và $d_i = b_i \oplus b_{i-1}$.
- Với mỗi vòng $j = 0..g-1$: gán $x_j = 0$, đi theo bước $+K$ suy ra các $x$; quay về $j$ mà mâu thuẫn thì in $-1$. Đếm $a_j$.
- Tính vế trái của máy $0$ với nghiệm gốc: $s_0 = x_0 \oplus x_{N-K+1} \oplus \cdots \oplus x_{N-1}$, và $need = s_0 \oplus b_0$ (cần đổi hay không).
- Mỗi vòng chọn $\min(a_j, N/g - a_j)$, đếm số vòng bị đảo; xử lý chẵn lẻ theo $t = K/g$ như Nhận xét 4.
Chạy tay $N = 6$, $K = 2$, $s = \texttt{000000}$: $b = [1,1,1,1,1,1]$, $d = [0,0,0,0,0,0]$, $g = 2$, mỗi vòng dài $3$, $t = 1$. Hai vòng $\{0, 2, 4\}$ và $\{1, 3, 5\}$ đều cho $x = 0$, $a_0 = a_1 = 0$. $s_0 = x_0 \oplus x_5 = 0$, $need = 0 \oplus 1 = 1$: phải đảo một số lẻ vòng. Tham lam không đảo vòng nào (chi phí $0$) – sai chẵn lẻ, nên đổi lựa chọn ở vòng rẻ nhất: $|3 - 0| = 3$. Đáp án $0 + 3 = 3$ ✓ (đảo vòng $\{0, 2, 4\}$ = gạt cầu dao 1, 3, 5).
Các bạn nhập $K$ và trạng thái để xem từng vòng được lan truyền:
- Tham lam như dãy thẳng (bỏ qua các cầu dao "vòng qua" máy $N$).
- Nghĩ rằng chỉ có một vòng (đúng khi $\gcd(N, K) = 1$), nên chỉ thử $x_0 = 0$ hoặc $1$.
- Quên phương trình của máy $0$: các phương trình hiệu chưa đủ, chúng chỉ "nối" các máy với nhau.
- Khi $t = K/g$ chẵn, phải in $-1$ nếu máy $0$ sai – không có cách đổi chẵn lẻ nào cứu được.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
string s;
cin >> n >> k >> s;
vector<int> b(n), d(n), x(n, 0);
for (int i = 0; i < n; i++) b[i] = (s[i] == '0'); // b[i] = 1: may i can doi trang thai
for (int i = 0; i < n; i++) d[i] = b[i] ^ b[(i - 1 + n) % n];
// x[i] ^ x[(i-k) mod n] = d[i] => chia cac vi tri thanh g vong: j, j+k, j+2k, ... (mod n)
int g = __gcd(n, k), len = n / g, t = k / g;
vector<int> a(g, 0); // a[j]: so cau dao gat o vong j (khi x[j] = 0)
for (int j = 0; j < g; j++) {
int cur = j;
for (int step = 1; step < len; step++) {
int nxt = (cur + k) % n;
x[nxt] = x[cur] ^ d[nxt];
cur = nxt;
}
if ((x[cur] ^ d[j]) != x[j]) { cout << -1 << "\n"; return 0; } // vong mau thuan
for (int i = j; i < n; i += g) a[j] += x[i]; // vong j = cac vi tri dong du j (mod g)
}
int s0 = x[0]; // may 0 chiu tac dong cua cau dao n-k+1..n-1 va 0
for (int i = n - k + 1; i < n; i++) s0 ^= x[i];
int need = s0 ^ b[0]; // dao 1 vong lam s0 doi t lan
long long ans = 0;
int flips = 0, fix = INT_MAX;
for (int j = 0; j < g; j++) {
if (len - a[j] < a[j]) { ans += len - a[j]; flips++; } // dao vong j thi so lan gat = len - a[j]
else ans += a[j];
fix = min(fix, abs(len - 2 * a[j]));
}
if (t % 2 == 0) {
if (need) { cout << -1 << "\n"; return 0; }
} else if (flips % 2 != need) {
ans += fix; // doi lua chon cua vong ton it nhat
}
cout << ans << "\n";
return 0;
}import sys
from math import gcd
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
s = data[2]
b = [1 - (c - 48) for c in s] # b[i] = 1: may i can doi trang thai
d = [b[i] ^ b[i - 1] for i in range(n)] # b[-1] = b[n-1]
g = gcd(n, k); ln = n // g; t = k // g
x = [0] * n
a = [0] * g
for j in range(g): # vong j: j, j+k, j+2k, ... (mod n)
cur = j
xc = 0
for _ in range(ln - 1):
cur += k
if cur >= n:
cur -= n
xc ^= d[cur]
x[cur] = xc
if xc ^ d[j]: # vong mau thuan
sys.stdout.write("-1\n")
return
a[j] = sum(x[j::g])
s0 = x[0] # may 0 chiu tac dong cua cau dao n-k+1..n-1 va 0
for i in range(n - k + 1, n):
s0 ^= x[i]
need = s0 ^ b[0]
ans = 0; flips = 0; fix = n + 1
for j in range(g):
aj = a[j]
if ln - aj < aj:
ans += ln - aj; flips += 1
else:
ans += aj
f = abs(ln - 2 * aj)
if f < fix:
fix = f
if t % 2 == 0:
if need:
sys.stdout.write("-1\n")
return
elif flips % 2 != need:
ans += fix
sys.stdout.write(str(ans) + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 33 test: 12 test subtask 1 ($N \le 16$), 10 test subtask 2 ($K \le 8$, $N \approx 5 \cdot 10^4$), 11 test subtask 3 ($N \approx 5 \cdot 10^5$, $K$ từ $1000$ trở lên). Số vòng $g$ rất đa dạng ($1, 2, 4, 32, \ldots, 2{,}5 \cdot 10^5$), có cả $K/g$ chẵn lẫn lẻ; phần lớn test có nghiệm cần "đổi chẵn lẻ" ở một vòng, và có các test vô nghiệm vì mâu thuẫn trong vòng hoặc vì chẵn lẻ.
| Cách làm | Sub 1 (20%) | Sub 2 (30%) | Sub 3 (50%) | Điểm |
|---|---|---|---|---|
| Cách 1 – thử mọi tập cầu dao | Đúng | TLE/WA | TLE/WA | 20 |
| Cách 2 – đoán K − 1 cầu dao đầu | Đúng | Đúng | TLE/WA | 50 |
| Cách 3 – vòng theo ƯCLN + chẵn lẻ | Đúng | Đúng | Đúng | 100 |
| Sai 1 – tham lam như dãy thẳng | 8/12 test | 5/10 test | 3/11 test | ≈ 42 |
| Sai 2 – quên phương trình của máy 0 (chẵn lẻ) | 9/12 test | 5/10 test | 6/11 test | ≈ 57 |
| Sai 3 – nghĩ chỉ có một vòng | 6/12 test | 4/10 test | 2/11 test | ≈ 31 |
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: Cách 1 đúng 12/12 test subtask 1, ở các subtask sau thì hoặc chạy quá thời gian, hoặc (vì 1 << n bị tràn khi $n$ lớn) chỉ thử được một phần và in sai; Cách 2 đúng hết hai subtask đầu và trượt cả 11 test subtask 3; Cách 3 đúng 33/33 test, test lâu nhất khoảng 0,02 giây. Các lời giải sai "ăn may" ở hai ví dụ, ở các test vô nghiệm vì mâu thuẫn trong vòng, ở các test có $\gcd(N, K) = 1$ và ở những test mà tham lam từng vòng tình cờ đã đúng chẵn lẻ.
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