题解 | #War of Inazuma (Easy Version)#

H 题

前置知识

假设 A 、B相邻，A 二进制表示中 1 的个数为 x ，B 二进制表示中 1 的个数为 y
那么，y 必为 x+1 或 x-1（x = 0 时，y 只能为 x+1 ） 
因此，x 和 y 的奇偶性，必不同

思路

我们令，二进制表示中 1 的个数为偶数的顶点的属性为 ‘0’，反之为 ‘1’，便可以实现：
对于任意一个顶点 A ，与其相邻的顶点必与其属性不同

证明如下：
假设 A顶点、B顶点 相邻，且 A、B 的属性相同
不妨令，A 二进制表示中 1 的个数为 x ，B 二进制表示中 1 的个数为 y
那么 x 和 y 的奇偶性，必不同，因此 A、B的属性也必不同，这与假设矛盾
所以可证：此时，对于任意一个顶点 A ，与其相邻的顶点必与其属性不同

Code

#include <bits/stdc++.h>

using namespace std;

int lowbit(int x){
    return x & -x;
}

int cal_cnt(int x){ // 计算 x 二进制表示中 1 的个数
    int cnt=0;
    for(int i=x;i!=0;i-=lowbit(i)) cnt++;
    return cnt;
}

int main(){
    int n; cin>>n;

    for(int i=0;i<(1<<n);i++) 
        if(cal_cnt(i)&1) cout<<1;
        else cout<<0;

    return 0;
}