题解：AT_arc203_b [ARC203B] Swap If Equal Sum

· · 题解

一道十分有趣的题，建议自己想出来而不是看题解，因为看题解之后就会失去它绝大部分的快乐。

首先先判断是否相等，再判断最终能否到达相等的局面，这是平凡的。

我们需要发现一个十分有趣的交换方式：一个区间单取一个 1，另一个区间取一个 1 和它前面或后面的连续的一段 0。这个操作能让你在两个 1 之间随便移动 0。所以只要有两个 1 就能轻松转换。

随后我们考虑只有一个 1 的情况。现在我们只有一个 1，不能再使用上面的那个把戏了。没关系，我们还能再发现新的交换方式。

我们可以令一个区间单取一个 0，另一个区间取任意个 0。这种操作可以将任意个 0 移动到另一个有 0 的位置。所以，只要这个恼人的 1 不在序列的开头或结尾，那我们就能将一侧的 0 移动到另一侧使得两侧的 0 数量相等。

代码就是把这个照着写一遍。

// Problem: B - Swap If Equal Sum
// Contest: AtCoder - AtCoder Regular Contest 203 (Div. 2)
// URL: https://atcoder.jp/contests/arc203/tasks/arc203_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
bool startmb;
constexpr int N=2e5+5;
int _,n,sum,a[N],b[N];
bool endmb;
main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin>>_;
    while(_--)
    {
        cin>>n;
        int suma=0,sumb=0;
        for(int i=1;i<=n;i++) cin>>a[i],suma+=a[i];
        for(int i=1;i<=n;i++) cin>>b[i],sumb+=b[i];
        bool flag=1;
        for(int i=1;i<=n;i++) if(a[i]!=b[i]) flag=0;
        if(flag==1) cout<<"Yes\n";//不需要交换
        else if(suma==sumb)
        {
            if(suma>=2) cout<<"Yes\n";//1的个数大于等于2
            else
            {
                bool flag=1;
                for(int i=1;i<=n;i++) if(a[i]==1) if(i==1||i==n) flag=0;
                for(int i=1;i<=n;i++) if(b[i]==1) if(i==1||i==n) flag=0;
                //判断1的位置
                if(flag) cout<<"Yes\n";
                else cout<<"No\n";
            }
        }
        else cout<<"No\n";//无法相同
    }
    return 0;
}