牛客多校10 War of Inazuma (Easy Version) 构造

牛客多校10 War of Inazuma (Easy Version) 构造 😊 | Powered By HeartFireY

Problem Description

题目大意：给定一个 n n n​​维立方体，共有 2 n 2^n 2n​​​个节点。如果在立方体上两个节点相连，那么要求两个点的二进制表示有且仅有一位不同。现在要求你构造一个 2 n 2^n 2n​长度的 01 01 01​​序列，表示每个点的颜色。要求每个点相邻的点中和这个点颜色相同的点的数目不超过 ⌈ n ⌉ \lceil{\sqrt{n}}\rceil ⌈n ​⌉​​​个。

首先分析每个点相邻点的情况：

我们可以得出规律，要是得构造的立方体定点分配满足题意，需要使得每个被染为 0 0 0​和 0 0 0​之间没有边，每个被染为 1 1 1​和 1 1 1​​之间没有边。对应到二进制的表示中去找规律：二进制表示中偶数个 1 1 1的填 0 0 0，奇数个 1 1 1填 1 1 1或者反过来亦可。

按照这个规律，不停的翻转 0 0 0和 1 1 1构造即可。

#include 
#define int long long
using namespace std;

const int N = 50000010;
char s[N];

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n = 0; cin >> n;
    s[0] = '0';
    for(int i = 1; i