Biến đổi xâu đối xứng


Submit solution


Points: 200 (partial)
Time limit: 1.0s
Memory limit: 640M

Author:
Problem type

Cho một xâu con độ dài \(n\) gồm các chữ cái in thường (\(n \le 600\)).

Yều cầu: Tìm cách đổi nhiều nhất \(2\) kí tự trong xâu để thu được 1 xâu đối xứng.

Dữ liệu vào

  • Gồm T dòng (\(T\le 10\), mỗi dòng chứa 1 xâu ký tự độ dài không quá \(600\) ký tự

Kết quả

  • Gồm \(T\) dòng, mỗi dòng là chữ “YES” nếu có cách đổi được, ngược lại ghi “NO”

Sample Input

zcxxxc
xxczxx
zxcvbn

Sample Output

YES
YES
NO

Giải thích:

  • zcxxxc -> ccxxcc
  • xxczxx -> xxccxx
  • Không có cách đổi thỏa mãn

Comments


  • 0
    phamngocphuc2008  commented on Oct. 17, 2020, 5:01 p.m.

    bài này khá dễ mà điểm cao thế


  • 0
    SPyofgame  commented on June 15, 2020, 10:28 a.m.

    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 |
    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;
    }