题目大意

给定两个只含 0 和 1 字符串 a , b ，在下面这种变换规则下，a 经过多少变换次数得到 b，输出该次数并输出每次变换的位置，并且变换次数不超过\(2 * n\)。

变换规则：选择字符串 a 的一个前缀，同时反转前缀中的位（ 0 变成 1 ， 1 变成 0 ），并反转前缀中位的顺序。例：\(a = 01011\), 从第2个位置进行操作，先反转位，得到\(a = 10011\)，再逆序该前缀，得到 \(a = 01011\)。

思路：

先将 a 和 b 都变成 0 串或者 1 串,那么 a 串变成 b 串的步骤就是先将 a 串变成 0串（1串），0 串（1串）反推到 b串（实际上就是 b 变换到 0 串的操作位置逆序，比如 操作是 2431 ，操作逆序就是 1342）。

细节处理：当 a 全部变成 0 串, 而 b 全部变成了 1 串，那么额外需要一次将 a 串从最后位置操作一次变成1串。

举例：\(n = 5\)

​ \(a = 01011, b = 11100\)

​ a 变换过程 :（1，2位置不同，操作前 1 位）a = 11011;

​ (2，3位置不同，操作前 2 位) a = 00011;

​ (3, 4位置不同，操作前 3 位) a = 11111; 3次

​ b变换过程同上，得到 b = 00000。（操作位置 ：3） 1次

此时 a, b不相同，所以 a 需要再经过 1 次操作，即操作位置 5，a = 00000。总次数 3 + 1 + 1 = 5次

答案 ：5 1 2 3 5 3

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int step1[N], step2[N];

int main(){
    int T;
    cin >> T;
    while(T --){
        
        int n, a = 0, b = 0;
        string str1, str2;
        
        cin >> n >> str1  >> str2 ;
        for(int i = 0; i < n - 1; i++) if(str1[i] != str1[i + 1]) step1[++a] = i + 1;//下标为0开始，所以加1
        for(int i = 0; i < n - 1; i++) if(str2[i] != str2[i + 1]) step2[++b] = i + 1;
        
        if(str1[n - 1] == str2[n - 1]) cout << a + b;//a , b变换成了相同的字符串
        else cout << a + b + 1;//a, b变成了相异的字符串，a需要再变换一次
        for(int i = 1; i <= a; i++) cout << " " << step1[i];
        if(str1[n - 1] != str2[n - 1]) cout << " " << n;
        for(int i = b; i >= 1; i--) cout << " " << step2[i];//b倒序输出
        
        cout << endl;
    }

    return 0;
}

​

​

​