AcWing 4967. 翻转
原题链接
中等
作者:
さのpool
,
2024-01-17 12:42:17
,
所有人可见
,
阅读 61
可以拿dp去想
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6+10;
int f[N];
int solve()
{
string s1,s2;
cin>>s1>>s2;
int n = s1.size();
if(s1[0] != s2[0]||s1[n-1]!=s2[n-1]) return -1;
for(int i = 1;i<n-1;i++)
{
if(s2[i]!=s1[i]&&s2[i]!=s2[i-1]&&s2[i-1]==s2[i+1])
{
s2[i] = '1'+'0'-s2[i];
f[i] = f[i-1]+1;
}
else
f[i] = f[i-1];
}
return s1==s2?f[n-2]:-1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
cout<<solve()<<endl;
}
return 0;
}