Xâu đặc biệt
Đề bài
Yên và Định là hai học sinh giỏi bộ môn Tin học. Yên có một nhóm chữ cái tiếng Anh mà bạn ấy yêu thích, ghép các chữ cái này lại ta được xâu $a$. Định cũng vậy, Định có nhóm chữ cái tiếng Anh yêu thích của riêng mình, ghép các chữ cái yêu thích của Định ta được xâu $b$. Khi lấy hai nhóm chữ cái yêu thích của Yên và Định so sánh với nhau thì thấy tất cả chúng đều là chữ cái in thường và không có chữ cái nào cùng thuộc cả hai nhóm.
Yên và Định gọi xâu $x$ là xâu đặc biệt nếu trong xâu $x$ thỏa mãn:
- Các kí tự trong xâu $x$ hoặc là chữ cái yêu thích của Yên, hoặc là chữ cái yêu thích của Định, hoặc là dấu cách;
- Số lượng chữ cái thuộc nhóm chữ cái yêu thích của Yên bằng số lượng chữ cái thuộc nhóm yêu thích của Định.
Yêu cầu: Với một xâu $S$ chỉ gồm các chữ cái in thường và dấu cách cho trước. Hãy cho biết có bao nhiêu xâu con liên tiếp của $S$ là xâu đặc biệt theo cách gọi của Yên và Định.
Dữ liệu vào từ file XDB.INP gồm 3 dòng:
- Dòng 1: chứa xâu $a$ (gồm các chữ cái tiếng Anh in thường yêu thích của Yên);
- Dòng 2: chứa xâu $b$ (gồm các chữ cái tiếng Anh in thường yêu thích của Định);
- Dòng 3: chứa xâu $S$.
Kết quả ghi ra file XDB.OUT số lượng xâu con liên tiếp của $S$ là xâu đặc biệt.
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài cho xâu $S$ có độ dài $\le 10^2$;
- Có 30% số test ứng với 30% số điểm của bài cho xâu $S$ có độ dài $\le 10^4$;
- Có 40% số test ứng với 40% số điểm của bài cho xâu $S$ có độ dài $\le 10^5$.
Giới hạn: 1 giây, 256 MB. Trên CLUE OJ dữ liệu đọc/ghi qua file XDB.INP / XDB.OUT.
ab
fd
abfe agfdaa4Giải thích ví dụ: có 4 xâu thoả mãn là xâu bf; da; fdaa và xâu có một dấu cách (xâu chỉ gồm dấu cách có 0 chữ của Yên và 0 chữ của Định, bằng nhau nên cũng là xâu đặc biệt).
Lời mở đầu
Bài này nghe thì có vẻ là bài xâu, nhưng thực chất là bài tổng tiền tố + đếm bằng map rất quen thuộc: "đếm số đoạn con có tổng bằng 0". Mình sẽ đi từ cách vét cạn cho subtask 1, rồi tối ưu dần. Tất cả các cách đều được chạy thật trên 100 test của CLUE OJ.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
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:
Bộ testBộ test chính thức có gì?
Bộ test gồm 100 test. Mình gọi chữ "xấu" là chữ cái không thuộc $a$ cũng không thuộc $b$ (một xâu con chứa chữ xấu thì chắc chắn không đặc biệt).
| Nhóm test | Số test | Độ dài S | Số chữ cái được thích (|a|+|b|) | Số dấu cách (max) | Số chữ "xấu" | Đoạn không có chữ xấu dài nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|---|---|
| 1–30 | 30 | 5 – 20 | 4 – 19 | 5 | 0 – 12 | 12 | 15 |
| 31–60 | 30 | 10.000 – 10.000 | 7 – 25 | 2.096 | 287 – 5.902 | 250 | 26.551 |
| 61–100 | 40 | 100.000 – 100.000 | 26 – 26 | 20.221 | 0 – 0 | 100.000 | 1.617.496 |
| Subtask | Điều kiện (theo đề) | Test | Thực tế trong bộ test |
|---|---|---|---|
| 1 (30%) | $|S| \le 10^2$ | 1 – 30 | $|S|$ từ 5 đến 20 |
| 2 (30%) | $|S| \le 10^4$ | 31 – 60 | $|S| = 10^4$, có nhiều chữ "xấu" nên các đoạn tốt ngắn (≤ 250) |
| 3 (40%) | $|S| \le 10^5$ | 61 – 100 | $|S| = 10^5$, cả 26 chữ cái đều được thích → không có chữ xấu nào |
- Xâu $S$ có dấu cách, nên phải đọc cả dòng bằng
getline, không dùngcin >> sđược. - Dấu cách ở đầu và cuối dòng cũng tính: có 19 test mà $S$ bắt đầu bằng dấu cách và 22 test kết thúc bằng dấu cách. Tuyệt đối đừng "trim" xâu.
- Cả 100 test đều được tạo trên Windows nên cuối mỗi dòng có thêm ký tự
'\r'. Nếu không bỏ đi, ký tự này bị coi là chữ "xấu" và làm sai kết quả. Trong code mình viết hàmreadLine()đọc 1 dòng rồi xoá'\r'ở cuối nếu có.
Ý tưởngĐổi chữ thành số: +1, −1, 0 và "vách ngăn"
Ta gán cho mỗi ký tự của $S$ một "trọng số":
- Chữ của Yên (thuộc $a$): $+1$;
- Chữ của Định (thuộc $b$): $-1$;
- Dấu cách: $0$;
- Chữ "xấu" (không ai thích): là một vách ngăn – không xâu đặc biệt nào được chứa nó.
Khi đó một xâu con là đặc biệt khi và chỉ khi nó không chứa vách ngăn và tổng trọng số bằng 0 (số chữ của Yên trừ số chữ của Định bằng 0).
Gọi $P_i$ là tổng trọng số của $i$ ký tự đầu (tính từ vách ngăn gần nhất). Tổng của đoạn từ vị trí $j+1$ tới $i$ bằng $P_i - P_j$, nên:
map<int, int> cnt để đếm số lần mỗi giá trị tiền tố đã xuất hiện. Gặp vách ngăn thì xoá sạch map và bắt đầu lại.Với ví dụ của đề: abfe agfdaa có chữ e và g là vách ngăn, chia $S$ thành 3 đoạn abf, ␣a, fdaa. Em bấm Tiếp để xem map đếm tiền tố hoạt động:
Cách 1Vét cạn mọi xâu con – Subtask 1
Duyệt mọi cặp $(l, r)$, với mỗi xâu con $S[l..r]$ đếm số chữ của Yên (ca), số chữ của Định (cb) và kiểm tra có chữ xấu không. Hàm a.find(c) trả về string::npos nếu ký tự c không có trong xâu a.
Kết quả chạy thật: bản C++ đúng 30/100 test – ăn trọn Subtask 1; sai mọi test từ test 31 trở đi (quá thời gian); test đúng chậm nhất chạy dưới 0,01s. Bản Python đúng 30/100 test – ăn trọn Subtask 1; sai mọi test từ test 31 trở đi (quá thời gian); test đúng chậm nhất chạy 0,03s. Với $|S| = 10^4$ đã phải xét $5 \cdot 10^7$ xâu con, mỗi xâu dài trung bình hàng nghìn ký tự → quá chậm.
Cách 2Cố định đầu trái, cộng dồn và dừng ở vách ngăn – Subtask 1, 2
Hai cải tiến so với cách 1:
- Tính trước mảng trọng số
w[c]cho từng ký tự (256 ô theo mã ASCII) để không phảifindtrong xâu $a$, $b$ nữa. - Cố định $l$, cho $r$ tăng dần và cộng dồn
bal += w[s[r]]thay vì đếm lại từ đầu. Gặp chữ xấu thìbreakngay vì mọi xâu dài hơn đều chứa nó.
Độ phức tạp là $O(\sum \text{độ dài đoạn tốt}^2)$. Ở subtask 2 các đoạn tốt rất ngắn (dài nhất 250 ký tự) nên chạy nhanh. Nhưng ở subtask 3 cả 26 chữ cái đều được thích, không có vách ngăn nào nên vòng r luôn chạy tới cuối: $\frac{10^{10}}{2}$ phép tính.
Kết quả chạy thật: bản C++ đúng 60/100 test – ăn trọn Subtask 1, Subtask 2; sai mọi test từ test 61 trở đi (quá thời gian); test đúng chậm nhất chạy dưới 0,01s. Bản Python đúng 60/100 test – ăn trọn Subtask 1, Subtask 2; sai mọi test từ test 61 trở đi (quá thời gian); test đúng chậm nhất chạy 0,10s.
Cách 3Tổng tiền tố + map – Full điểm
Cài đặt đúng ý tưởng ở trên: duyệt $S$ một lần, giữ tổng tiền tố $p$ và map cnt. Ban đầu cnt[0] = 1 ứng với tiền tố rỗng (để đếm được cả các xâu con bắt đầu ngay từ đầu đoạn).
ans += cnt[p]phải đặt trướccnt[p]++: ta chỉ ghép vị trí hiện tại với các tiền tố trước đó, không ghép với chính nó (xâu rỗng không tính).- Gặp chữ xấu:
cnt.clear(), đặt lạicnt[0] = 1vàp = 0– coi như bắt đầu một xâu mới ngay sau vách ngăn. - Đáp án có thể lên tới $\frac{n(n+1)}{2} \approx 5 \cdot 10^9$ (ví dụ $S$ toàn dấu cách) nên
ansphải làlong long. - $p$ luôn nằm trong $[-n, n]$ nên cũng có thể dùng mảng
cnt[2n + 1]với chỉ số lệch $p + n$ thay cho map. Dùng map thì không phải lo chỉ số âm.
Kết quả chạy thật: bản C++ đúng 100/100 test – ăn trọn Subtask 1, Subtask 2, Subtask 3; test đúng chậm nhất chạy 0,03s. Bản Python dùng dict đúng 100/100 test – ăn trọn Subtask 1, Subtask 2, Subtask 3; test đúng chậm nhất chạy 0,09s.
Tổng kếtKết quả chạy thật của các cách
| Cách | Subtask 1 test 1–30 | Subtask 2 test 31–60 | Subtask 3 test 61–100 | Tổng | Chậm nhất (test đúng) |
|---|---|---|---|---|---|
| Cách 1 – C++ | 30/30 | 0/30 quá thời gian | 0/40 quá thời gian | 30/100 | 0,01s |
| Cách 1 – Python | 30/30 | 0/30 quá thời gian | 0/40 quá thời gian | 30/100 | 0,03s |
| Cách 2 – C++ | 30/30 | 30/30 | 0/40 quá thời gian | 60/100 | 0,01s |
| Cách 2 – Python | 30/30 | 30/30 | 0/40 quá thời gian | 60/100 | 0,10s |
| Cách 3 – C++ | 30/30 | 30/30 | 40/40 | 100/100 | 0,03s |
| Cách 3 – Python | 30/30 | 30/30 | 40/40 | 100/100 | 0,09s |
g++ -O2), giới hạn 1 giây. Cách 3 bản C++ đạt 100/100 test. Nhớ 3 cái bẫy đọc dữ liệu: dùng getline, giữ nguyên dấu cách đầu/cuối, và bỏ ký tự '\r'.
Nhận xét
Đăng nhận xét