Hướng dẫn giải của [VT Thiếu nhi] BÀI 07: CHAR
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 xâu S (≤ 1000 ký tự) gồm chữ cái tiếng Anh (phân biệt hoa thường) và chữ số. In ra số ký tự khác nhau, rồi mỗi dòng một ký tự kèm số lần xuất hiện. Thứ tự in: chữ in hoa A..Z, chữ thường a..z, rồi chữ số 0..9.
Ví dụ: "AzB1C9A1BC" cho 6 ký tự: A 2, B 2, C 2, z 1, 1 2, 9 1.
Sub 1: Vét cạn — ~O(62 · n)~
Với mỗi ký tự theo đúng thứ tự in, quét cả xâu đếm số lần xuất hiện; ký tự nào có số lần lớn hơn 0 thì đưa vào danh sách. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("CHAR.INP", "r", stdin);
freopen("CHAR.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
// Thứ tự in: chữ in hoa A..Z, chữ thường a..z, rồi chữ số 0..9
string order;
for (char c = 'A'; c <= 'Z'; c++) order += c;
for (char c = 'a'; c <= 'z'; c++) order += c;
for (char c = '0'; c <= '9'; c++) order += c;
// Vét cạn: với mỗi ký tự trong thứ tự trên, đếm bằng cách quét lại cả xâu
vector<pair<char, int>> res;
for (char c : order) {
int cnt = 0;
for (char d : s)
if (d == c) cnt++;
if (cnt > 0) res.push_back({c, cnt});
}
cout << res.size() << '\n';
for (auto &p : res) cout << p.first << ' ' << p.second << '\n';
return 0;
}
Sub 2: Mảng đếm theo thứ tự — ~O(n)~
Đánh số mỗi ký tự: 'A'..'Z' là 0..25, 'a'..'z' là 26..51, '0'..'9' là 52..61. Đếm một lượt vào mảng cnt, rồi duyệt mảng theo thứ tự số và in các vị trí có cnt > 0. Lưu ý không dùng thứ tự mã ASCII trực tiếp vì chữ số có mã nhỏ hơn chữ cái, trái với yêu cầu đề. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Thứ tự in: chữ in hoa, chữ thường, chữ số (không dùng thứ tự mã ASCII vì chữ số đứng trước chữ cái)
int rankOf(char c) {
if (c >= 'A' && c <= 'Z') return c - 'A';
if (c >= 'a' && c <= 'z') return 26 + (c - 'a');
return 52 + (c - '0');
}
int main() {
freopen("CHAR.INP", "r", stdin);
freopen("CHAR.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
// Đếm số lần xuất hiện của từng ký tự, lưu theo thứ tự rank (62 vị trí)
int cnt[62] = {0};
for (char c : s) cnt[rankOf(c)]++;
vector<int> ids;
for (int r = 0; r < 62; r++)
if (cnt[r] > 0) ids.push_back(r);
cout << ids.size() << '\n';
for (int r : ids) {
char c;
if (r < 26) c = 'A' + r;
else if (r < 52) c = 'a' + (r - 26);
else c = '0' + (r - 52);
cout << c << ' ' << cnt[r] << '\n';
}
return 0;
}
Bình luận