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.

Authors: SPyofgame


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

Không có bình luận nào.