CF1789D.Serval and Shift-Shift-Shift
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Serval has two n -bit binary integer numbers a and b . He wants to share those numbers with Toxel.
Since Toxel likes the number b more, Serval decides to change a into b by some (possibly zero) operations. In an operation, Serval can choose any positive integer k between 1 and n , and change a into one of the following number:
- a⊕(a≪k)
- a⊕(a≫k)
In other words, the operation moves every bit of a left or right by k positions, where the overflowed bits are removed, and the missing bits are padded with 0 . The bitwise XOR of the shift result and the original a is assigned back to a .
Serval does not have much time. He wants to perform no more than n operations to change a into b . Please help him to find out an operation sequence, or determine that it is impossible to change a into b in at most n operations. You do not need to minimize the number of operations.
In this problem, x⊕y denotes the bitwise XOR operation of x and y . a≪k and a≫k denote the logical left shift and logical right shift.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤2⋅103 ). The description of the test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤2⋅103 ) — the number of bits in numbers a and b .
The second and the third line of each test case contain a binary string of length n , representing a and b , respectively. The strings contain only characters 0 and 1.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅103 .
输出格式
For each test case, if it is impossible to change a into b in at most n operations, print a single integer −1 .
Otherwise, in the first line, print the number of operations m ( 0≤m≤n ).
If m>0 , in the second line, print m integers k1,k2,…,km representing the operations. If 1≤ki≤n , it means logical left shift a by ki positions. If −n≤ki≤−1 , it means logical right shift a by −ki positions.
If there are multiple solutions, print any of them.
输入输出样例
输入#1
3 5 00111 11000 1 1 1 3 001 000
输出#1
2 3 -2 0 -1
说明/提示
In the first test case:
The first operation changes a into 00111⊕00111000=11111 .
The second operation changes a into 11111⊕0011111=11000 .
The bits with strikethroughs are overflowed bits that are removed. The bits with underline are padded bits.
In the second test case, a is already equal to b , so no operations are needed.
In the third test case, it can be shown that a cannot be changed into b .