P7022 [NWRRC2017] Dividing Marbles

· · 题解

本篇题解参考 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。

现在有两条性质：

考虑 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;
}