[牛客]2021牛客暑期多校训练营10

前言

近期打算补一下 牛客暑假多校,打算提升一波

传送门 :

E.War of Inazuma (Easy Version)

题意 : 题面较为复杂,大概意思是 对于一个超立方体,有 2 n 2^n 2n个节点,对于每一个节点当他们的二进制只有一位不同的时候,认为他们相邻,问使得相邻 0 , 1 0,1 0,1不超过 ( n ) \sqrt{(n)} (n) ​的方案

思路 :

设 x x x为一个数的二进制个数,另一个为 y y y

则如果这两个数相邻那么 y = x + 1 ∣ ∣ x − 1 y=x+1||x-1 y=x+1∣∣x−1,为了不超过 n \sqrt{n} n ​我们可以令偶数相邻为1,奇数相邻为 0 0 0即可

code

int lowbit(int x){return x&-x;}
int calc(int x){
	int res  = 0 ;
	while(x){
		x-=lowbit(x);
		res++;
	}
	return res;
}
void solve(){
	cin>>n;
	for(int i=0;i