CF1701B的题解

简单构造题。

很明显的，当 \(d=2\) 的时候代价最大。

证明：

\(\because p_i\cdot d=p_{i+1}\)

当 \(d\) 减小时，\(p_i\cdot d\) 也在减小，\(p_{i+1}\) 也在减小，

那么 \(p_{i+1}\) 减小时，\(p_{i+1}\) 可供选择的数就越多，代价也随即越大，

那么 \(d\) 在取最小值时，代价最大，

因为 \(p\) 是个排列，所以没有重复数字，所以 \(d\) 最小值为 \(1\)。

所以我们对于 \(d=2\) 来构造即可

#include<cstdio>
#include<cstring>
int t;
int n;
int a[200010];
bool vis[200010];
int tot;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		tot=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
			if(!vis[i])//如果这个数已经出现在排列中，由于排列的不重复性，所以不能选择该数
				for(int j=i;j<=n;j*=2)
				{
					a[++tot]=j;
					vis[j]=1;//标记，代表此数已出现在排列中
				}
		printf("2\n");
		for(int i=1;i<=n;i++) printf("%d ",a[i]);
		printf("\n");
	}
	return 0;
}