Hướng dẫn giải của Mật khẩu
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 n xâu chỉ gồm chữ in hoa. Trong mỗi xâu có đúng một ký tự xuất hiện một lần, các ký tự còn lại xuất hiện ít nhất hai lần. Mật khẩu là ghép các ký tự duy nhất đó theo thứ tự các xâu.
Ví dụ: "ACADD", "FAAA", "ABBBBAFAAA" cho mật khẩu "CFF".
Sub 1: Vét cạn — ~O(n · L^2)~
Với mỗi xâu, thử từng ký tự và đếm số lần xuất hiện bằng cách quét lại cả xâu; ký tự có đúng một lần thì lấy và dừng. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("MatKhau.INP", "r", stdin);
freopen("MatKhau.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string res;
// Vét cạn: với mỗi xâu, thử từng ký tự và đếm số lần xuất hiện bằng cách quét cả xâu
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (char c : s) {
int cnt = 0;
for (char d : s)
if (d == c) cnt++;
if (cnt == 1) { // ký tự chỉ xuất hiện đúng 1 lần là ký tự cần tìm
res += c;
break;
}
}
}
cout << res << '\n';
return 0;
}
Sub 2: Đếm bằng mảng 26 phần tử — ~O(n · L)~
Với mỗi xâu, đếm số lần xuất hiện của 26 chữ cái vào mảng cnt, rồi duyệt lại xâu và lấy ký tự đầu tiên có cnt == 1. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("MatKhau.INP", "r", stdin);
freopen("MatKhau.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string res;
// Với mỗi xâu, đếm số lần xuất hiện của 26 chữ cái, lấy chữ có đúng 1 lần
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int cnt[26] = {0};
for (char c : s) cnt[c - 'A']++;
for (char c : s)
if (cnt[c - 'A'] == 1) {
res += c;
break;
}
}
cout << res << '\n';
return 0;
}
Bình luận