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

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 900 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Cho một xâu con độ dài \(n\). Hãy tìm cách thay thế nhiều nhất 2 kí tự để thu được 1 xâu đối xứng.

Input

Gồm \(T\) testcase \((T \leq 10)\), mỗi testcase nằm trên một dòng:

  • Mỗi dòng gồm 1 xâu \(s\) \((|s| \leq 600)\)

Output

  • Hãy in ra \(T\) dòng, mỗi dòng là YES nếu có cách thực hiện yêu cầu trên, hoặc NO nếu không tồn tại cách nào.

Example

Test 1

Input 
zcxxxc
xxczxx
zxcvbn
Output 
YES
YES
NO

Note

Cách biến đổi từng testcase như sau:

  • zcxxxc \(\rightarrow\) ccxxcc
  • xxczxx \(\rightarrow\) xxccxx
  • Không có cách biến đổi thỏa mãn.

Cách đọc input bằng Python:

Python
import sys
for s in sys.stdin:
    # xử lý s

Bình luận


  • 9
    SPyofgame    10:28 a.m. 15 Tháng 6, 2020

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

    • 0
      THOANGLQDT    9:08 p.m. 29 Tháng 10, 2020

      ah ơi cho xin nốt đoạn code còn lại của hint 4


      • 1
        SPyofgame    10:28 p.m. 29 Tháng 10, 2020

        Chỉ có khai báo thư viện thâu bạn :v


        • 2
          n2anndk    8:11 p.m. 1 Tháng 3, 2021

          sz(s) là gì vậy a


          • 2
            SPyofgame    9:40 p.m. 1 Tháng 3, 2021

            ah thường thì để tránh bị sai do (size() - int) thì người ta thường định nghĩa

            C++
            #define sz(x) int((x).size())

          • -8
            THOANGLQDT    8:10 p.m. 30 Tháng 10, 2020

            Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

        9 bình luận nữa