THPTTD_66 - Biến đổi xâu _ Transtr

View as PDF

Submit solution

Points: 6.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: transtr.inp
Output: transtr.out

Author:
Problem type
Allowed languages
C, C#, C++, Go, Java, JavaScript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • 0
    vudinhlong  commented on April 2, 2024, 2:31 p.m.

    Ý tưởng:

    1. Ta sẽ cần đi tìm những đoạn kí tự 'B' liên tiếp nhau từ dưới lên, mục đích là để khi lật xong thì phần đó sẽ ko phải quan tâm nữa (hay nói cách khác là nếu duyệt từ đầu về, thì mỗi bước lật sẽ làm các kí tự đằng trước lật theo -> khó quản lý)

    2. Tìm được rồi thì sẽ cần xác định độ dài:

      • Nếu độ dài là 1 => ta chỉ cần dùng thao tác 1 để lật 'B' -> 'A' => +1 bước

      • Nếu độ dài > 1 => phải dùng thao tác 2 vì sẽ lật được cả xâu thành 'A' luôn => +1 bước

    3. Vậy khi lật như vậy, ta sẽ cần 1 biến ok để check trạng thái của xâu:

      • Quy ước: ok = 1, sẽ coi 'B' là 'B', ok = 0 sẽ coi 'A' là 'B'

      • Đơn giản vì nếu dùng hàm void edit(string &a) để swap kí tự thì TLE chặt :))

    4. Nếu gặp TH: BBBABBBB thì có thể các bạn sẽ miss mất 1 chữ 'A' do làm mốc ngắt, mặc dù sau khỉ dùng thao tác 2 cho xâu B ở cuối, 'A' sẽ biến thành 'B' nhưng mà bị miss => WA => cách khắc phục là khi xài thao tác 2 thì ++i lên cho nó duyệt lại

    5. Và TH cuối cùng là duyệt dãy B ở đầu xâu nhưng ko có kí tự 'A' để ngắt => check len > 0 thì +1 bước nữa rồi mới in ra

    Chúc các bạn AC nhéee <3


    • 0
      vudinhlong  commented on April 2, 2024, 2:36 p.m.

      Cố gắng hết sức rồi mà chưa AC thì mình để code ở đây nhé:

      https://ideone.com/x8hI33

      hãy sử dụng 1 cách hiệu quả ._.