题目链接
解题思路
这题有三个重要的性质：
-
在同一个点做两次操作与不在这个点做操作是等价的。
-
给两个不同的点做操作等价于交换这两个点。
-
给一个字符串做偶数次操作，这个字符串的 \(0\) 的数量和 \(1\) 的数量不会改变。
知道这三个性质，这题就很好做了，直接分操作次数的奇偶性来讨论即可，详见代码。
时间复杂度 \(O(n)\)。
参考代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
ll t;
/*
一个位置不会被做 2 次操作
100010111 --> 4 5
111101000 --> 4 5
010010111 --> 4 5
101101100 --> 4 5
100000000 --> 8 1
111111111 --> 0 9
010000000 --> 8 1
111111111 --> 0 9
*/
ll n;
string s1,s2,s3;
ll sum0,sum1,sum2,sum3,ans;
void solve()
{
sum0=sum1=sum2=sum3=ans=0;
ans=1e18;
cin>>n>>s1>>s2;
s1=' '+s1;
s2=' '+s2;
forl(i,1,n)
sum0+=s1[i]=='0',sum1+=s1[i]!='0';
forl(i,1,n)
sum2+=s2[i]=='0',sum3+=s2[i]!='0';
if(sum0==sum2 && sum1==0)
{
cout<<0<<endl;
return ;
}
else if(sum1==0)
{
cout<<-1<<endl;
return ;
}
ll ke1=sum0+1,ke0=n-ke1;
// cout<<ke0<<' '<<ke1<<endl;
if(!((sum0==sum2 && sum1==sum3) || (ke0==sum2 && ke1==sum3)))
{
cout<<-1<<endl;
return ;
}
s3=s1;
forl(i,1,n)
{
if(s3[i]=='0')
s3[i]='1';
else
s3[i]='0';
}
if(sum0==sum2 && sum1==sum3)
{
ll sum=0;
forl(i,1,n)
if(s1[i]!=s2[i])
sum++;
ans=min(ans,sum);
}
if(ke0==sum2 && ke1==sum3)
{
ll sum=0;
forl(i,1,n)
if(s3[i]!=s2[i])
sum++;
ans=min(ans,sum);
}
cout<<ans<<endl;
}
int main()
{
IOS;
t=1;
cin>>t;
while(t--)
solve();
QwQ;
}