A
如果 \(S\) 和 \(T\) 的某一位相同，那么 \(U\) 无论怎么填都无法影响答案，为了字典序最小，一定填 \(0\)。
只考虑 \(S\) 和 \(T\) 不同的位置，假设有 \(k\) 位不同，易知 \(k\) 为奇数一定无解。
如果 \(k\) 为偶数，那么 \(U\) 数组可以视为在 \(S\) 数组上修改了 \(k/2\) 位。考虑如何修改才能让字典序最小。
一定是把 \(S\) 前面的 \(1\) 都换成 \(0\)。当然，如果 \(k/2\) 次用不完，还得被迫把后面的一些 \(0\) 改成 \(1\)。
讲的比较抽象，具体看代码。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,s[N],t[N],ans[N];
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
char ch;cin>>ch;
s[i]=ch-'0';
}
for(int i=1;i<=n;++i)
{
char ch;cin>>ch;
t[i]=ch-'0';
}
int cnt=0;
for(int i=1;i<=n;++i)
if(s[i]!=t[i])cnt++;
if(cnt%2==1)cout<<-1<<endl;
else
{
int cur=0;
for(int i=1;i<=n;++i)
{
if(s[i]==t[i])ans[i]=0;
else //不同的地方
{
if(s[i]==1)
{
if(cur<cnt/2)ans[i]=0,cur++;
else ans[i]=1;
}
else ans[i]=0;
}
}
int res=cnt/2-cur;
if(res>0)
{
for(int i=n;i>=1;--i)
{
if(s[i]!=t[i])
{
if(s[i]==0&&ans[i]==0)
{
ans[i]=1;res--;
if(res==0)break;
}
}
}
}
for(int i=1;i<=n;++i)cout<<ans[i];
}
return 0;
}