Hướng dẫn giải của [200 đề thầy Đức] Bài 131: Chuỗi tốt
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Một chuỗi con tốt khi số 0 và số 1 khác nhau. Cần cắt s thành ít chuỗi con tốt nhất.
Sub 1: Quy hoạch động thử mọi đoạn — ~O(n^3)~
dp[i] là số đoạn ít nhất để cắt s[0..i). Với mỗi j < i, nếu đoạn s[j..i) tốt thì cập nhật dp[i] = min(dp[i], dp[j] + 1). Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
string s;
cin >> s;
int n = s.size();
// dp[i] = số chuỗi con ít nhất để cắt đoạn s[0..i)
const int INF = 1e9;
vector<int> dp(n + 1, INF);
dp[0] = 0;
for (int i = 1; i <= n; i++)
// Vét cạn: thử mọi đoạn s[j..i) làm đoạn cuối
for (int j = 0; j < i; j++) {
int d0 = 0, d1 = 0;
for (int k = j; k < i; k++) {
if (s[k] == '0') d0++;
else d1++;
}
if (d0 != d1 && dp[j] + 1 < dp[i]) dp[i] = dp[j] + 1;
}
cout << dp[n] << "\n";
}
return 0;
}
Sub 2: Công thức đếm — ~O(n)~
Nếu cả s đã tốt (số 0 khác số 1) thì đáp án là 1. Nếu không, số 0 bằng số 1; khi đó cắt ký tự đầu tiên thành một đoạn (luôn tốt) và phần còn lại có số 0 khác số 1, nên đáp án là 2. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
string s;
cin >> s;
int d0 = 0, d1 = 0;
for (char c : s) {
if (c == '0') d0++;
else d1++;
}
// Nếu cả chuỗi đã "tốt" thì cắt 1 đoạn.
// Nếu không, số 0 = số 1; cắt ký tự đầu tiên (đoạn có 1 ký tự luôn tốt)
// thì phần còn lại cũng có số 0 != số 1, nên đáp án là 2.
cout << (d0 != d1 ? 1 : 2) << "\n";
}
return 0;
}
Bình luận