Hướng dẫn giải của [200 đề thầy Đức] Bài 128: Mật khẩu
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
Cho xâu $S$ gồm chữ cái in hoa, chữ cái in thường và chữ số. Cần đếm số cặp $(i, j)$ với $1 \le i < j \le |S|$ sao cho đoạn $S[i..j]$ là mật khẩu "an toàn": có độ dài ít nhất $6$, chứa ít nhất một chữ in hoa, một chữ in thường và một chữ số.
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 50~
Thử mọi cặp $(i, j)$, với mỗi cặp duyệt lại các ký tự của đoạn để kiểm tra độ dài và ba loại ký tự. Đếm các đoạn thỏa mãn.
Kết quả chấm riêng sub này: đúng 20/20 test.
Sub 2: Điểm đầu cố định, mở rộng dần — ~O(n^2)~
Với mỗi điểm đầu $i$, cho $j$ chạy từ $i$ đến cuối xâu và giữ ba cờ: đã gặp chữ in hoa, chữ in thường, chữ số chưa. Mỗi bước thêm một ký tự chỉ cần cập nhật cờ tương ứng, nên kiểm tra mỗi đoạn trong $O(1)$. Đoạn $[i, j]$ được đếm khi $j - i + 1 \ge 6$ và đủ ba cờ.
Bẫy cần chú ý: điều kiện độ dài là $\ge 6$ chứ không phải $> 6$. Ví dụ a1B2C3 có độ dài đúng $6$ vẫn là mật khẩu an toàn.
Kết quả chấm riêng sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc xâu $S$, rồi gọi sub1 nếu $|S| \le 50$, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm 50% test đầu nếu sub2 chưa làm kịp.
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
// Kiểm tra đoạn s[i..j] có "an toàn" không: độ dài >= 6, có chữ in hoa, chữ thường, chữ số
bool safe(int i, int j) {
if (j - i + 1 < 6) return false;
bool up = false, low = false, dig = false;
for (int k = i; k <= j; k++) {
if (isupper((unsigned char)s[k])) up = true;
else if (islower((unsigned char)s[k])) low = true;
else if (isdigit((unsigned char)s[k])) dig = true;
}
return up && low && dig;
}
// Sub 1: vét cạn — thử mọi cặp (i, j), kiểm tra từng đoạn bằng cách duyệt lại các ký tự
// Độ phức tạp O(n^3). Dùng khi n <= 50
void sub1() {
long long cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (safe(i, j)) cnt++;
cout << cnt << "\n";
}
// Sub 2: với mỗi điểm đầu i, mở rộng j và giữ 3 cờ (có in hoa, in thường, chữ số)
// cập nhật theo từng ký tự mới, nên mỗi đoạn kiểm tra trong O(1). Độ phức tạp O(n^2)
void sub2() {
long long cnt = 0;
for (int i = 0; i < n; i++) {
bool up = false, low = false, dig = false;
for (int j = i; j < n; j++) {
if (isupper((unsigned char)s[j])) up = true;
else if (islower((unsigned char)s[j])) low = true;
else if (isdigit((unsigned char)s[j])) dig = true;
// Đoạn [i, j] có độ dài >= 6 và đủ ba loại ký tự thì được đếm
if (j - i + 1 >= 6 && up && low && dig) cnt++;
}
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s;
n = (int)s.size();
if (n <= 50) sub1(); // S ngắn: vét cạn cho chắc
else sub2(); // S dài: đếm theo từng điểm đầu với cờ
return 0;
}
Bình luận