THPTTD_66 - Biến đổi xâu _ Transtr
Xem dạng PDF
Gửi bài giải
Điểm:
6,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
transtr.inp
Output:
transtr.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, JavaScript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Bình luận
Ý tưởng:
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ý)
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
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 :))
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
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
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ả ._.