ARC182B |{floor(A_i/2^k)}| 题解

题目大意

定义一个长度为 \(N\) 的序列 \(A\) 的分数为 能被表示成 \(\lfloor {A_i\over2^k}\rfloor\) 的数的个数，其中 \(i=1,2,\dots,N\)，\(k\) 为任意自然数。

给定 \(N,K\)，求长度为 \(N\) 且元素大小都在 \(2^K-1\) 内的所有序列的分数的最大值，输出任意拥有最大分数的序列。

Solve

除以 \(k\) 下取整相当于二进制下右移 \(k\) 位，所以按位考虑。

显然有效位数越多越好，因为有效位数多的右移 \(k\) 位得到的数也更多。比如 \((101010)_2\) 右移得到的数是包含 \((01010)_2\) 能得到的数的。

所以序列中的数二进制下第 \(K-1\) 位一定是 \(1\)，接下来我们考虑怎么构造能使右移得到的不同的数更多。这里有一种构造方法：

1 0 0 0 ...
1 1 0 0 ...
1 0 1 0 ...
1 1 1 0 ...
1 0 0 1 ...
1 1 0 1 ...
1 0 1 1 ...
1 0 1 1 ...
1 0 0 0 ...
1 1 0 0 ...
1 0 1 0 ...
1 1 1 0 ...
...

即二进制位尽量交错着填，保证每一种情况都被考虑，比如第 \(K-4\) 位上填 \(0\) 的数中，第 \(K-2,K-3\) 位上填 \(1\) 或 \(0\) 的所有 \(4\) 种情况都被考虑到。

如此，我们能保证右移任意 \(k\) 位得到的数的个数都是卡满的。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	short f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1e5+10;
int T,n,m,a[N];
signed main()
{
	T=read();
	while(T--)
	{
		n=read();m=read();
		for(int i=1;i<=n;i=-~i)	a[i]=1<<m-1;
		for(int i=m-2;i>=0;i--)
		{
			bool f=0;
			for(int j=1;j<=n;j+=(1<<m-2-i),f^=1)
				for(int k=j;k<=min(j+(1<<m-2-i)-1,n);k=-~k)
					a[k]+=f<<i;
		}
		for(int i=1;i<=n;i=-~i)	printf("%d ",a[i]);
		putchar('\n');
	}
	return 0;
}