【題解】Codeforces 1382C2. Prefix Flip (Hard Version)

#include <iostream>
#include <vector>
using namespace std;
 
int t, n, l, r, side, now;
string a, b;
vector <int> ans;
 
int main() {
    cin >> t;
    while (t--){
        cin >> n >> a >> b;
        a = "a" + a;
        b = "b" + b;
        l = 2;
        r = a.length()-1;
        side = 0;
        ans.clear();
        for (int i = a.length()-1; i > 1; i--){
            if (side){
                now = (a[l]-'0')^1;
                l++;
            }
            else{
                now = a[r]-'0';
                r--;
            }
            if (now == b[i]-'0') continue;
            if (a[1]-'0' == now){
                if (a[1] == '0') a[1] = '1';
                else a[1] = '0';
            }
            else{
                ans.push_back(1);
            }
            side ^= 1;
            ans.push_back(i);
        }
        if (a[1] != b[1]) ans.push_back(1);
        cout << ans.size();
        for (auto i:ans){
            cout << " " << i;
        }
        cout << "\n";
    }
}