【题解】P7949 [✗✓OI R1] 左方之地

题目传送门

正解

思路

n 的特殊值:

\(n=0\)

  • 此时,只有一个数,所以 k 是多少并不能对它造成限制,直接输出即可。

\(n=1\)

  • 此时,有两个数,且这两个数是 0 和 1 ,所以 k 只能等于 1 。

此后,不妨假设 \(n \ge 2\)

无解情况

事实上,它有解当且仅当 \(n>k\) 且 \(k \mod 2 =1\) (也就是 k 为奇数)。

证明:

对于 \(n>k\)

  • 显然, \(n<k\) 无解很好理解

  • 但是 \(n=k\) 的时候,为什么无解呢?

  • 这个其实也好理解,因为如果 \(n=k\) ,就要求相邻两个元素完全取反,所以这种情况合法当且仅当 \(n=1\) ,而现在已经假设了 \(n \ge 2\) ,所以它无解

  • 为什么成立了就有解呢?这个其实也不一定,它只作为其中一个限制条件,剩下的看下面。

对于 \(k \mod 2 =1\)

  • 如果 k 为偶数,不难发现,每两个数之间的 \(popcount\) 一定相差偶数个,即奇偶性相同,这时候,只能保证出现所有 \(popcount\) 奇偶性相同的数,对于不同的数则不可能出现,然后就 GG 了。

  • 反之,则可以一奇一偶交替覆盖,便有解了。

如何构造

这里,不妨先假设 \(n=k+1\)

然后怎么做呢?

Step 1

  • 首先,构造一个格雷码 \(a_1\sim a_{...} \sim a_{2^n}\)

  • 怎么构造呢?很简单:

a[i]=i^(i>>1)
  • 为什么?我也不知道 QWQ

  • 反正它对就是了~

Step 2

  • 注意到,格雷码中每两位之间有且仅有一位不同,即 \(n-1\) 位相同,将每一个下标为偶数的元素取反 ( \(\oplus 2^n-1\) ),就变成了 \(n-1\) 位不同,而我们已经假设 \(n=k+1\) ,所以此时任意两位之间都有 \(k\) 位不同,符合题意。

Step 3

  • 对于每个 \(a_i\) ,将其 \(\oplus 2^n+2^{k-1}-1\) ,得到 \(c_1 \sim c_{...} \sim c_{2^n}\),其中, \(2^n\) 意味着最高位的取反,而 \(2^{k-1}-1\) 则意味着最后 \(k-1\) 位的取反,这样,刚好有 \(k\) 位变得相反。

  • 然后,把每个 \(c_i\) 倒序拼到 a 序列的后面,得到的就是 n 再增大 1 的答案。

  • 正确性:

  • 首先,c 序列只是将最后 \(k-1\) 位取反,这意味着该覆盖到的还是覆盖到了。

  • 其次,c 序列将最高位取反,这意味着它覆盖了 n 再增大 1 的答案的另一部分,保证了不重不漏地覆盖每一个数。

  • 然后,不断按照此操作进行覆盖,直到 \(n\) 符合数据要求即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,now; 
int a[3050000],c[3050000];
int main(){
	scanf("%d%d",&n,&k);
	if(n==0){printf("1\n0\n");return 0;}
	if(n==1){if(k==1) printf("1\n0 1\n");else printf("0\n");return 0;}
	if(k>=n||!(k&1)){printf("0\n");return 0;	}
	printf("1\n");
	now=k+1;
	for(int i=0;i<(1<<now);++i) a[i]=i^(i>>1);//格雷码公式
	for(int i=0;i<(1<<now);++i,++i) a[i]^=((1<<now)-1);//将偶数位取反
	for(;now<=n;++now){
		for(int i=0;i<(1<<now);++i)
			c[i]=a[i]^((1<<now)+(1<<(k-1))-1);//按照上面进行取反
		for(int i=0;i<(1<<now);++i)
			a[(1<<now)+i]=c[(1<<now)-i-1];//倒序拼接
	}
	for(int i=0;i<(1<<n);++i)
		printf("%d ",a[i]);
	printf("\n");
	return 0;
}
上一篇:C语言文件操作


下一篇:一次关于Spring Batch的实践