Hướng dẫn giải của [Beginner Free Contest 17] KSTRPOW
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 hai xâu S, T và số nguyên K. Kiểm tra T có phải là xâu lũy thừa bậc K của S (T được tạo bằng cách viết K lần S liên tiếp) hay không. In YES hoặc NO.
Sub 1: Dựng lại xâu S^K rồi so sánh — ~O(K·|S|)~
Viết S liên tiếp K lần vào một xâu mới rồi so sánh với T. Độ dài tối đa khoảng 10^6 nên đủ nhanh. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
int k;
cin >> s >> t >> k;
// Sub 1: dung truc tiep xau S^K bang cach viet K lan S roi so sanh voi T
string built;
for (int i = 0; i < k; i++) built += s;
cout << (built == t ? "YES" : "NO") << endl;
return 0;
}
Sub 2: Kiểm tra từng ký tự — ~O(|T|)~
Trước hết kiểm tra độ dài: |T| phải bằng K·|S|, nếu không thì NO. Sau đó với mỗi i, ký tự T[i] phải bằng S[i mod |S|]. Cách này không tạo xâu mới nên tiết kiệm bộ nhớ. Đạt 20/20 test.
Bẫy cần chú ý: phải kiểm tra độ dài trước để không so sánh ngoài phạm vi.
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
int k;
cin >> s >> t >> k;
// T phai dai dung |S| * K
if ((long long)t.size() != (long long)s.size() * k) {
cout << "NO" << endl;
return 0;
}
// Ki tu thu i cua T phai bang ki tu thu (i mod |S|) cua S
for (size_t i = 0; i < t.size(); i++) {
if (t[i] != s[i % s.size()]) {
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
return 0;
}
Bình luận