Hướng dẫn giải của [2526 KSCUM_PN] Câu 2: SString
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 Latin hoa và thường, độ dài tới 10^6. Xâu SString là xâu chỉ gồm một loại chữ cái (không phân biệt hoa thường). Tìm xâu SString dài nhất, in ra chữ cái đó (viết hoa) và độ dài. Nếu có nhiều kết quả thì lấy cái xuất hiện đầu tiên. Đề đọc từ CAU2.INP và ghi ra CAU2.OUT.
Sub 1: Mở rộng từ mỗi vị trí bắt đầu — ~O(n^2)~
Với mỗi vị trí i làm điểm bắt đầu, đi tiếp j cho đến khi gặp ký tự khác chữ cái (so sánh sau khi đổi về chữ thường). Ghi lại đoạn dài nhất, chỉ cập nhật khi dài hơn nên giữ được vị trí xuất hiện đầu tiên. Đạt 24/24 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); }
string s;
cin >> s;
int n = s.size();
// Sub 1: voi moi vi tri bat dau i, mo rong j khi cac ki tu cung chu cai (khong phan biet hoa thuong)
int bestLen = 0, bestPos = 0;
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && tolower(s[j]) == tolower(s[i])) j++;
if (j - i > bestLen) { bestLen = j - i; bestPos = i; }
}
cout << (char)toupper(s[bestPos]) << " " << bestLen << endl;
return 0;
}
Sub 2: Quét một lần giữ đoạn hiện tại — ~O(n)~
Duyệt một lần, giữ độ dài đoạn hiện tại curLen và vị trí bắt đầu curStart. Nếu ký tự i cùng chữ cái (bỏ qua hoa thường) với ký tự i − 1 thì tăng curLen, ngược lại bắt đầu đoạn mới. Chỉ cập nhật đáp án khi curLen lớn hơn đáp án hiện tại, nên giữ được vị trí xuất hiện đầu tiên. Đạt 24/24 test.
Bẫy cần chú ý: phải so sánh không phân biệt hoa thường, và chữ cái in ra phải viết hoa.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU2.INP", "r")) { freopen("CAU2.INP", "r", stdin); freopen("CAU2.OUT", "w", stdout); }
string s;
cin >> s;
int n = s.size();
// Quet mot lan: doan hien tai gom cac ki tu cung chu cai (bo qua hoa thuong)
int bestLen = 0, bestPos = 0, curLen = 0, curStart = 0;
for (int i = 0; i < n; i++) {
if (i > 0 && tolower(s[i]) == tolower(s[i - 1])) {
curLen++;
} else {
curStart = i;
curLen = 1;
}
// Chi cap nhat khi dai hon (giu vi tri xuat hien dau tien)
if (curLen > bestLen) { bestLen = curLen; bestPos = curStart; }
}
cout << (char)toupper(s[bestPos]) << " " << bestLen << endl;
return 0;
}
Bình luận