Đảo bit tiền tố
Đề bài
Mô tả
Cho hai xâu nhị phân và có cùng độ dài , chỉ gồm các ký tự 0 và 1.
Trong một thao tác, bạn chọn một tiền tố của có số ký tự 0 bằng số ký tự 1, sau đó đảo tất cả các bit trong tiền tố đó (mỗi 0 thành 1 và mỗi 1 thành 0).
Ví dụ với 0111010000:
- Có thể chọn tiền tố độ dài (vì có bốn
0và bốn1): [01110100]00 → [10001011]00. - Sau đó chọn tiền tố độ dài (một
0và một1): [10]00101100 → [01]00101100. - Không được chọn tiền tố độ dài là [0100] vì có ba
0và một1.
Hỏi có thể biến thành sau một số thao tác (có thể bằng ) hay không?
Dữ liệu vào
Dòng đầu chứa số nguyên () — số bộ dữ liệu.
Mỗi bộ dữ liệu gồm:
- Dòng đầu chứa số nguyên () — độ dài hai xâu.
- Hai dòng tiếp theo lần lượt chứa xâu và xâu , mỗi xâu có độ dài và chỉ gồm các ký tự
0và1.
Tổng trên toàn bộ các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in YES nếu có thể biến thành , ngược lại in NO. Có thể in bằng chữ hoa hoặc thường tùy ý.
Ràng buộc
- Tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 10 0111010000 0100101100 4 0000 0000 3 001 000 12 010101010101 100110011010 6 000111 110100 |
YES YES NO YES NO |
Bộ 1: hai thao tác như minh hoạ ở phần đề bài. Bộ 2: đã bằng , không cần thao tác. Bộ 3: không có tiền tố nào hợp lệ để thao tác, mà . Bộ 4: tồn tại dãy thao tác biến thành . Bộ 5: thao tác hợp lệ duy nhất biến 000111 thành 111000, từ đó chỉ có thể quay lại 000111 — không thể đạt 110100. |
| 1 4 0000 0011 |
NO | Mọi tiền tố của 0000 đều có số 0 khác số 1, nên không thao tác được. |
Bình luận