Lật xâu đối xứng
Đề bài
Mô tả
Cho hai xâu nhị phân và (đánh số từ ), mỗi xâu có độ dài . Bạn có thể thực hiện thao tác sau với số lần tùy ý (có thể bằng ):
- Chọn một xâu con liên tiếp của có độ dài chẵn và là xâu đối xứng (palindrome), rồi đảo tất cả các chữ số trong xâu con đó (mọi chữ số thành và ngược lại).
Hãy xác định xem có thể biến xâu thành xâu hay không.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương (): số bộ test. Mỗi bộ test gồm:
- Dòng thứ nhất chứa số nguyên dương (): độ dài hai xâu.
- Dòng thứ hai chứa xâu nhị phân độ dài .
- Dòng thứ ba chứa xâu nhị phân độ dài .
Dữ liệu đảm bảo tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra "YES" (không có dấu ngoặc kép) nếu có thể biến thành . Ngược lại, in ra "NO".
Ràng buộc
- , tổng trên tất cả các bộ test không vượt quá
- và chỉ gồm các ký tự và
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 10010 01111 3 101 110 4 0000 0000 |
YES NO YES |
Bộ test thứ nhất: đảo đoạn ("1001") được 01100, rồi đảo đoạn ("00") được 01111. Bộ test thứ hai: xâu 101 không có xâu con đối xứng độ dài chẵn nào nên không thể thao tác. Bộ test thứ ba: không cần thao tác nào. |
| 4 2 00 11 2 01 10 4 0110 1001 4 1100 0011 |
YES NO YES YES |
Bộ test thứ nhất: đảo cả xâu 00. Bộ test thứ hai: 01 không có xâu con đối xứng độ dài chẵn. Bộ test thứ ba: đảo cả xâu 0110. Bộ test thứ tư: đảo 11 được 0000, rồi đảo đoạn được 0011. |
Bình luận