← 返回题目列表

Codeforces · 1381/A1

A1. 前缀翻转(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的差异在于 $$$n$$$ 的约束和所需的操作数量。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

有两个长度为$$$n$$$的二进制字符串$$$a$$$和$$$b$$$(二进制字符串是由符号$$$0$$$和$$$1$$$组成的字符串)。在运算中,选择 $$$a$$$ 前缀,同时反转前缀中的位($$$0$$$ 更改为 $$$1$$$,$$$1$$$ 更改为 $$$0$$$)并反转前缀中位的顺序。

例如,如果 $$$a=001011$$$ 并且您选择长度为 $$$3$$$ 的前缀,则它将变为 $$$011011$$$。然后,如果选择整个字符串,它将变为 $$$001001$$$。

你的任务是在最多 $$$3n$$$ 操作中将字符串 $$$a$$$ 转换为 $$$b$$$。可以证明,它总是可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。接下来的 $$$3t$$$ 行包含测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 1000$$$) — 二进制字符串的长度。

接下来两行包含两个二进制字符串 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

输出

对于每个测试用例,输出一个整数 $$$k$$$ ($$$0\le k\le 3n$$$),后跟 $$$k$$$ 整数 $$$p_1,\ldots,p_k$$$ ($$$1\le p_i\le n$$$)。这里 $$$k$$$ 是您使用的操作数,$$$p_i$$$ 是您在第 $$$i$$$ 操作中翻转的前缀长度。

示例

输入 #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

注意

在第一个测试用例中,我们有 $$$01\to 11\to 00\to 10$$$。

在第二个测试用例中,我们有 $$$01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$$$。

在第三个测试用例中,字符串已经相同。另一种解决方案是翻转长度 $$$2$$$ 的前缀,这将使 $$$a$$$ 保持不变。