Chép vè (Đề tự luyện HSG Tin 12 – Bài 2)
Đề bài
Chép vè. Cho xâu $S$ gồm $N$ chữ cái thường. Với bài vè $P = S_1 S_2 \ldots S_L$ ($1 \le L \le N$), ta cần chia $S$ thành các đoạn liên tiếp, mỗi đoạn là một đoạn đầu khác rỗng của $P$ (tức là bằng $S_1 \ldots S_k$ với $1 \le k \le L$) – mỗi đoạn là một lượt bé Na chép bài vè từ đầu, có thể bỏ dở. Tìm $L$ nhỏ nhất để chia được.
Dữ liệu vào: dòng đầu $N$ ($1 \le N \le 2 \cdot 10^5$); dòng hai là xâu $S$.
Kết quả: độ dài nhỏ nhất $L$.
- Subtask 1 (20%): $N \le 100$.
- Subtask 2 (30%): $N \le 3000$.
- Subtask 3 (50%): không có ràng buộc gì thêm.
15
aaabaaabaaabaaa4Với $P = \texttt{aaab}$: $S = \texttt{aaab} \mid \texttt{aaab} \mid \texttt{aaab} \mid \texttt{aaa}$. Với $L \le 3$ bài vè không chứa chữ b nên không chia được.
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 Chép vèLời mở đầu
Ví dụ của đề trông như bài "tìm chu kỳ của xâu": $\texttt{aaab}$ lặp lại 3 lần rồi bỏ dở. Nhưng đừng vội! Bé Na có thể bỏ dở ở bất kỳ lượt nào, kể cả các lượt ở giữa. Chẳng hạn với $S = \texttt{aabaaab}$, chu kỳ nhỏ nhất của $S$ là $4$, nhưng bài vè chỉ cần dài $3$: $\texttt{aab} \mid \texttt{a} \mid \texttt{aab}$ (lượt thứ hai Na chỉ chép được chữ đầu tiên).
Nhận xét 1 – khi nào một đoạn là "đoạn đầu của bài vè"? Đoạn $S[i..i+len)$ (đếm từ $0$) bằng đoạn đầu dài $len$ của bài vè khi và chỉ khi $len \le L$ và $S[i..i+len) = S[0..len)$. Gọi $z_i$ là độ dài đoạn chung dài nhất của $S$ và $S[i..]$ (mảng Z của xâu, $z_0 = N$). Khi đó điều kiện trở thành gọn gàng:
$$S[i..i+len) \text{ là đoạn đầu của } P \iff 1 \le len \le \min(z_i, L).$$
Nghĩa là: đang đứng ở vị trí $i$ (đã chia xong $S[0..i)$), ta được phép "nhảy" tới bất kỳ vị trí nào trong $i+1, i+2, \ldots, i + \min(z_i, L)$. Cần nhảy từ $0$ tới đúng $N$.
Hình 1. Mỗi bước nhảy là một lượt chép. Đường xanh $0 \to 3 \to 4 \to 7$ ứng với cách chia $\texttt{aab} \mid \texttt{a} \mid \texttt{aab}$.
b – kẹt, trong khi nhảy ngắn ($3 \to 4$) lại đi tiếp được. Ví dụ của đề thì tham lam vẫn ra đúng $4$, nên các bạn phải tự cẩn thận.Nhận xét 2 – $L$ càng lớn càng dễ chia. Tăng $L$ thì mọi $\min(z_i, L)$ đều không giảm, các bước nhảy cũ vẫn còn nguyên. Vậy nếu $L$ chia được thì $L + 1$ cũng chia được – đáp án có thể chặt nhị phân.
Cách 1Thử từng L, quy hoạch động chia xâu – O(N⁴) · 20%
Thử $L = 1, 2, \ldots$; với mỗi $L$ làm QHĐ: $f[i]$ = có chia được $S[0..i)$ hay không. $f[0]$ đúng; nếu $f[i]$ đúng thì với mỗi $len = 1..L$, nếu s.substr(i, len) == P.substr(0, len) thì $f[i + len]$ đúng. $L$ đầu tiên có $f[N]$ đúng là đáp án. Mỗi $L$ tốn $O(N \cdot L^2)$ (so sánh xâu con mất $O(len)$), cả bài tới $O(N^4)$ – vẫn ổn khi $N \le 100$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
for (int L = 1; L <= n; L++) { // thu bai ve dai L
string P = s.substr(0, L);
vector<bool> f(n + 1, false); // f[i]: chia duoc S[0..i)
f[0] = true;
for (int i = 0; i < n; i++) {
if (!f[i]) continue;
for (int len = 1; len <= L && i + len <= n; len++)
if (s.substr(i, len) == P.substr(0, len)) f[i + len] = true;
}
if (f[n]) { cout << L << "\n"; return 0; }
}
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0]); s = data[1]
for L in range(1, n + 1): # thu bai ve dai L
P = s[:L]
f = [False] * (n + 1) # f[i]: chia duoc S[0..i)
f[0] = True
for i in range(n):
if not f[i]:
continue
for ln in range(1, min(L, n - i) + 1):
if s[i:i + ln] == P[:ln]:
f[i + ln] = True
if f[n]:
print(L)
return
main()Cách 2QHĐ "đoạn dài nhất nhỏ nhất" – O(N²) · 50%
Thay vì thử từng $L$, ta hỏi thẳng: chia $S[0..i)$ thành các đoạn đầu của $S$ thì đoạn dài nhất ít nhất phải dài bao nhiêu? Gọi đó là $best[i]$, $best[0] = 0$. Đáp án chính là $best[N]$ (bài vè phải dài ít nhất bằng đoạn dài nhất, và dài đúng chừng đó là đủ).
Từ vị trí $i$, đoạn $S[i..i+len)$ là đoạn đầu của $S$ khi các ký tự khớp liên tiếp: $S[i] = S[0], S[i+1] = S[1], \ldots$ Ta tăng $len$ dần, dừng ngay khi gặp ký tự không khớp, và cập nhật
$$best[i + len] = \min\big(best[i + len],\ \max(best[i], len)\big).$$
Chạy tay với $S = \texttt{aabaaab}$:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| S[i] | a | a | b | a | a | a | b | – |
| best[i] | 0 | 1 | 1 | 3 | 3 | 3 | 3 | 3 |
Ví dụ $best[7]$: từ $i = 4$ ($best = 3$) đoạn $\texttt{aab}$ khớp với $\texttt{aab}$ nên $best[7] \le \max(3, 3) = 3$. Còn $best[3] = 3$ vì chữ b ở vị trí $2$ chỉ nằm trong được đoạn bắt đầu từ $0$.
Mỗi vị trí $i$ duyệt tối đa $z_i + 1$ ký tự, tổng $O(N^2)$ trong trường hợp xấu (ví dụ $S = \texttt{aaa\ldots ab}$) – đủ nhanh với $N \le 3000$, nhưng quá chậm với $N = 2 \cdot 10^5$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
const int INF = INT_MAX;
vector<int> best(n + 1, INF); // best[i]: doan dai nhat nho nhat co the khi chia S[0..i)
best[0] = 0;
for (int i = 0; i < n; i++) {
if (best[i] == INF) continue;
// S[i..i+len) trung doan dau S[0..len) khi cac ky tu khop lien tiep
for (int len = 1; i + len <= n && s[i + len - 1] == s[len - 1]; len++)
best[i + len] = min(best[i + len], max(best[i], len));
}
cout << best[n] << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0]); s = data[1]
INF = n + 1
best = [INF] * (n + 1) # best[i]: doan dai nhat nho nhat co the khi chia S[0..i)
best[0] = 0
for i in range(n):
b = best[i]
if b == INF:
continue
ln = 1
# S[i..i+len) trung doan dau S[0..len) khi cac ky tu khop lien tiep
while i + ln <= n and s[i + ln - 1] == s[ln - 1]:
c = b if b > ln else ln
if c < best[i + ln]:
best[i + ln] = c
ln += 1
print(best[n])
main()Cách 3Hàm Z + nhảy xa + chặt nhị phân – O(N log N) · 100%
Ghép ba mảnh lại:
- Hàm Z tính mọi $z_i$ trong $O(N)$ (thuật toán "hộp Z" $[l, r)$ quen thuộc: nếu $i$ nằm trong hộp thì $z_i$ ít nhất là $\min(r - i, z_{i-l})$, rồi so tiếp từng ký tự; mỗi lần so trúng thì $r$ tăng nên tổng chi phí tuyến tính).
- Kiểm tra một $L$ trong $O(N)$ – đây là bài "nhảy xa": tập các vị trí tới được luôn là một đoạn liền $[0..R]$ (vì từ $i$ nhảy được tới mọi vị trí $i+1..far$). Duyệt $i = 0, 1, \ldots$ chừng nào $i \le R$, cập nhật $R = \max(R, i + \min(z_i, L))$. Chia được khi $R \ge N$. Không cần biết đi đường nào!
- Chặt nhị phân $L$ trong $[1, N]$ nhờ Nhận xét 2 ($L = N$ luôn chia được: cả xâu là một đoạn).
Các bạn nhập xâu để xem mảng Z và quá trình chặt nhị phân (ô xanh là các vị trí tới được với $L$ đang thử):
- Tham lam "luôn chép đoạn dài nhất" (kể cả có chặt nhị phân) – sai như Hình 1.
- Nghĩ đáp án là chu kỳ nhỏ nhất của $S$ – chỉ đúng khi các lượt bỏ dở nằm ở cuối.
- Thử $L = 1, 2, 3, \ldots$ tăng dần với phép kiểm tra $O(N)$: đúng nhưng $O(N \cdot \text{đáp án})$, đáp án có thể tới $N$.
- Tính mảng Z "ngây thơ" (so từng ký tự từ đầu): $O(N^2)$ với xâu kiểu $\texttt{aaa\ldots ab}$.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> z;
// Co chia duoc S thanh cac doan, moi doan la doan dau dai <= L cua S khong?
bool ok(int L) {
int R = 0; // cac vi tri 0..R deu "toi duoc"
for (int i = 0; i <= R && i < n; i++) {
int far = i + min(z[i], L); // tu i co the nhay toi i+1 .. far
if (far > R) R = far;
}
return R >= n;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
string s;
cin >> n >> s;
z.assign(n, 0);
z[0] = n;
for (int i = 1, l = 0, r = 0; i < n; i++) { // ham Z: z[i] = LCP(S, S[i..])
if (i < r) z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
int lo = 1, hi = n; // ok(n) luon dung
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ok(mid)) hi = mid; else lo = mid + 1;
}
cout << lo << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s = data[1]
z = [0] * n
z[0] = n
l = r = 0
for i in range(1, n): # ham Z: z[i] = LCP(S, S[i..])
k = 0
if i < r:
k = z[i - l]
if r - i < k:
k = r - i
while i + k < n and s[k] == s[i + k]:
k += 1
z[i] = k
if i + k > r:
l = i; r = i + k
e = [i + z[i] for i in range(n)] # tu i nhay xa nhat toi i + z[i]
def ok(L):
R = 0
i = 0
while i <= R:
if i >= n:
return True
far = e[i]
if far > i + L:
far = i + L
if far > R:
R = far
i += 1
return R >= n
lo, hi = 1, n
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
sys.stdout.write(str(lo) + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 29 test: 10 test subtask 1 ($N \le 100$), 9 test subtask 2 ($N \approx 3000$), 10 test subtask 3 ($N \approx 2 \cdot 10^5$). Các test lớn có dạng: bài vè gốc gồm một khúc rất dài lặp đi lặp lại (như $\texttt{aaaa\ldots}$ hay $\texttt{abab\ldots}$) rồi mới tới một chữ "lạ"; dòng chữ gồm nhiều lượt chép bỏ dở ngắn xen với lượt chép dài – đủ để tham lam nhảy xa nhất bị kẹt, chu kỳ của $S$ rất lớn, và mảng Z tính kiểu ngây thơ chạy rất lâu. Đáp án của các test lớn đều từ vài chục nghìn trở lên.
| Cách làm | Sub 1 (20%) | Sub 2 (30%) | Sub 3 (50%) | Điểm |
|---|---|---|---|---|
| Cách 1 – thử từng L, so xâu con | Đúng | TLE | TLE | 20 |
| Cách 2 – QHĐ đoạn dài nhất nhỏ nhất | Đúng | Đúng | TLE | 50 |
| Cách 3 – hàm Z + nhảy xa + chặt nhị phân | Đúng | Đúng | Đúng | 100 |
| Sai 1 – chặt nhị phân nhưng tham lam nhảy xa nhất | 5/10 test | 1/9 test | 3/10 test | ≈ 28 |
| Sai 2 – đáp án = chu kỳ nhỏ nhất của S | 4/10 test | 1/9 test | 3/10 test | ≈ 26 |
| Chậm – hàm Z đúng nhưng thử L tăng dần | Đúng | Đúng | TLE | 50 |
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 10/10 test subtask 1 và chạy quá 5 giây ở mỗi test subtask 2; Cách 2 đúng hết hai subtask đầu và mất từ 4,5 giây trở lên ở mỗi test subtask 3; Cách 3 đúng 29/29 test, test lâu nhất chỉ khoảng 0,01 giây. Hai lời giải sai chỉ "ăn may" ở ví dụ, các test cực nhỏ và các xâu kiểu $\texttt{aa\ldots ab}$ (ở đó đáp án trùng chu kỳ và tham lam không bị lừa).
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