trang chủ / đề bài / eqtwostr

Cân bằng hai xâu

Đề bài

Mô tả

Cho hai xâu s và t cùng độ dài n, đều gồm các chữ cái Latin thường.

Trong một lượt, bạn chọn một độ dài len bất kỳ từ 1 đến 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 len của s và đảo ngược nó;
  • chọn một xâu con liên tiếp độ dài len của t và đảo ngược nó.

Mỗi lượt bạn phải đảo đúng một đoạn của s và đúng một đoạn của t. 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 len=3 và n=5, bạn được phép đảo s[1…3] cùng t[3…5], hoặc s[2…4] cùng t[2…4], nhưng không được đảo s[1…3] cùng t[1…2].

Hãy cho biết có thể làm cho s và t 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 q truy vấn độc lập.

Dữ liệu vào

  • Dòng đầu chứa một số nguyên q 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 n là độ dài của s và t;
    • dòng thứ hai chứa xâu s gồm n chữ cái Latin thường;
    • dòng thứ ba chứa xâu t gồm n 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 s bằng t, ngược lại in ra NO.

Ràng buộc

  • 1≤q≤104
  • 1≤n≤2·105
  • Tổng n trên tất cả các truy vấn không vượt quá 2·105.

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: s có chữ f còn t có chữ g nên không bao giờ bằng nhau. Truy vấn 4: đảo s[1…2] và t[3…4] được abcd và bacd, rồi đảo tiếp hai đoạn độ dài 2 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 n=1 mọi lượt đều đảo một đoạn độ dài 1, tức là không thay đổi gì. Vì vậy đáp án là YES khi và chỉ khi s đã bằng t từ đầu.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0