AT_arc203_b [ARC203B] Swap If Equal Sum 题解

· · 题解

很有趣的题目。

首先有一个无解的情况很好判断：A 中 1 的数量和 B 中的不同。

接下来分析性质。经过若干次手玩后，我们发现让 \{1,0\} 和 \{1\} 交换似乎很有性质。仔细观察可以发现，这样的交换等价于将 1 往左或者往右调。

所以我们总是可以把 A 变成 B。

但是这样的操作需要两个 1，如果只有一个 1 怎么办呢？

此时我们发现，我们可以通过交换 \{0,0\} 和 \{0\}，使我们的 1 移动。

我们发现，如果 1 在边界上，它是不能移动的。同理，这个 1 也不能移动到边界上。

所以，如果 A 上面的 1 在边界上（B 上面的同理），就不能将 A 变成 B。

当然，要特判掉 A 数组和 B 数组本来就相同的情况。

知道这些后，代码还是不难写的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
const int mod=998244353;
const int INF=0xc0c0c0c0c0c0c0c0;
int n,m;
int a[N],b[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    int s=0;
    for(int i=1;i<=n;i++)s+=a[i];
    for(int i=1;i<=n;i++)s-=b[i];
    if(s){//1数量不相同
        cout<<"No\n";
        return;
    }
    int fl=1;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]){
            fl=0;
        }
        cnt+=a[i];
    }
    if(fl==1){//本身相同
        cout<<"Yes\n";
        return;
    }
    if(cnt==1){//仅有1个'1'
        int tot=0;
        for(int i=2;i<n;i++){
            if(b[i]==1){
                tot++;
            }
            if(a[i]==1){
                tot++;
            }
        }
        if(tot==2)cout<<"Yes\n";//都不在边界上
        else cout<<"No\n";
        return;
    }
    else cout<<"Yes\n";//多个'1'
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}
/*

*/