两种解法，第一种是从前往后再从后往前，两次for循环。
第二种是从后往前匹配，一次循环。
最后时间第一种是46ms，第二种是46ms或者31ms？，空间都是800kb，但第一种理解与实现起来相对简单。
为了方便说明，初始字符串称为s，目标字符串称为d
第二种因为for循环次数比第一种少一半，但每次循环做的更多，所以时间似乎是相同的。
第二种我测了两次，有一次跑了31ms。两次的代码有点点不同，31ms的如下面解法二所示，而46ms的我把if(flip)那段分成了两次。
31ms的代码函数更少，理论上时间应该是一样的，但考虑到cpu分支预测之类的玄学情况，不清楚是否真的会带来优化。
下面是46和31两次代码的区别。
// 46ms
if(){
f(1);
f(i + 1);
if(flip){}else{}
}else{
f(i + 1);
if(flip){}else{}
}
// 31ms
if(){
f(1);
}
f(i + 1);
if(flip){}else{}
解法一
总体思路是先把s变成全是0或者全是1，然后再变成d。
第一次循环从前往后遍历s，把s变成全是0或者1。具体来说就是从前往后遍历，遇到不同的就意味着要变。
第二次循环从后往前遍历d，把刚刚的结果变成d。同样也是从后往前遍历，遇到不同的就意味着要变。
细节是设置一个flag记录当前是0还是1，遇到不同就添加答案，第一次循环结束后，相当于s的元素全变成了flag 。
直接拿flag参与第二次循环。
第一次循环是从s[1]到s[n-1]，第二次是从d[n-1]到d[0]，由此也可以得到这种方法的翻转次数 <= 2n-1。
//#pragma warning(disable:4996)
#include<stdio.h>
#define MAX 100000
int N;
char s[MAX + 1], d[MAX + 1];
int ans[2 * MAX];
int ansSP;
int main() {
//freopen("q.txt", "r", stdin);
// big loop
int t;
// temp loop
int i;
// flag
int flag;
scanf("%d", &t);
for (; t; t--) {
scanf("%d", &N);
scanf("%s", s);
scanf("%s", d);
ansSP = 0;
// loop 1
flag = s[0];
for (i = 1; i < N; i++) {
if (s[i] != flag) {
flag = s[i];
ans[ansSP++] = i;
}
}
// loop 2
for (i = N - 1; i >= 0; i--) {
if (d[i] != flag) {
flag = d[i];
ans[ansSP++] = i + 1;
}
}
// output
printf("%d ", ansSP);
for(i = 0; i < ansSP; i++)
printf("%d ", ans[i]);
printf("\n");
}
return 0;
}
解法二
思路是从后往前检查 s[ i ] 和 d[ i ] 是否相等，不相等就把 s[ 0 ] 变成与 d[ i ] 不相等，然后再翻转i+1。这样s[ 0 ]就变成与d[ i ]相等，并且位置与s[ i ]调换。
细节是需要两个指针或者下标，分别记录当前s[ 0 ] 和 s[ i ]对应原数组的哪个元素。同时还需要一个flag记录当前是不是在翻转状态。当完成一次匹配后，实际上就可以不考虑该数字了，因为是从后往前翻转，所以可以避免当前的翻转影响之前的结果。
//#pragma warning(disable:4996)
#include<stdio.h>
#define MAX 100000
int N;
char s[MAX + 1], d[MAX + 1];
int ans[2 * MAX];
int ansSP;
int main() {
//freopen("q.txt", "r", stdin);
// big loop
int t;
// temp loop
int i;
// flag
int first, last, flip, temp;
scanf("%d", &t);
for (; t; t--) {
scanf("%d", &N);
scanf("%s", s);
scanf("%s", d);
ansSP = 0;
first = 0;
last = N - 1;
flip = 0;
for (i = N - 1; i >= 0; i--) {
if ((s[last] != d[i]) ^ flip) {
if ((s[first] == d[i]) ^ flip) {
ans[ansSP++] = 1;
}
ans[ansSP++] = i + 1;
if (flip) {
// swap
temp = first - 1;
first = last;
last = temp;
// flip
flip = 0;
}
else {
// swap
temp = first + 1;
first = last;
last = temp;
// flip
flip = 1;
}
}
else {
if (flip) {
last++;
}
else {
last--;
}
}
}
// output
printf("%d ", ansSP);
for(i = 0; i < ansSP; i++)
printf("%d ", ans[i]);
printf("\n");
}
return 0;
}
