Cân bằng hai xâu
Đề bài
Mô tả
Cho hai xâu và cùng độ dài , đều gồm các chữ cái Latin thường.
Trong một lượt, bạn chọn một độ dài bất kỳ từ đến rồi thực hiện đồng thời hai thao tác:
- chọn một xâu con liên tiếp độ dài của và đảo ngược nó;
- chọn một xâu con liên tiếp độ dài của và đảo ngược nó.
Mỗi lượt bạn phải đảo đúng một đoạn của và đúng một đoạn của . Vị trí hai đoạn có thể khác nhau, ràng buộc duy nhất là độ dài của chúng phải bằng nhau. Chẳng hạn với và , bạn được phép đảo cùng , hoặc cùng , nhưng không được đảo cùng .
Hãy cho biết có thể làm cho và trở nên bằng nhau sau một dãy lượt nào đó (có thể là dãy rỗng) hay không.
Bạn phải trả lời truy vấn độc lập.
Dữ liệu vào
- Dòng đầu chứa một số nguyên là số truy vấn.
- Mỗi truy vấn gồm ba dòng:
- dòng thứ nhất chứa số nguyên là độ dài của và ;
- dòng thứ hai chứa xâu gồm chữ cái Latin thường;
- dòng thứ ba chứa xâu gồm chữ cái Latin thường.
Dữ liệu ra
Với mỗi truy vấn, in ra YES nếu có thể làm bằng , ngược lại in ra NO.
Ràng buộc
- Tổng trên tất cả các truy vấn không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 abcd abdc 5 ababa baaba 4 asdf asdg 4 abcd badc |
NO YES NO YES |
Truy vấn 1: hai xâu là hoán vị của nhau nhưng mọi chữ cái đều đôi một khác nhau và số nghịch thế của chúng khác tính chẵn lẻ. Truy vấn 2: chữ cái lặp lại cho phép "đốt" một lượt ở một xâu mà không làm nó thay đổi. Truy vấn 3: có chữ f còn có chữ g nên không bao giờ bằng nhau. Truy vấn 4: đảo và được abcd và bacd, rồi đảo tiếp hai đoạn độ dài nữa là xong. |
| 5 1 a a 1 a b 1 z z 1 b a 1 m m |
YES NO YES NO YES |
Với mọi lượt đều đảo một đoạn độ dài , tức là không thay đổi gì. Vì vậy đáp án là YES khi và chỉ khi đã bằng từ đầu. |
Bình luận