Marina loves strings of the same length and Vasya loves when there is a third string, different from them in exactly t characters. Help Vasya find at least one such string.
More formally, you are given two strings s1, s2 of length n and number t. Let's denote as f(a, b) the number of characters in which strings a and b are different. Then your task will be to find any string s3 of length n, such that f(s1, s3) = f(s2, s3) = t. If there is no such string, print - 1.
The first line contains two integers n and t (1 ≤ n ≤ 105, 0 ≤ t ≤ n).
The second line contains string s1 of length n, consisting of lowercase English letters.
The third line contain string s2 of length n, consisting of lowercase English letters.
Print a string of length n, differing from string s1 and from s2 in exactly t characters. Your string should consist only from lowercase English letters. If such string doesn't exist, print -1.
3 2 abc xyc
ayd
1 0 c b
-1
解题思路：
具体解释有点麻烦。。。直接上代码吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e5+5;
const int mod = 1000000007;
const double eps = 1e-7;
int f(char s1[],char s2[],int n,bool flag[])
{
int sum=0;
for(int i=0; i<n; i++)
{
if(s1[i]!=s2[i])
{
sum++;
flag[i]=true;
}
}
///cout<<sum<<"++"<<endl;
return sum;
}
char s1[maxn],s2[maxn],s[maxn];
int main()
{
int n,t,sum;
bool flag[maxn];
memset(flag,false,sizeof(flag));
cin>>n>>t;
cin>>s1>>s2;
sum=f(s1,s2,n,flag);
s[n]='\n';
if((1+sum)/2>t) cout<<-1<<endl;
else if(sum>t)
{
int k=sum-t;
int l;
for(int i=0; i<n; i++)
s[i]=s1[i];
for(int i=0; i<n; i++)
{
if(flag[i]==true)
{
s[i]=s1[i];
k--;
}
if(k<=0)
{
l=i;
break;
}
}
k=sum-t;
///cout<<l<<"++"<<k<<endl;
for(l=l+1; l<n; l++)
{
if(flag[l]==true)
{
s[l]=s2[l];
//cout<<s[l]<<endl;
k--;
}
if(k<=0) break;
}
///cout<<l<<"++"<<endl;
for(l=l+1
; l<n; l++)
{
if(flag[l]==false)
goto endw;
char x,y;
///cout<<"kkk"<<endl;
if(s1[l]>s2[l])
x=s2[l],y=s1[l];
else
x=s1[l],y=s2[l];
s[l]=x-1;
if(s[l]>='a')
{
goto endw;
}
s[l]=y+1;
if(s[l]<='z')
{
goto endw;
}
s[l]=x+1;
endw:
;
}
}
else
{
for(int i=0; i<n; i++)
{
if(flag[i]==false)
{
s[i]=s1[i];
}
else
{
char x,y;
if(s1[i]>s2[i])
x=s2[i],y=s1[i];
else
x=s1[i],y=s2[i];
s[i]=x-1;
if(s[i]>='a')
{
t--;
goto endW;
}
s[i]=y+1;
if(s[i]<='z')
{
t--;
goto endW;
}
s[i]=x+1;
t--;
if(t<=0) break;
}
endW:;
}
///cout<<t<<"__"<<endl;
if(t>0)
{
for(int i=0; i<n; i++)
{
if(flag[i]==false)
{
s[i]=s1[i]+1;
if(s[i]>'z')
s[i]=s1[i]-1;
t--;
}
if(t<=0) break;
}
}
}
cout<<s<<endl;
return 0;
}
