自动搬运

查看原文

来自洛谷，原作者为

	Erinyes 压力诺？

搬运于2025-08-24 22:37:39，当前版本为作者最后更新于2022-04-12 16:08:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

来自出题人的题解。

这道题我们采用分类讨论的思想。

$n\le2$：

当 $n=1$ 时，一定可以实现。

当 $n=2$ 时，如果不是其中一个为 $0$，就不能实现。

if(n==1) puts("YES");
if(n==2){
	if(a[1]==0 || a[2]==0) puts("YES");
	else puts("NO");
}

$n=3$：

我们可以将这个数列表示为 $a_1,a_2,a_3$。

首先将这个数列升序排序。

那么就可以将三个数变成 $0$ 和另外两个数。

具体过程：

$$a_1,a_2,a_3$$

将 $a_1$ 和 $a_2$ 对 $a_3$ 执行 $a_1$ 次操作，即可得到：

$$0,(a_2-a_1),(a_3+a_1\times2)$$

假如剩下的数为 $0,x,y$ $(x<y)$。

我们将 $x$ 和 $y$ 各减去 $1$，再将 $0$ 加上 $2$，就会变成 $2,(x-1),(y-1)$。

再将 $2$ 和 $x-1$ 对 $y-1$ 执行两次操作，就会变成 $0,(x-3),(y+3)$。

由此在不改变 $a_1$ 为 $0$ 的情况下，每次可以将 $x$ 减去 $3$，再将 $y$ 加上 $3$。

• 如果 $x\bmod3$ 为 $0$，则最后肯定可以使 $x$ 变成 $0$，并把 $y$ 变成 $x+y$。

• 如果 $x\bmod3$ 不为 $0$，那么肯定可以使用刚才的方式将原数列变为：

这里的 $k$ 表示为操作完的 $y$ 值，对结果不影响。

$$0,1,k$$

或者

$$0,2,k$$

当数列是 $0,1,k$ 时，我们可以将 $1$ 和 $k$ 对 $0$ 进行一次操作，将数列变为：

$$2,0,(k-1)$$

这时，若 $(k-1)\bmod3$ 为 $0$，则可以像之前的方法将 $2$ 和 $k-1$ 进行操作，所以可以。

当数列是 $0,2,k$ 时，我们也可以将数列变为：

$$4,0,(k-2)$$

这时，若 $(k-2)\bmod3$ 为 $0$，则可以像之前的方法将 $4$ 和 $k-2$ 进行操作，所以可以。

上面两种方法一个满足 $x\bmod3$ 为 $1$ 且 $y\bmod3$ 为 $1$，另一个满足 $x\bmod3$ 为 $2$ 且 $y\bmod3$ 为 $2$，总结出来就是 $(x+y)\bmod3$ 不为 $0$。

所以当满足上述条件之一是时一定可以实现，否则不行。

注意：$x$ 和 $y$ 可以互换

if(n==3){
	sort(a+1,a+n+1);
	a[3]+=a[1]*2; a[2]-=a[1]; a[1]=0;
	if(a[2]%3==0 || a[3]%3==0) puts("YES");
	else if((a[2]%3==1 && a[3]%3==1) || (a[3]%3==1 && a[2]%3==1)) puts("YES");
	else if((a[2]%3==2 && a[3]%3==2) || (a[3]%3==2 && a[2]%3==2)) puts("YES");
	else puts("NO"); 
}

$n=4$：

对于这种情况，我们可以用类似于 $n=3$ 的方法将数列变成 $0,0,x,y$。

具体方法：先对整个序列进行升序排序，然后对于每一个 $i$ $(2\le i<n)$，可以将 $a_{i-1}$ 和 $a_i$ 对 $a_{i+1}$ 进行 $a_{i-1}$ 次操作，将 $a_{i-1},a_i,a_{i+1}$ 变成 $0,(a_i-a_{i-1}),(a_{i+1}+a_{i-1}\times 2)$。

转换完后，我们可以先将 $x$ 和 $y$ 对第一个 $0$ 和第二个 $0$ 各进行一次操作，将序列变成：

$$2,2,(x-2),(y-2)$$

然后我们再将两个 $2$ 对 $y-2$ 进行两次操作，将序列变成：

$$0,0,(x-2),(y+2)$$

所以我们可以在不改变前面两个 $0$ 的情况下，将 $x$ 减去 $2$，并将 $y$ 加上 $2$。

由于我们在 $n=3$ 的情况下已经证明了可以将 $x$ 减去 $3$，并将 $y$ 加上 $3$，所以问题就转化成了每次可以将 $x$ 减去 $2$ 或 $3$，问能不能将 $x$ 减到 $0$。

• 当 $x\bmod2$ 为 $0$ 时，直接进行 $\dfrac{x}{2}$ 次减 $2$ 操作。

• 当 $x\bmod2$ 为 $1$ 时，先进行一次减 $3$ 操作，再进行 $\dfrac{n-3}{2}$ 次减 $2$ 操作。

按照以上的推论，当 $n=4$ 时，是一定能实现的，但如果我们要进行减 $2$ 操作，$x$ 必须要大于等于 $2$，所以需要特殊考虑。

• $x=1,y=1$：将 $x$ 和 $y$ 对另一个 $0$ 进行一次操作即可。

• $x=1,y=2$：$x$ 进行不了操作，并且将 $y$ 进行减 $2$ 操作时 $x$ 会减到负数去，所以这个特例是不能实现的。

• $x=2,y=2$：同 $x=1,y=1$，两次操作即可。

同样的，如果我们要进行减 $3$ 操作，$x$ 必须要大于等于 $3$，也需要特殊考虑。

• $x=1,y=3$：将 $x$ 和 $y$ 对一个 $0$ 进行一次操作，再将得到的 $2$ 和 $y(2)$ 对剩下一个 $0$ 进行两次操作即可。

• $x=2,y=3$：将 $x$ 进行一次减 $2$ 操作即可。

• $x=3,y=3$：同 $x=1,y=1$，进行三次操作。

综上，当原数列排序后不为 $0,0,1,2$ 时，就可以实现，否则不行。

$n>4$：

当 $n>4$ 时，也可以用类似的方法将原数列变为 $0,0,...,0,x,y$ 的形式，然后按照 $n=4$ 时的操作方法进行操作，所以类似的，当原数列排序后不为 $0,0,...,0,1,2$ 时一定可以实现，否则不行。

其实我们没必要排序，只用统计 $0,1,2$ 出现的次数即可。

if(n>=4){
	int cnt0=0,cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		if(a[i]==0) cnt0++;
		else if(a[i]==1) cnt1++;
		else if(a[i]==2) cnt2++;
	}
	if(cnt0==n-2 && cnt1==1 && cnt2==1) puts("NO");
	else puts("YES");
}

Code：

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,a[maxn];
int main(){
	int T; scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		if(n==1) puts("YES");
		if(n==2){
			if(a[1]==0 || a[2]==0) puts("YES");
			else puts("NO");
		}
		if(n==3){
			sort(a+1,a+n+1);
			a[3]+=a[1]*2; a[2]-=a[1]; a[1]=0;
			if(a[2]%3==0 || a[3]%3==0) puts("YES");
			else if((a[2]%3==1 && a[3]%3==1) || (a[3]%3==1 && a[2]%3==1)) puts("YES");
			else if((a[2]%3==2 && a[3]%3==2) || (a[3]%3==2 && a[2]%3==2)) puts("YES");
			else puts("NO"); 
		}
		if(n>=4){
			int cnt0=0,cnt1=0,cnt2=0;
			for(int i=1;i<=n;i++){
				if(a[i]==0) cnt0++;
				else if(a[i]==1) cnt1++;
				else if(a[i]==2) cnt2++;
			}
			if(cnt0==n-2 && cnt1==1 && cnt2==1) puts("NO");
			else puts("YES");
		}
	}
	getchar(); getchar();
	return 0;
}