自动搬运

查看原文

来自洛谷，原作者为

	xiaoqian02 小舟从此逝，江海寄余生。

搬运于2025-08-24 22:43:40，当前版本为作者最后更新于2023-01-29 20:23:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

第一部分：思路

首先明确一下，这题是构造题。

限制很宽泛，构造也就很憨批。——选自 P8846

不过，这道题的构造没 P8846 憨批，还是要多用点脑子的。

第一步：构造

首先，一定要有 $2$ 个 $1$。不然最少是 $2$，这样还需要 $3$ 来凑出答案 $2$（$2=3+3-2-2$），可是这样又凑不出 $8$……这样拼拼凑凑的看起来不好，实际写起来也麻烦。构造有规律也能方便后面的确定正负。

第一个是 $1$，后面接 $3$ 最优。接 $2$ 能达到的，接 $3$ 也能达到，且接 $3$ 能凑出 $8$（$8=1+3+3+3$）。如果接 $4$，虽然最大能凑出 $10$，但 $4$ 就凑不出了。

同理，接下来是 $9,27,81,...$

所以规律出来了：每组 $2$ 个，第 $i$ 组是 $3^{i-1}$。

但是，如果直接这样会全 WA 掉。因为 $3^{19}$ 达到了 $1162261467$，超过了题目给的 $1 \le a_i \le 10^9$。

有两种方法：一是把它扔了（剩下加起来还有 $3^{19}-1$，范围足够)，二是输出 $10^9$。本篇题解里采用的是第二种，但是建议用第一种，这样更简洁。

这样，构造部分就完成了。

第二步：判断正负号

这一部分比较麻烦，但我们可以先做一点处理。

因为 $X$ 是偶数，所以我们将其除以 $2$。每 $2$ 个构造数据也可以看作 $1$ 个。具体来说：

• 如果加这个数，则输出 ++。

• 如果减这个数，则输出 --。

• 如果不使用这个数，则输出 +-（或者 -+ 也可以）。

实际上，用 $1,3,9,27,...$ 这些数，可以不用，添加正负号，可以不重不漏地得到给定数字之和以下的正整数（比如给 $1,3,9$，就可以做到 $13$ 以下）。

接下来，就是怎么排的问题。有一种巧妙的方法：三进制。但是这种三进制比较特殊。

首先，将 $\frac{X}{2}$ 转成三进制。

然后，从个位开始看每一位。

• 先加上下面传上来的进位（具体进位机制在下面）。

• 如果当前位为 $0$，说明这个数不用。

• 如果当前位为 $1$，说明加这个数。

• 如果当前位为 $2$，这意味着要用 $2$ 个，但是我们只有一个数。考虑将当前位设为 $-1$，向上进位。这也等同于减去这个数再加上这个数的 $3$ 倍，符合要求。

• 最后，如果当前位为 $3$，同样向上进位，并将当前位设为 $0$。

对于每一位，按上面的规则对应输出即可。

这样，这道题就解决了。

第二部分：代码

#include<bits/stdc++.h>
using namespace std;
void IOS()//cin 优化
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
typedef long long ll;//开 long long 保险一点
ll m,q,p;
ll pw3[25];//存储 3 的幂次
int main()
{
	IOS();
	cin>>m>>q;
	pw3[1]=1;
	for(ll i=2;i<=20;i++) pw3[i]=3*pw3[i-1];
	cout<<40<<endl;
	for(ll i=1;i<=40;i++)
		cout<<min(pw3[(i+1)>>1],(ll)(1000000000))<<" ";
        //这里用的是第二种方法，第一种方法就是只构造 38 个数
	cout<<endl;
	while(q--)
	{
		cin>>p;
		ll ad=0;//ad 存进位
		p/=2;
		for(ll i=1;i<=20;i++)
		{
			ll kkk=p%3+ad;
			ad=0;
			if(kkk==2)
			{
				kkk=-1;
				ad=1;
			}
			if(kkk==3)
			{
				kkk=0;
				ad=1;
			}
			if(kkk==-1) cout<<"--";//减去
			else if(kkk==0) cout<<"+-";//不用
            else cout<<"++";//加上
			p/=3;
		}
		cout<<endl;
	}
	return 0;
}