307601: CF1381A1. Prefix Flip (Easy Version)

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Prefix Flip (Easy Version)

题意翻译

给定一个01构成的字符串 $a$ 。你需要将它在$3 n$次操作内变成字符串 $b$ 。有多组数据。 每一次操作,你可以将字符串的前 $p$ 个颠倒顺序,并把其中的 $0$ 变成 $1$ ,$1$ 变成 $0$ 。 举例: $p=3$ 时 ``001011`` 变成 ``011011``, ``011011`` $p=6$ 时变成``001001`` 现在给定 $t$ 组数据和对应的 $n,a_i,b_i$,保证 $|a\ |=|b\ |$ 输出 $t$ 行,每行先输出$k$,表示操作次数,然后按顺序输出$p_1,p_2...p_k$ . Translated by @Error_Eric

题目描述

This is the easy version of the problem. The difference between the versions is the constraint on $ n $ and the required number of operations. You can make hacks only if all versions of the problem are solved. There are two binary strings $ a $ and $ b $ of length $ n $ (a binary string is a string consisting of symbols $ 0 $ and $ 1 $ ). In an operation, you select a prefix of $ a $ , and simultaneously invert the bits in the prefix ( $ 0 $ changes to $ 1 $ and $ 1 $ changes to $ 0 $ ) and reverse the order of the bits in the prefix. For example, if $ a=001011 $ and you select the prefix of length $ 3 $ , it becomes $ 011011 $ . Then if you select the entire string, it becomes $ 001001 $ . Your task is to transform the string $ a $ into $ b $ in at most $ 3n $ operations. It can be proved that it is always possible.

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1\le t\le 1000 $ ) — the number of test cases. Next $ 3t $ lines contain descriptions of test cases. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 1000 $ ) — the length of the binary strings. The next two lines contain two binary strings $ a $ and $ b $ of length $ n $ . It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 1000 $ .

输出格式


For each test case, output an integer $ k $ ( $ 0\le k\le 3n $ ), followed by $ k $ integers $ p_1,\ldots,p_k $ ( $ 1\le p_i\le n $ ). Here $ k $ is the number of operations you use and $ p_i $ is the length of the prefix you flip in the $ i $ -th operation.

输入输出样例

输入样例 #1

5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1

输出样例 #1

3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1

说明

In the first test case, we have $ 01\to 11\to 00\to 10 $ . In the second test case, we have $ 01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100 $ . In the third test case, the strings are already the same. Another solution is to flip the prefix of length $ 2 $ , which will leave $ a $ unchanged.

Input

题意翻译

给定一个01构成的字符串 $a$ 。你需要将它在$3 n$次操作内变成字符串 $b$ 。有多组数据。 每一次操作,你可以将字符串的前 $p$ 个颠倒顺序,并把其中的 $0$ 变成 $1$ ,$1$ 变成 $0$ 。 举例: $p=3$ 时 ``001011`` 变成 ``011011``, ``011011`` $p=6$ 时变成``001001`` 现在给定 $t$ 组数据和对应的 $n,a_i,b_i$,保证 $|a\ |=|b\ |$ 输出 $t$ 行,每行先输出$k$,表示操作次数,然后按顺序输出$p_1,p_2...p_k$ . Translated by @Error_Eric

加入题单

上一题 下一题 算法标签: