Hướng dẫn giải của [200 đề thầy Đức] Bài 136: Xóa các chữ số 0
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
Các số 1 phải nằm liền nhau sau khi xóa. Vì vậy cần xóa toàn bộ số 0 nằm giữa số 1 đầu tiên và số 1 cuối cùng. Nếu không có số 1 nào thì đáp án là 0.
Sub 1: Vét cạn mọi đoạn — ~O(n^3)~
Thử mọi đoạn [l, r] có đầu và cuối là số 1 và chứa hết mọi số 1. Đếm số 0 trong đoạn và lấy giá trị nhỏ nhất. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
int n = s.size();
// Vét cạn: thử mọi đoạn [l, r] có đầu và cuối là '1' chứa hết mọi số '1'.
// Số '0' phải xóa = số '0' nằm trong đoạn đó. Lấy đoạn có ít '0' nhất.
int ketQua = INT_MAX;
bool coMotSo1 = false;
for (int l = 0; l < n; l++) {
if (s[l] != '1') continue;
for (int r = l; r < n; r++) {
if (s[r] != '1') continue;
bool hopLe = true;
for (int k = 0; k < n && hopLe; k++)
if (s[k] == '1' && (k < l || k > r)) hopLe = false;
if (!hopLe) continue;
int soZero = 0;
for (int k = l; k <= r; k++)
if (s[k] == '0') soZero++;
ketQua = min(ketQua, soZero);
coMotSo1 = true;
}
}
if (!coMotSo1) ketQua = 0; // không có số 1 nào thì không cần xóa
cout << ketQua << "\n";
}
return 0;
}
Sub 2: Tìm số 1 đầu và cuối — ~O(n)~
Tìm vị trí số 1 đầu tiên (first) và cuối cùng (last), đếm số 0 trong đoạn [first, last]. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
int n = s.size();
// Tìm vị trí số 1 đầu tiên và cuối cùng
int first = -1, last = -1;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
if (first == -1) first = i;
last = i;
}
}
if (first == -1) { // không có số 1 nào
cout << 0 << "\n";
continue;
}
// Các số 1 phải nằm liền nhau: cần xóa toàn bộ số 0 nằm giữa first và last
int soZero = 0;
for (int i = first; i <= last; i++)
if (s[i] == '0') soZero++;
cout << soZero << "\n";
}
return 0;
}
Bình luận