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


  • 3
    Dang_Minh_Duc    12:51 p.m. 11 Tháng 2, 2024

    Có thể bạn chưa biết:
    Mỗi testcase của bài này đều là 5 xâu nhập trên 5 dòng
    Nên đáp án của mỗi test chỉ cần là 5 dòng YES/NO để AC

    Riêng bài này các bạn có thể làm cách như trên, for 5 lần nhập và xử lý xâu, nhưng tốt nhất khi gặp dạng này nên làm cách nhập khác để tránh WA oan uổng:(


    • 0
      NguyenLePhuc    8:59 p.m. 9 Tháng 8, 2023

      cho em hỏi máy không nhập số testcase làm sao mình làm ạ?


      • 1
        kenleweb13    8:14 p.m. 19 Tháng 3, 2023

        bài này làm theo cách python thì như nào ạ

        1 phản hồi

        • 0
          lamsauday246    9:12 p.m. 6 Tháng 2, 2023

          Làm pascal sao mà đọc được vậy mọi người


          • 0
            phubinh2k10    1:01 p.m. 4 Tháng 6, 2022

            Bài này dùng C++ read kiểu j zậy mọi ngừi? Em mới học nên ko bít :PPP

            1 phản hồi

            • 0
              ldvl2511    4:39 p.m. 24 Tháng 12, 2021 ← đã chỉnh sửa

              cho iem hỏi dùng pascal thì read kiểu gì vậy mọi người. chứ input không nhập i để for chạy lưu vào array thì biết chạy đến khi nào ạ :_)

              1 phản hồi

              • -6
                THOANGLQDT    8:05 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ở.


                • -10
                  THOANGLQDT    9:07 p.m. 29 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ở.


                  • -6
                    phamngocphuc2008    5:01 p.m. 17 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ở.

                    1 phản hồi

                    • 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;
}
                      1 phản hồi