2012-A3-0016

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：有一个L * W * H个立方体拼成的长方体，每个cube上有一个数字，每次可以将共面相邻两个数加减去一个相同的数，判断最后能否把所有cubes上的数变成0.

把每个格子（i,j,k)分成按i+j+k的奇偶性分成两类，如果两类的和相等就是可以，否则不行。

必要性：每次操作选取共面相邻的数，减去一个数，不改变两类的和的差。

充分性：如果两类的和相等，那么可以随机选取一组相邻的，都减去每类的和，那么这样每类的和就都是0了，

然后对于同一类中的两个数，随便找一条路径连接它们，它们的Manhattan距离必然是个偶数，沿路径正负交替操作加减同一个数，

可以实现同一类里面的2个数，分别+和-一个相同的数，由于每类的和是0，而每次这样的沿路径操作，都可以使这类中的数增加至少一个0，

这样最后可以分别把每类中的数都变成0.

{{{
#include<cstdio>
int main(){
    int l,w,h;
    for(bool ans;scanf("%d%d%d",&l,&w,&h)==3;puts(ans?"Yes":"No")){
        int a=0,b=0,t;
        for(int i=0;i<l;++i)
            for(int j=0;j<w;++j)
                for(int k=0;k<h;++k){
                    scanf("%d",&t);
                    if((i^j^k) &1){
                        a+= t;
                    }else{
                        b+=t;
                    }
                }
        ans = (a==b);
    }
}
}}}

题意：有一个L * W * H个立方体拼成的长方体，每个cube上有一个数字，每次可以将共面相邻两个数加减去一个相同的数，判断最后能否把所有cubes上的数变成0.

把每个格子（i,j,k)分成按i+j+k的奇偶性分成两类，如果两类的和相等就是可以，否则不行。

必要性：每次操作选取共面相邻的数，减去一个数，不改变两类的和的差。

充分性：如果两类的和相等，那么可以随机选取一组相邻的，都减去每类的和，那么这样每类的和就都是0了，

然后对于同一类中的两个数，随便找一条路径连接它们，它们的Manhattan距离必然是个偶数，沿路径正负交替操作加减同一个数，

可以实现同一类里面的2个数，分别+和-一个相同的数，由于每类的和是0，而每次这样的沿路径操作，都可以使这类中的数增加至少一个0，

这样最后可以分别把每类中的数都变成0.

#include<cstdio>
int main(){
    int l,w,h;
    for(bool ans;scanf("%d%d%d",&l,&w,&h)==3;puts(ans?"Yes":"No")){
        int a=0,b=0,t;
        for(int i=0;i<l;++i)
            for(int j=0;j<w;++j)
                for(int k=0;k<h;++k){
                    scanf("%d",&t);
                    if((i^j^k) &1){
                        a+= t;
                    }else{
                        b+=t;
                    }
                }
        ans = (a==b);
    }
}