https://codeforces.com/contest/1789/problem/D
给定两个 n 位二进制数 a,b，你可以每次使 \(a = a \oplus a >> k\) 或 \(a = a \oplus a << k\)，你需要用不超过 n 次操作使得 \(a = b\)，若无法达成输出
-1
显然 a 和 b 中仅有一个是 0 就无法达成
我们可以通过 a 的 1 来完成这个任务，由于不能超过 n 次操作，考虑每次操作都能固定一个位置，我们要保证每次操作不会影响我们已经确定好的数
首先尝试对齐 a 和 b 的最左端的 1，然后用这个 1 去更新它的右侧
然后考虑这个 1 的左端，我们可以用当前 a 中最小的 1 去更新，这样它的右侧全是 0，就不会影响我们已经调整好的部分
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <bitset>
#define i64 long long
const int mod = 998244353, inf = 0x3f3f3f3f;
int main() {
int T; std::cin >> T;
while (T--) {
int n; std::cin >> n;
std::string s, t; std::cin >> s >> t;
if (s == t) {
printf("0\n"); continue;
}
std::vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
a[i] = s[i - 1] - '0';
b[i] = t[i - 1] - '0';
}
if (std::count(a.begin() + 1, a.end(), 1) == 0) {
printf("-1\n"); continue;
}
if (std::count(b.begin() + 1, b.end(), 1) == 0) {
printf("-1\n"); continue;
}
int x = std::find(a.begin() + 1, a.end(), 1) - a.begin();
int y = std::find(b.begin() + 1, b.end(), 1) - b.begin();
std::vector<int> ans;
if (x > y) {
int d = x - y;
for (int i = 1; i + d <= n; i++) a[i] ^= a[i + d];
ans.push_back(d); x = y;
}
for (int i = x + 1; i <= n; i++) {
if (a[i] == b[i]) continue;
int d = i - x;
for (int j = n; j > d; j--) a[j] ^= a[j - d];
ans.push_back(-d);
}
int z = n; while (!a[z]) z--;
for (int i = x; i >= 1; i--) {
if (a[i] == b[i]) continue;
int d = z - i;
for (int j = 1; j <= i; j++) a[j] ^= a[j + d];
ans.push_back(d);
}
int m = ans.size(); printf("%d\n", m);
for (int i = 0; i < m; i++) printf("%d ", ans[i]); puts("");
}
return 0;
}