Kí tự
Đề bài
Cho xâu kí tự $S$ có chiều dài tối đa 1000 kí tự gồm các kí tự chữ cái cả hoa và thường.
Yêu cầu: hãy tìm xâu kí tự $T$ theo thứ tự trong $S$ gồm các kí tự hoa tăng dần dài nhất.
Dữ liệu vào: cho trong tập tin văn bản KITU.INP có 1 dòng duy nhất gồm các kí tự.
Kết quả: ghi vào tập tin văn bản KITU.OUT kết quả là số kí tự trong xâu $T$.
Subtask:
- 20% số test đầu tiên có $N \le 20$.
- 20% số test tiếp theo có $N \le 50$.
- 20% số test tiếp theo có $N \le 100$.
- 40% số test còn lại không có điều kiện gì thêm.
($N$ là độ dài xâu $S$.)
aADbCBcdDCEefDEgFh6Giải thích: xâu $S$ = aADbCBcdDCEefDEgFh. Xâu $T$ tăng dần là ABCDEF (lấy trong xâu $S$: A vị trí 2, B vị trí 6, C vị trí 10, D vị trí 14, E vị trí 15, F vị trí 17).
KITU.INP / KITU.OUT. Code bên dưới dùng mẫu if(fopen("KITU.INP", "r")){ freopen(...); }: có file thì đọc file, không có file thì vẫn đọc bàn phím bình thường, nên các bạn chạy thử trên máy hay nộp bài đều được.Lời mở đầu
Bỏ đi lớp áo "xâu kí tự", đây chính là bài toán kinh điển dãy con tăng dài nhất (Longest Increasing Subsequence – LIS): chỉ xét các chữ hoa, chọn ra nhiều chữ nhất (giữ nguyên thứ tự trong xâu) sao cho chữ sau lớn hơn hẳn chữ trước. Bài rất hợp để luyện quy trình của chương quy hoạch động: đi từ đệ quy vét cạn → QHĐ $O(N^2)$ → tận dụng chỉ có 26 chữ cái để còn $O(26N)$.
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ì?
| Test | Độ dài N | Số chữ hoa nhiều nhất | Đáp án |
|---|---|---|---|
| 1–20 | 2 … 19 | 13 | 0 … 5 |
| 21–40 | 22 … 49 | 28 | 3 … 7 |
| 41–60 | 52 … 99 | 51 | 5 … 10 |
| 61–100 | 534 … 1000 | 541 | 19 … 26 |
- 100 test, khớp đúng 4 subtask của đề. Ở subtask cuối có 10 test dài đúng 1000 kí tự. Khoảng một nửa số kí tự là chữ hoa.
- Lưu ý 1: ví dụ của đề không nằm trong bộ test (test 1 là một xâu khác).
- Lưu ý 2 – "tăng dần" là tăng ngặt: có test chứa hai chữ hoa giống nhau đứng liền nhau mà đáp án vẫn là 1, nên hai chữ bằng nhau không được cùng có mặt trong $T$.
- Lưu ý 3: có test không có chữ hoa nào (test 9), đáp án là 0 – code phải in 0 chứ không được in 1.
- Đáp án không bao giờ vượt quá 26 (chỉ có 26 chữ hoa A…Z, mỗi chữ dùng tối đa 1 lần). Có 3 test đạt đúng 26.
Bốn subtask và số test đúng của từng cách (chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 đệ quy | Cách 2 $O(N^2)$ | Cách 3 $O(26N)$ |
|---|---|---|---|---|---|
| 1 (20%) | $N \le 20$ | 1 – 20 | 20/20 | 20/20 | 20/20 |
| 2 (20%) | $N \le 50$ | 21 – 40 | 20/20 | 20/20 | 20/20 |
| 3 (20%) | $N \le 100$ | 41 – 60 | 20/20 | 20/20 | 20/20 |
| 4 (40%) | $N \le 1000$ | 61 – 100 | 0/40 | 40/40 | 40/40 |
(Số test đúng của bản C++, chạy thật với giới hạn 1 giây/test.)
Ý tưởngdp[i] – xâu tốt nhất kết thúc tại vị trí i
Với dãy con tăng, câu hỏi then chốt là: chữ hoa $s[i]$ có thể nối vào sau xâu nào? – vào sau bất kỳ xâu tăng nào kết thúc tại một chữ hoa $s[j]$ đứng trước ($j < i$) và nhỏ hơn ($s[j] < s[i]$). Muốn dài nhất thì chọn xâu dài nhất trong số đó. Vậy ta đặt:
Em nhập xâu rồi bấm Tiếp. Ô viền cam là chữ đang xét, ô tím là các chữ đứng trước mà nhỏ hơn (nối được), ô xanh là chữ có dp lớn nhất được chọn để nối vào. Bước cuối lần ngược lại để in ra chính xâu $T$:
Cách 1Đệ quy chọn / bỏ từng kí tự
Cách "ngây thơ" nhất: đi qua từng kí tự, với mỗi kí tự quyết định chọn (chỉ được chọn khi là chữ hoa lớn hơn chữ vừa chọn trước đó) hoặc bỏ. Đi hết xâu thì cập nhật độ dài lớn nhất. Hàm Try(i, last, len) nhớ chữ hoa vừa chọn last để kiểm tra điều kiện tăng.
Kết quả chạy thật: bản C++ đúng 60/100 test, quá thời gian ở các test 61–100; test đúng chạy lâu nhất 0,007 s. Bản Python đúng 60/100 test, quá thời gian ở các test 61–100; test đúng chạy lâu nhất 0,117 s. Đệ quy đi qua mọi xâu con tăng, số lượng xâu này tăng theo hàm mũ khi xâu dài; nhờ điều kiện "chữ hoa và lớn hơn" cắt bớt nhiều nhánh nên vẫn qua được tới $N \le 100$, nhưng gặp $N = 1000$ (khoảng 500 chữ hoa) thì chịu thua.
Mẹo nhỏ: kết quả của Try chỉ phụ thuộc $(i, last)$ – có $1000 \times 27$ trạng thái. Nếu viết lại thành hàm trả về giá trị và nhớ kết quả từng trạng thái (đệ quy có nhớ) thì cũng đạt full điểm. Ở dưới mình đi theo hướng QHĐ lập bảng quen thuộc của bài LIS.
Cách 2Quy hoạch động dp[i] – O(N²) (full điểm)
Cài đặt đúng công thức ở phần ý tưởng: với mỗi chữ hoa $s[i]$, duyệt mọi $j < i$ để tìm xâu tốt nhất nối được.
if (gộp với dòng for).- Chữ thường thì
continueluôn, $dp[i]$ giữ giá trị 0 – và điều kiệnisupper(s[j])ở vòng trong bảo đảm không bao giờ nối vào chữ thường. - Dùng dấu
<(không phải<=) vì "tăng dần" là tăng ngặt. anskhởi tạo bằng 0 nên xâu không có chữ hoa sẽ in 0.
Kết quả chạy thật: bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0,006 s; bản Python đúng 100/100 test; test đúng chạy lâu nhất 0,048 s. Với $N \le 1000$ thì $N^2/2 = 5 \cdot 10^5$ phép so sánh – quá nhẹ.
Cách 3Chỉ có 26 chữ cái – O(26·N)
Ở vòng trong của cách 2, ta chỉ cần biết: "trong các chữ hoa đã gặp mà nhỏ hơn $s[i]$, xâu dài nhất kết thúc bằng chúng dài bao nhiêu?". Câu hỏi này chỉ phụ thuộc vào chữ cái, không phụ thuộc vị trí. Nên thay vì mảng $dp$ theo vị trí, ta giữ mảng $f[c]$ theo chữ cái:
'A' + c. Gặp chữ hoa $ch$:
Kết quả chạy thật: bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0,004 s; bản Python đúng 100/100 test; test đúng chạy lâu nhất 0,022 s. Cách này đọc xâu một lượt, nên kể cả xâu dài $10^6$ kí tự vẫn chạy tốt.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Đệ quy chọn / bỏ | C++ | 60/100 | 0,007 s | Quá thời gian ở test 61–100 |
| Python | 60/100 | 0,117 s | Quá thời gian ở test 61–100 | |
| 2. QHĐ dp[i] | C++ | 100/100 | 0,006 s | Full điểm |
| Python | 100/100 | 0,048 s | Full điểm | |
| 3. QHĐ theo chữ cái | C++ | 100/100 | 0,004 s | Full điểm |
| Python | 100/100 | 0,022 s | Full điểm |
<= thay vì <, và quên trường hợp không có chữ hoa (phải in 0).
Nhận xét
Đăng nhận xét