题解：AT_arc203_b [ARC203B] Swap If Equal Sum

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

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

我们需要发现一个十分有趣的交换方式：一个区间单取一个

1

，另一个区间取一个

1

和它前面或后面的连续的一段

0

。这个操作能让你在两个

1

之间随便移动

0

。所以只要有两个

1

就能轻松转换。

随后我们考虑只有一个

1

的情况。现在我们只有一个

1

，不能再使用上面的那个把戏了。没关系，我们还能再发现新的交换方式。

我们可以令一个区间单取一个

0

，另一个区间取任意个

0

。这种操作可以将任意个

0

移动到另一个有

0

的位置。所以，只要这个恼人的

1

不在序列的开头或结尾，那我们就能将一侧的

0

移动到另一侧使得两侧的

0

数量相等。

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

CPP

// 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;
}

题解：AT_arc203_b [ARC203B] Swap If Equal Sum

文章操作

相关推荐

评论

题解：AT_arc203_b [ARC203B] Swap If Equal Sum