Hướng dẫn giải của XÂU KÝ TỰ
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 chỉ gồm chữ in hoa. Tìm độ dài lớn nhất của xâu con liên tiếp không chứa các ký tự A, N, H. Nếu không có xâu con nào thỏa mãn (mọi ký tự đều là A, N hoặc H) thì in -1. Dữ liệu vào từ tệp CAU2.INP, kết quả ghi ra tệp CAU2.OUT.
Sub 1: Vét cạn — ~O(N^3)~
Thử mọi xâu con S[i..j], với mỗi xâu quét lại từng ký tự để xem có ký tự cấm nào không. Nếu không có thì cập nhật độ dài lớn nhất. Đạt 3/20 test, còn lại quá giờ vì |S| có thể tới 10^5.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU2.INP", "r")) { freopen("CAU2.INP", "r", stdin); freopen("CAU2.OUT", "w", stdout); }
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
int n = s.size();
int best = -1;
// Vét cạn: thử mọi xâu con s[i..j], kiểm tra có chứa A, N, H không
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
bool bad = false;
for (int k = i; k <= j && !bad; k++)
if (s[k] == 'A' || s[k] == 'N' || s[k] == 'H') bad = true;
if (!bad) best = max(best, j - i + 1);
}
}
cout << best << "\n";
}
return 0;
}
Sub 2: Đếm liên tiếp, gặp ký tự cấm thì đặt lại — ~O(N)~
Duyệt xâu một lần, giữ cur là độ dài đoạn hiện tại không chứa ký tự cấm. Gặp A, N hoặc H thì đặt cur = 0 vì đoạn bị cắt; gặp ký tự khác thì tăng cur và cập nhật best. Cuối cùng nếu best = 0 (không có đoạn nào) thì in -1.
Bẫy cần chú ý: một ký tự đơn như B đã là xâu hợp lệ, nên không được in -1 khi chỉ mới thấy ký tự cấm. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU2.INP", "r")) { freopen("CAU2.INP", "r", stdin); freopen("CAU2.OUT", "w", stdout); }
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
int best = 0; // độ dài lớn nhất tìm được
int cur = 0; // độ dài đoạn hiện tại không chứa A, N, H
for (char c : s) {
if (c == 'A' || c == 'N' || c == 'H') cur = 0; // gặp ký tự cấm thì đoạn bị cắt
else {
cur++;
best = max(best, cur);
}
}
cout << (best == 0 ? -1 : best) << "\n";
}
return 0;
}
Bình luận