trang chủ / đề bài / icpc24_nat_i

Lật xâu đối xứng

Đề bài

Mô tả

Cho hai xâu nhị phân a và b (đánh số từ 0), mỗi xâu có độ dài n. Bạn có thể thực hiện thao tác sau với số lần tùy ý (có thể bằng 0):

  • Chọn một xâu con liên tiếp của 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ố 0 thành 1 và ngược lại).

Hãy xác định xem có thể biến xâu a thành xâu b hay không.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương t (1≤t≤104): số bộ test. Mỗi bộ test gồm:

  • Dòng thứ nhất chứa số nguyên dương n (2≤n≤100): độ dài hai xâu.
  • Dòng thứ hai chứa xâu nhị phân a độ dài n.
  • Dòng thứ ba chứa xâu nhị phân b độ dài n.

Dữ liệu đảm bảo tổng n trên tất cả các bộ test không vượt quá 2·105.

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 a thành b. Ngược lại, in ra "NO".

Ràng buộc

  • 1≤t≤104
  • 2≤n≤100, tổng n trên tất cả các bộ test không vượt quá 2·105
  • a và b chỉ gồm các ký tự 0 và 1

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 [0,3] ("1001") được 01100, rồi đảo đoạn [3,4] ("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 [2,3] được 0011.

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