Lật tiền tố nhị phân

Điểm: 6,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho hai xâu nhị phân $a$ và $b$ cùng độ dài $n$ (chỉ gồm các kí tự $0$ và $1$ ).

Một thao tác được định nghĩa như sau: chọn một số nguyên $p$ ( $1 \leq p \leq n$ ), sau đó với tiền tố độ dài $p$ của $a$ , ta đồng thời đảo bit từng vị trí (đổi $0 \leftrightarrow 1$ ) và đảo ngược thứ tự các kí tự trong tiền tố đó.

Ví dụ, nếu $a = 001011$ và chọn $p = 3$ thì $a$ trở thành $011011$ . Nếu tiếp đó chọn $p = 6$ thì $a$ trở thành $001001$ .

Nhiệm vụ của bạn là biến $a$ thành $b$ bằng không quá $2 n$ thao tác. Có thể chứng minh điều này luôn thực hiện được.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ( $1 \leq t \leq 1000$ ) — số bộ dữ liệu.
Với mỗi bộ:
- Dòng đầu chứa số nguyên $n$ ( $1 \leq n \leq 10^{5}$ ).
- Hai dòng kế tiếp lần lượt chứa hai xâu nhị phân $a$ và $b$ độ dài $n$ .

Tổng giá trị $n$ trên toàn bộ các bộ dữ liệu không vượt quá $10^{5}$ .

Dữ liệu ra

Với mỗi bộ, in một dòng theo định dạng:

$k p_{1} p_{2} \dots p_{k}$

trong đó $0 \leq k \leq 2 n$ là số thao tác đã dùng và $p_{i}$ ( $1 \leq p_{i} \leq n$ ) là độ dài tiền tố ở thao tác thứ $i$ . Nếu có nhiều phương án hợp lệ, in ra bất kì phương án nào.

Ràng buộc

$1 \leq t \leq 1000$
$1 \leq n \leq 10^{5}$
Tổng $n$ không vượt quá $10^{5}$ .

Ví dụ

Input	Output	Giải thích
5 2 01 10 5 01011 11100 2 01 01 10 0110011011 1000110100 1 0 1	3 1 2 1 3 1 5 2 0 7 1 10 8 7 1 2 1 1 1	Bộ 1: $01 \to 11 \to 00 \to 10$ . Bộ 3: $a$ đã bằng $b$ nên không cần thao tác nào. Các đáp án khác cũng được chấp nhận miễn $k \leq 2 n$ và xâu cuối cùng bằng $b$ .
1 3 000 111	1 3	Lật tiền tố độ dài $3$ của $a = 000$ : đảo bit từng vị trí thành $111$ , đảo ngược thứ tự vẫn là $111$ . Vậy $a = b$ sau đúng $1$ thao tác.

Bình luận

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