Hướng dẫn giải của [Beginner Free Contest 07] REPALIND
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
Xâu t là s lặp k lần. Nhận xét: t đối xứng khi và chỉ khi s đối xứng, vì đảo ngược t cho (đảo s) lặp k lần và hai xâu cùng độ dài nên phải bằng nhau theo từng đoạn độ dài |s|.
Sub 1: Ghép xâu — dùng khi ~k \le 10~
Ghép s lặp k lần thành t (độ dài tối đa 5000 \cdot 10) rồi kiểm tra t đối xứng.
Nếu chỉ nộp sub này: đúng 5/10 test.
Sub 2: Kiểm tra s — ~O(|s|)~
Chỉ cần kiểm tra s đối xứng, không cần ghép xâu vì k có thể lên tới 10^18.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Với mỗi test, nếu k \le 10 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
// Nhan xet: s^k doi xung khi va chi khi s doi xung.
// (Doc nguoc s^k = (rev s)^k; hai xau cung do dai nen s = rev s.)
string s;
long long k;
// Sub 1: k <= 10 nen xau t co do dai <= 5000 * 10. Ghep t va kiem tra truc tiep.
void sub1() {
string t;
for (long long i = 0; i < k; i++) t += s;
string r(t.rbegin(), t.rend());
cout << (r == t ? "YES" : "NO") << "\n";
}
// Sub 2: kiem tra truc tiep s doi xung. O(|s|)
void sub2() {
string r(s.rbegin(), s.rend());
cout << (r == s ? "YES" : "NO") << "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> s >> k;
if (k <= 10) sub1();
else sub2();
}
return 0;
}
Bình luận