Codeforces 941 Div1 B

题目链接：Codeforces 941 Div1 B

思路

由于a序列的大小不超过25，想到二进制讨论。

求出i为$2^i $小于等于k的最大i。

已知当a序列$ a_i $=$2^{i+1} $时，每个数都能被表示。

故可先将a数组确定为[$1$，$2$，$4$…$2^{i-1}$，,….$2^{22}$]。

其中对$2^{i-1}$到$2^{i+1}$进行研究。

可先加入元素$k-2^i$，那么对于1到k-1，均可由1到$2^{i-1}$及$k-2^i$表示。

再加入元素$k+1$，那么对于$k+1$到$2^{i+1}+k$，均可由$k+1$与之前的元素表示（$k+1>2^i$且之前的元素和最大为$k-1$，$2k>=2^{i+1}$）。

最后讨论$2^{i+1}+k$，这个元素需要由$2^{i+1}$与k来表示，由于原序列中不能表示k，故需要新增元素。经过分析，当增加$k+1+2^i$时，可由$2^i+1+k$与$2^i-1$来表示。

故此时答案为[$k-2^i，k+1，k+1+2^i，1，2，4…2^{i-1}，2^{i+1}…2^{22}$]。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n,k;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin>>t;
	while(t--){
		cin>>n>>k;
		int i=0;
		while((1<<i)<=k){
			i++;
		}
		i--;
		cout<<23<<endl;
		cout<<k+1<<' '<<k-(1<<i)<<' ';
		for(int j=0;j<=20;j++){
			if(j!=i)cout<<(1<<j)<<' ';
		}
		cout<<endl;
	}

	return 0;
}