自动搬运

查看原文

来自洛谷，原作者为

	Vct14 **

搬运于2025-08-24 23:16:32，当前版本为作者最后更新于2025-06-06 04:32:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

构造好玩捏！

我们发现通过增量操作我们可以轻易地将一个数翻倍。所以考虑递归当前数应为多少。但是如果当前数 $k$ 是奇数的话其无法通过翻倍得到，而翻出 $k-1$ 之后再加一也不好处理。于是考虑一开始就将所有 $a_i$ 均赋为 $1$。如此若 $k$ 为奇数，可以直接递归 $\dfrac {k-1}2$；否则在递归前先将当前 $a_i$ 赋为 $2$，然后递归 $\dfrac{k-2}2$。

可以发现每次递归实质上是消去了 $k$ 的一个二进制位，最终目标为 $1$ 位（即 $1$）。而 $k$ 最多有 $\left\lfloor\log_2 10^{18}\right\rfloor+1=60$ 位，因此需要的最大 $a$ 数组大小约为 $60<100$，操作次数 $s<99+(60-1)\times3=276<300$。因此这样构造是正确的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define add op.push_back(i)

vector<int> op;
void work(int i,int k){
	if(k==1) return ;
	if(k==2){add;return ;}
	if(!(k%2)) add;
	work(i+1,(k-1)/2); // k 为偶数时，(k-2)/2==(k-1)/2
	add;add; // 将 a_i 赋值为 $a_{i+1}*2
}

signed main(){
	int t,g;cin>>t>>g;
	while(t--){
		op.clear();
		int n;cin>>n;
		for(int i=99; i>=1; i--) add;
		work(1,n);
		cout<<op.size()<<"\n";
		for(int x : op) cout<<x<<" "; 
		cout<<"\n";
	}
	return 0;
}