Hướng dẫn giải của Đếm kí tự (đề Phú Yên 2021)
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
Đếm số lần xuất hiện của mỗi chữ cái in hoa A..Z và chữ số 0..9 trong xâu S (dài tối đa 255 ký tự), rồi in các ký tự có xuất hiện theo thứ tự từ điển 0..9, A..Z.
Sub 1: Vét cạn — ~O(62 \cdot n)~
Với mỗi ký tự cần xét (62 ký tự), duyệt lại toàn bộ xâu để đếm số lần nó xuất hiện. Cách làm thẳng theo đề, đúng nhưng phải duyệt xâu nhiều lần.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BAI1.INP", "r")) { freopen("BAI1.INP", "r", stdin); freopen("BAI1.OUT", "w", stdout); }
// Doc toan bo xau S
string s, all;
while (cin >> s) all += s;
// Vet can: voi moi ky tu theo thu tu 0..9, A..Z, dem lai bang cach duyet ca xau
string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for (char c : chars) {
int cnt = 0;
for (size_t i = 0; i < all.size(); i++)
if (all[i] == c) cnt++;
if (cnt > 0) cout << c << " " << cnt << "\n";
}
return 0;
}
Sub 2: Dùng mảng đếm — ~O(n)~
Chỉ cần duyệt xâu một lần: mỗi ký tự gặp thì tăng bộ đếm cnt[c] tương ứng. Cuối cùng in các ký tự có cnt > 0 theo thứ tự từ điển. Dùng mảng 256 phần tử và ép kiểu unsigned char để tránh chỉ số âm.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BAI1.INP", "r")) { freopen("BAI1.INP", "r", stdin); freopen("BAI1.OUT", "w", stdout); }
// Doc toan bo xau S
string s, all;
while (cin >> s) all += s;
// Mang dem: cnt[c] la so lan xuat hien cua ky tu c (chi can 256 o)
int cnt[256] = {0};
for (unsigned char c : all) cnt[c]++;
// In theo thu tu tu dien 0..9, A..Z
string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for (char c : chars)
if (cnt[(unsigned char)c] > 0) cout << c << " " << cnt[(unsigned char)c] << "\n";
return 0;
}
Bình luận