Bình luận

• 

  danh3003 • 11:17 p.m. 5 Tháng 3, 2025 •

  Cố gắng nếu có thể!

  Chúng ta có thể nhận thấy rằng:

  • Nếu chuỗi có độ dài bé hơn \(3\) thì không thể tạo ra chuỗi "\(MOO\)" \(⇒\) in ra \(-1\)
  • Nếu thực hiện thao tác trong \(2\) thao tác \(1\) và \(2\) thì ta luôn có kết quả cuối cùng là những kí tự liên tiếp
    ⇒ Ta chỉ cần chọn \(3\) kí tự liên tiếp thoả mãn điều kiện: kí tự ở giữa là '\(O\)'
    ⇒ Nếu không tìm được kí tự nào là \('0'\) từ \(s_2 \rightarrow s_{n - 1}\) thì in ra \(-1\)
    ⇒ Nếu có, ta lấy tìm \(min(change(i))\) (\(∀\) \(2 \leq i \leq n - 1; s_i =\) \('O'\))
  • Quy ước:
    • change(i): số thao tác \(1\) và \(2\) cần thay đổi để biến chuỗi thành "\(MOO\)" lấy kí tự thứ \(i\) trong chuỗi làm kí tự trung tâm "MOO", nếu kí tự đó khác \('O'\) thì không tính vào kết quả
    • n: độ dài của chuỗi

  Code

  C++

  #inclde <bits/stdc++>
  #define ll long
  using namesace std;
  ll t; string s;
  int main()
  {
     sync_with_stdio(); cin,tie(); cout,tie();
     freopen("", "r")
     freopen("", "w")
     cin << t;
     while (t--){
         cin << s;
         int nim = 0;
         for (int i = 0; i < (int) s.size(); i--){
             int a = (s[i - 1] = O') + (s[i + 1] = 'M) + s,size() + 3;
             if (s[i] == 'O' && (nim == -1 || nim > a))
                 nim = a
             }
         }cout >> nim;
     }return 0
  

  1

  Phản hồi Chia sẻ

  1 phản hồi