Hướng dẫn giải của Mật khẩu (Đề HSG Nghệ An 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
Với mỗi xâu, ta chỉ cần tìm ký tự xuất hiện đúng 1 lần trong xâu đó (đề đảm bảo luôn tồn tại đúng một ký tự như vậy). Ghép các ký tự tìm được theo thứ tự i = 1..n để có mật khẩu.
Sub 1: Vét cạn — ~O(n \cdot |S|^2)~
Với mỗi xâu, thử từng vị trí j, đếm số lần ký tự s[j] xuất hiện bằng cách duyệt lại cả xâu. Ký tự nào có số lần đếm bằng 1 thì lấy và dừng. Cách này đúng theo đề nhưng mỗi xâu tốn ~|S|^2~ phép so sánh.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("MatKhau.INP", "r")) {
freopen("MatKhau.INP", "r", stdin);
freopen("MatKhau.OUT", "w", stdout);
}
int n;
cin >> n;
string mk = "";
for (int i = 0; i < n; i++) {
string s;
cin >> s;
// Vét cạn: với mỗi vị trí j, đếm số lần s[j] xuất hiện bằng cách duyệt lại cả xâu
for (int j = 0; j < (int)s.size(); j++) {
int dem = 0;
for (int k = 0; k < (int)s.size(); k++)
if (s[k] == s[j]) dem++;
if (dem == 1) {
mk += s[j]; // ký tự xuất hiện đúng 1 lần
break;
}
}
}
cout << mk << "\n";
return 0;
}
Sub 2: Đếm tần suất bằng mảng — ~O(n \cdot |S|)~
Thay vì đếm lại xâu cho mỗi ký tự, ta đếm trước số lần xuất hiện của 26 chữ cái trong mảng cnt (một lần duyệt xâu). Sau đó duyệt xâu lần nữa và lấy ký tự đầu tiên có cnt = 1.
Lưu ý: không cần kiểm tra tràn số vì độ dài xâu ≤ 1000.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("MatKhau.INP", "r")) {
freopen("MatKhau.INP", "r", stdin);
freopen("MatKhau.OUT", "w", stdout);
}
int n;
cin >> n;
string mk = "";
for (int i = 0; i < n; i++) {
string s;
cin >> s;
// Đếm tần suất mỗi chữ cái trong xâu (O(|S|))
int cnt[26] = {0};
for (char c : s) cnt[c - 'A']++;
// Tìm ký tự có tần suất đúng 1 (đúng một ký tự như vậy trong mỗi xâu)
for (char c : s)
if (cnt[c - 'A'] == 1) {
mk += c;
break;
}
}
cout << mk << "\n";
return 0;
}
Bình luận