Hướng dẫn cho Biến đổi xâu đối xứng
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Spoiler Alert
Hint 1
- Đếm số vị trí đối xứng khác nhau
Gọi \(L\) là con trỏ trái của xâu, di chuyển sang phải tới khi gặp \(R\)
Gọi \(R\) là con trỏ phải của xâu, di chuyển sang trái tới khi gặp \(L\)
Tăng biến đếm nếu \(S_L \neq S_R\)
Hint 2
- Dùng
while (cin >> s)
để nhận các xâu tới khi hết file
Hint 3
- Với mỗi truy vấn là xâu
S
nhận được
Ta đếm \(cnt\) là số lượng vị trí đối xứng khác nhau
Khi hai vị trí đối xứng khác nhau, ta chỉ cần thay một trong hai bên bằng bên còn lại
Hint 4
- Từ nhận xét trên, ta có \(cnt\) là số lượng thay đổi tối đa
Nếu \(cnt \leq 2\) thì xuất "
YES
" ngược lại xuất "NO
"
Reference AC code | \(O(n)\) time | \(O(n)\) auxiliary space |
C++
inline bool check(const string s) {
int cnt = 0;
for (int l = 0, r = sz(s) - 1; l < r; ++l, --r)
cnt += (s[l] != s[r]);
return cnt <= 2;
}
int main()
{
for (string s; cin >> s; cout << (check(s) ? "YES" : "NO") << '\n');
return 0;
}
Bình luận