题目：
There are two binary strings a and b of length nn (a binary string is a string consisting of symbols 0 and 1). In an operation, you select a prefix of a, and simultaneously invert the bits in the prefix (0 changes to 1and 1 changes to 0) and reverse the order of the bits in the prefix.
For example, if a=001011 and you select the prefix of length 3, it becomes 011011. Then if you select the entire string, it becomes 001001
Your task is to transform the string a into b in at most 2n operations. It can be proved that it is always possible.
思路：我们可以每次只处理一位二进制，让a的第一位和b的最后一位不同，然后反转a未匹配的串，每次匹配一个b的后面的字符，这样最多操作也是2n。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <queue>
5 #include <string>
6 #include <vector>
7 #include <cmath>
8
9 using namespace std;
10
11 #define ll long long
12 #define pb push_back
13 #define fi first
14 #define se second
15
16 const int N = 2e5 + 10;
17 ll a[N], dp[N], sum;
18
19 void solve()
20 {
21 int T;
22 cin >> T;
23 while(T--){
24 int n;
25 string a, b;
26 cin >> n >> a >> b;
27
28 int k, al, ar, br, cnt, now;
29 vector<int > ans;
30 now = k = al = cnt = 0;
31 ar = br = n - 1;
32 while(1){
33 //printf("a[now] = %c b[br] = %c\n", a[now], b[br]);
34 if(cnt & 1){
35 if((a[now] - '0' + cnt) % 2 == b[br] - '0'){
36 k += 2, br--, ar--, now = al;
37 ans.pb(1);
38 ans.pb(n - cnt);
39 }else{
40 k += 1, br--, ar--, now = al;
41 ans.pb(n - cnt);
42 }
43 cnt++;
44 }else{
45 if((a[now] - '0' + cnt) % 2 == b[br] - '0'){
46 k += 2, br--, al++, now = ar;
47 ans.pb(1);
48 ans.pb(n - cnt);
49 }else{
50 k += 1, br--, al++, now = ar;
51 ans.pb(n - cnt);
52 }
53 cnt++;
54 }
55 //cout << "k = " << k << endl;
56 //cout << " cnt = " << cnt << endl;
57 //cout << "br = " << br << endl;
58 if(br < 0) break;
59 }
60
61 //cout << "ans = " << k << " ";
62 cout << k << endl;
63 for(auto x : ans) cout << x << " ";
64 cout << endl;
65 }
66 }
67
68 int main()
69 {
70 ios::sync_with_stdio(false);
71 cin.tie(0);
72 cout.tie(0);
73 solve();
74
75 return 0;
76 }