trang chủ / bài tập / flipbits

Đảo bit tiền tố

Đề bài

Mô tả

Cho hai xâu nhị phân ab có cùng độ dài n, chỉ gồm các ký tự 01.

Trong một thao tác, bạn chọn một tiền tố của asố 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 a= 0111010000:

  • Có thể chọn tiền tố độ dài 8 (vì có bốn 0 và bốn 1): [01110100]00 → [10001011]00.
  • Sau đó chọn tiền tố độ dài 2 (một 0 và một 1): [10]00101100 → [01]00101100.
  • Không được chọn tiền tố độ dài 4 là [0100] vì có ba 0 và một 1.

Hỏi có thể biến a thành b sau một số thao tác (có thể bằng 0) hay không?

Dữ liệu vào

Dòng đầu chứa số nguyên t (1t104) — số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

  • Dòng đầu chứa số nguyên n (1n3·105) — độ dài hai xâu.
  • Hai dòng tiếp theo lần lượt chứa xâu a và xâu b, mỗi xâu có độ dài n và chỉ gồm các ký tự 01.

Tổng n trên toàn bộ các bộ dữ liệu không vượt quá 3·105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in YES nếu có thể biến a thành b, ngược lại in NO. Có thể in bằng chữ hoa hoặc thường tùy ý.

Ràng buộc

  • 1t104
  • 1n3·105
  • Tổng n không vượt quá 3·105.

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: a đã bằng b, không cần thao tác.
Bộ 3: không có tiền tố nào hợp lệ để thao tác, mà ab.
Bộ 4: tồn tại dãy thao tác biến a thành b.
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

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0