Hướng dẫn giải của Dãy kí tự số (TS 10 chuyên Ninh Bình 2022)
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
Cho một xâu gồm chữ số, chữ cái thường và chữ cái hoa (độ dài tới 10^6). Tìm độ dài dãy kí tự số liên tiếp dài nhất.
Sub 1: Vét cạn, thử mọi đoạn — ~O(n^3)~
Thử mọi đoạn [i, j], kiểm tra từng ký tự trong đoạn có phải chữ số không. Lấy độ dài lớn nhất.
Kết quả chấm: 27/40 (SUB ok 27/40, TLE 13, WA 0)
#include <bits/stdc++.h>
using namespace std;
bool laChuSo(char c) { return c >= '0' && c <= '9'; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("KTS.INP", "r")) { freopen("KTS.INP", "r", stdin); freopen("KTS.OUT", "w", stdout); }
string s;
cin >> s;
int n = s.size(), best = 0;
// Vet can: voi moi doan [i, j], kiem tra toan bo ky tu la chu so
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
bool ok = true;
for (int k = i; k <= j; k++)
if (!laChuSo(s[k])) { ok = false; break; }
if (ok) best = max(best, j - i + 1);
}
cout << best << "\n";
return 0;
}
Sub 2: Duyệt một lần — ~O(n)~
Duyệt xâu một lần, gặp chữ số thì tăng độ dài hiện tại, gặp ký tự khác thì đặt lại về 0. Cập nhật độ dài lớn nhất trong quá trình duyệt.
Kết quả chấm: 40/40
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("KTS.INP", "r")) { freopen("KTS.INP", "r", stdin); freopen("KTS.OUT", "w", stdout); }
string s;
cin >> s;
// Duyet mot lan, dem do dai doan chu so hien tai; gap ky tu khong phai chu so thi dat lai ve 0
int cur = 0, best = 0;
for (char c : s) {
if (c >= '0' && c <= '9') cur++;
else cur = 0;
best = max(best, cur);
}
cout << best << "\n";
return 0;
}
Bình luận