Hướng dẫn giải của Xâu thuần khiết (đề HSG 12 Phú Thọ 2023-2024)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Tách xâu thành ít xâu con nhất, mỗi xâu con liên tiếp và các ký tự trong đó đôi một khác nhau. Đầu ra là số xâu con.
Sub 1: Quy hoạch động — ~O(n^2)~, dùng khi ~n \le 1000~
Gọi ~dp[i]~ là số xâu ít nhất để tách tiền tố độ dài ~i~. Với mỗi ~i~, thử mọi điểm đầu ~j~ của đoạn cuối, đoạn phải không có ký tự lặp; ~dp[i] = \min(dp[j] + 1)~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Tham lam — ~O(n)~
Từ trái sang phải, mỗi lần lấy đoạn dài nhất có ký tự đôi một khác nhau. Cách này tối ưu vì nếu một đoạn có ký tự khác nhau thì mọi đoạn con của nó cũng vậy, nên lấy dài nhất không làm tệ hơn.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
// Sub 1: quy hoạch động vét cạn — dp[i] = số xâu con ít nhất để tách tiền tố s[0..i-1].
// Với mỗi i, thử mọi điểm bắt đầu j của đoạn cuối s[j..i-1]; đoạn phải toàn ký tự khác nhau. O(n^2)
void sub1() {
vector<int> dp(n + 1, INT_MAX / 2);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int mask = 0;
for (int j = i - 1; j >= 0; j--) {
int bit = 1 << (s[j] - 'a');
if (mask & bit) break; // đoạn s[j..i-1] có ký tự lặp thì mọi j nhỏ hơn cũng lặp
mask |= bit;
dp[i] = min(dp[i], dp[j] + 1);
}
}
cout << dp[n] << "\n";
}
// Sub 2: tham lam — từ trái sang phải, mỗi lần lấy đoạn dài nhất có ký tự đôi một khác nhau. O(n)
void sub2() {
int cnt = 0;
int i = 0;
while (i < n) {
cnt++;
bool seen[26] = {false};
while (i < n && !seen[s[i] - 'a']) { seen[s[i] - 'a'] = true; i++; }
}
cout << cnt << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> s;
n = s.size();
if (n <= 1000) sub1(); // dữ liệu nhỏ: quy hoạch động
else sub2();
return 0;
}
Bình luận