AcWing 4967. 翻转
原题链接
中等
作者:
m_math
,
2024-01-17 01:05:45
,
所有人可见
,
阅读 63
思路1:分类讨论
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
string t,s;
int tt;
void solve()
{
cin >> t >> s;
int n = t.size();
if(t[0] != s[0] || t[n - 1] != s[n - 1])
{
cout << -1 << endl;
return;
}
int cnt = 0;
for(int i = 1;i < n - 1;i++)
{
if(s[i] != t[i])
{
if(s[i + 1] == s[i] || s[i + 1] != t[i + 1] || s[i] == s[i - 1])
{
cout << -1 << endl;
return;
}
cnt++;
}
}
cout << cnt << endl;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> tt;
while(tt--)
solve();
return 0;
}
思路2:递推
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
char t[N],s[N];
int tt;
void solve()
{
scanf("%s%s", t, s);
int n = strlen(t);
if(t[0] != s[0] || t[n - 1] != s[n - 1])
{
cout << -1 << endl;
return;
}
int cnt = 0;
for(int i = 1;i < n - 1;i++)
{
if(s[i] != t[i])
{
if(s[i] == s[i + 1] || s[i] == s[i - 1])
{
cout << -1 << endl;
return;
}
s[i] ^= 1;
cnt++;
}
}
cout << cnt << endl;
}
int main()
{
scanf("%d",&tt);
while(tt--)
solve();
return 0;
}