Hướng dẫn giải của Mã hóa (Đề chọn ĐTQG Phú Thọ 2017-2018)
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
Bản mã được mã hóa bằng dịch chữ kiểu Caesar với khóa k. Cho bản mã và k, khôi phục bản tin ban đầu bằng cách lùi mỗi chữ cái k vị trí. Đọc từ CAU2.INP, ghi ra CAU2.OUT.
Sub 1: Vét cạn — ~O(26·n)~
Với mỗi ký tự của bản mã, thử lần lượt 26 chữ cái gốc, chữ nào mã hóa ra đúng ký tự này thì chọn. Cách này không cần suy luận về phép dịch nhưng vẫn cho kết quả đúng.
Kết quả chấm: đạt 32/32 test (SUB ok 32/32, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU2.INP", "r")) {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
}
string s;
int k;
cin >> s >> k;
// Vét cạn: với mỗi ký tự mã, thử 26 chữ cái gốc, chữ nào mã hóa ra đúng ký tự này thì nhận
for (char c : s) {
for (char p = 'a'; p <= 'z'; p++) {
char enc = 'a' + (p - 'a' + k) % 26;
if (enc == c) {
cout << p;
break;
}
}
}
cout << "\n";
return 0;
}
Sub 2: Dịch ngược trực tiếp — ~O(n)~
Mã hóa là cộng k vào vị trí chữ cái (mod 26), nên giải mã là trừ k. Để tránh số âm khi trừ, cộng thêm 26 rồi lấy phần dư: c = 'a' + (c - 'a' - k + 26) % 26. Bẫy cần chú ý: bản tin dài tới 10^6 ký tự nên đọc bằng chuỗi và xử lý một lần.
Kết quả chấm: đạt 32/32 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU2.INP", "r")) {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
}
string s;
int k;
cin >> s >> k;
// Giải mã: lùi k vị trí, cộng 26 để tránh số âm
for (char &c : s)
c = 'a' + (c - 'a' - k + 26) % 26;
cout << s << "\n";
return 0;
}
Bình luận