P8913 题解

· · 题解

第一部分：思路

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

限制很宽泛，构造也就很憨批。——选自 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} 转成三进制。

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

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

这样，这道题就解决了。

第二部分：代码

#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;
}