Hướng dẫn giải của Mật khẩu an toàn
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
Dem xau con co do dai >= 6 chua it nhat mot chu in hoa, mot chu thuong va mot chu so.
Sub 1: Vet can, ~N \le 500~ ~O(N^2)~
Voi moi l, mo rong r va dem dieu kien. Chay rieng: dung 15/20 test.
Sub 2: Vi tri gan nhat, ~N \le 2 \cdot 10^6~ ~O(N)~
Voi moi r, doan [l..r] tot khi l <= min(vi tri gan nhat cua 3 loai) va l <= r - 5. Chay rieng: dung 20/20 test.
Chương trình hoàn chỉnh
Neu N <= 500 dung sub 1, nguoc lai dung sub 2.
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
// Loai ky tu: 0 = in hoa, 1 = in thuong, 2 = chu so, 3 = khac
int typ(char c) {
if (isupper((unsigned char)c)) return 0;
if (islower((unsigned char)c)) return 1;
if (isdigit((unsigned char)c)) return 2;
return 3;
}
// Sub 1: vet can O(N^2), dung khi N <= 500: voi moi l, mo rong r va ghi nhan da du 3 loai chua
void sub1() {
long long ans = 0;
for (int l = 0; l < n; l++) {
bool has[3] = {false, false, false};
for (int r = l; r < n; r++) {
int t = typ(s[r]);
if (t < 3) has[t] = true;
if (r - l + 1 >= 6 && has[0] && has[1] && has[2]) ans++;
}
}
cout << ans << "\n";
}
// Sub 2: O(N): voi moi r, lay vi tri xuat hien gan nhat cua 3 loai; doan [l..r] tot khi
// l <= min(3 vi tri) va l <= r - 5
void sub2() {
long long ans = 0;
long long last[3] = {0, 0, 0}; // 1-based, 0 = chua co
for (int r = 1; r <= n; r++) {
int t = typ(s[r - 1]);
if (t < 3) last[t] = r;
long long m = min(last[0], min(last[1], last[2]));
long long up = min(m, (long long)r - 5);
if (up > 0) ans += up;
}
cout << ans << "\n";
}
int main() {
freopen("MATKHAU.INP", "r", stdin);
freopen("MATKHAU.OUT", "w", stdout);
getline(cin, s);
while (!s.empty() && (s.back() == '\r' || s.back() == '\n')) s.pop_back();
n = s.size();
if (n <= 500) sub1();
else sub2();
return 0;
}
Bình luận