自动搬运

查看原文

来自洛谷，原作者为

	2020HZ06 **

搬运于2025-08-24 22:25:57，当前版本为作者最后更新于2024-10-29 21:08:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本篇题解参考 https://www.cnblogs.com/vb4896/p/9489338.html 在此致谢。

注意拆分后得到的数会去重。因此有一个方案是假设 $n$ 有 $s$ 位而其中有 $t$ 位 $1$。那么可以每次拆出 $\operatorname{lowbit(n)}$ 并让 $n-\operatorname{lowbit(n)}\to n$。拆成若干 $2^k$ 之后从最高位不停 $/2$ 并去重最终即可达到 $1$。代价 $s+t-2$。这是答案的上界。

这个过程可以视作加法链，$a_i=a_j+a_k(j,k<i),a_0=1,a_m=n$，求最短加法链长度 $m$。

然而有时候不是这样。$15=(1111)_2$，$[1,2,3,6,9,15]$ 加法链长度只有 $s+t-3=5$。而 $s+t-2=4+4-2=6$。

现在有两条性质：

• $a_i\ge \frac{a_{i+1}}2$，显然。不然 $a_i$ 拼不出来。
• $a_i\ge 2^{i-t+1}$。因为 $m \le s+t-2$。得到 $m-t+1\le s-1$，又因为 $a_m=n\ge 2^{s-1}$，两边同时作为指数，得到 $a_m\ge 2^{m-t+1}$，由性质一得 $a_i\ge 2^{i-t+1}$，$t\le 4$，$a_i\ge 2^{i-3}$。

考虑 $m=s+t-2$ 可以直接构造，只需搜索 $m\le s+t-3$ 的情况即可。类似的有 $a_i\ge 2^{i-t+2}\ge 2^{i-2}$。直接搜即可。

接下来有几种搜索方法：

方法一：每组数据搜索，枚举 $i+1$ 位置填什么，最优性和可行性剪枝。

很遗憾，

1
13 17 19 20

直接能把它卡 T 飞。

方法二：枚举值域太傻，枚举当前链中元素暴力组合。由于元素是 $O(\log n)$ 量级，单组数据能很快出解。

然而 $T=500$ 会导致 TLE on test 2。

方法三：只进行一次 DFS 预处理出所有数的答案。注意 $n$ 的 $1$ 的个数不超过 $4$。另外还可以发现一条性质：

每次往链中加元素时 $a_i=a_{i-1}+a_k(k<i)$ 一定成立。因为 $a_{i-1}$ 如果拼出来却暂时不用完全可以到后面用到再拼。

举个例子，假设现在链中元素 $1,2$。要拼出 $7$，一种方案是 $[1,2,3,4,7](7=3+4,4=2+2,3=1+2)$。但是我们也可以 $[1,2,4,6,7],(4=2+2,6=2+4,7=6+1)$。也就是说，$a_{i-1}=x+y$，$a_j+a_{i-1}=a_k(i-1<j<k)$ 完全可以把 $x,y$ 的累加贡献后移变成 $(a_j+x)+y=a_k$，次数不变。

因此直接枚举 $a_j+a_{i-1}(j<i)$ 扩展即可。只需一重循环。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
int T,d1,d2,d3,d4,n,s,t;
int a[35];
vector<int>ans[4*(1<<20)+5],v;
void dfs(int nw){
	if(nw>=25||(nw>=2&&a[nw]<(1<<nw-2))) return;//24=max(s+t-3)=23+4-3
	if(__builtin_popcount(a[nw])<=4&&(!ans[a[nw]].size()||ans[a[nw]].size()>nw)){//更新答案
		ans[a[nw]].clear();
		for(int i=0;i<=nw;i++) ans[a[nw]].pb(a[i]);
	}
	for(int i=0;i<=nw;i++){//扩展
		a[nw+1]=a[nw]+a[i];
		if(a[nw+1]<=(1<<22)) dfs(nw+1);
		else break;
	}
}
int main(){
	scanf("%d",&T);
	a[0]=1;
	dfs(0);
	for(int i=1;i<=(1<<22);i++){
		if(__builtin_popcount(i)<=4&&!ans[i].size()){//答案为 s+t-2
			for(int j=0;(1<<j)<=i;j++) ans[i].pb(1<<j);
			v.clear();
			int u=i;
			while(u!=(u&-u)) v.pb(u),u-=(u&-u);
			for(int j=v.size()-1;j>=0;j--) ans[i].pb(v[j]);//倒着插回去
		}
	}
	while(T--){
		scanf("%d%d%d%d",&d1,&d2,&d3,&d4);
		n=(1<<d1)+(1<<d2)+(1<<d3)+(1<<d4);
		printf("%d\n",ans[n].size()-1);
		for(int i=ans[n].size()-1;i>0;i--) printf("%d %d %d\n",ans[n][i],ans[n][i-1],ans[n][i]-ans[n][i-1]);//直接相减构造答案
	}
	return 0;
}