C. Menorah

显然对于每个操作我们是保留一个1
所以我们当先是x个1的话 做一次就是n+1-x个1
并且我们只有这两种数量 这样我们就可以特判无解了
之后显然 对于每两个操作 我们可以交换一次01
这样就是不同组的数量
但是显然还有一种解就是我们翻转一次 让他当原串再计算不同组数量
因为我们只有1能翻转 所以我们要记录1并且同组的下标 如果没有的话也只能不同组了
然后当然我们要对应的cnta==cntb 也就是同组相等 特判一下即可
代码写的脚臭 大家学一下思路就是了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);

void solve() {
    int n;cin>>n;
    string a,b;cin>>a>>b;
    int cnt1=0,cnta=count(all(a),'1'),cntb=count(all(b),'1');
    if(cnta!=cntb&&n+1-cnta!=cntb){cout<<-1<<endl;return;}
    int pos=-1,pos1;
    for(int i=0;i<n;i++){
        if(a[i]=='1')pos1=i;
        if(a[i]==b[i]){
            if(a[i]=='1')pos=i;
        }
        else cnt1++;
    }
    if(cnta!=cntb)cnt1=INF;
    if(n+1-cnta!=cntb){cout<<cnt1<<endl;return;}
    int cnt4=0;
    if(pos==-1)pos=pos1;
    for(int i=0;i<n;i++){
        if(i==pos)continue;
        if(a[i]=='1')a[i]='0';
        else a[i]='1';
    }
    for(int i=0;i<n;i++){
        if(a[i]!=b[i])cnt4++;
    }
    cout<<min(cnt4+1,cnt1)<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

原文地址：http://www.cnblogs.com/ycllz/p/16792422.html