「DAOI R1」Magic 题解

Erinyes · 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 次操作，即可得到：

假如剩下的数为 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 时，我们可以将 1 和 k 对 0 进行一次操作，将数列变为：

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

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

这时，若 (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 对 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，所以需要特殊考虑。

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

综上，当原数列排序后不为 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;
}