题意

有一个非空可重整数集合 $S$，$T$ 表示其所有子集（包含空集）的和。给出 $T$，让你还原出排序后字典序最小的 $S$。

$|S| \le 60,~\text{T 中不同数值数量} \le 10^4,~|S_i| \le 10^{10}$

题解

将 $T$ 中最大值与次大值相减得到 $p$，不难发现 $S$ 中一定存在一个元素满足其绝对值为 $p$。

我们无法直接判断其在 $S$ 中的正负号，但是不难发现当其为 $+p$ 加入 $S$ 时 $f[i]=f[i]+f[i-p]$，当其为 $-p$ 时 $f[i]=f[i]+f[i+p]$，所得到的两个 $f$ 数组仅存在下标偏移的区别，不存在数值上的差别。因此我们可以钦定其在 $S$ 中即为 $+p$。

通过上述钦定所有数均为正数的方式，在经过 $|S|$ 轮操作后可以得到一个不一定正确的 $S$，且此时 $T$ 中只剩下一个元素。对于合法的 $S$ 构造，$T$ 中剩下的元素一定为 $0$（其代表空集）。但是由于我们得出的 $S$ 不一定正确，所以最终的元素 $x$ 不一定等于 $0$。我们发现每将一个 $-p$ 错误地钦定为 $+p$ 会使序列与正确序列产生 $p$ 的偏移。因此我们需要从集合 $S$ 中取出若干个元素使得他们的和为 $|x|$，并将他们符号改为负号，得到正确的 $S$。

由于需要让排序后字典序最小化，最后一步将所有元素从大到小排序后贪心尽可能选靠前的元素取反即可。

时间复杂度 $O(|S| \times |T| \times \log |S|)$。

代码

由于真正可能出现的子集和数量在 $10^4$ 规模内，因此这里使用 map 代替数组进行转移。

/**
 * @author Macesuted (macesuted@outlook.com)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {
// fread
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 10005
#define maxm 65

typedef pair<long long, long long> pll;

pll a[maxn];
long long b[maxn];
map<long long, long long> S;
vector<set<long long>> f;

int main() {
    int _ = read<int>();
    for (int __ = 1; __ <= _; __++) {
        putstr("Case #"), write(__), putch(':');
        int n = read<int>();
        long long cnt = 0;
        for (int i = 1; i <= n; i++) a[i].first = read<long long>();
        for (int i = 1; i <= n; i++) a[i].second = read<long long>(), cnt += a[i].second;
        S.clear();
        for (int i = 1; i <= n; i++) S.insert(a[i]);
        int m = log2(cnt);
        for (int i = 1; i <= m; i++) {
            long long p1 = (--S.end())->first, p2 = (S[p1] > 1 ? p1 : (----S.end())->first), p = abs(p1 - p2);
            b[i] = p;
            vector<long long> cache;
            for (auto j : S) {
                if (j.second == 0) cache.push_back(j.first);
                if (S.find(j.first + p) == S.end()) continue;
                if (p == 0)
                    S[j.first] >>= 1;
                else
                    S[j.first + p] -= j.second;
            }
            for (auto j : cache) S.erase(j);
        }
        long long delta = abs(S.begin()->first);
        sort(b + 1, b + m + 1, greater<long long>());
        f.resize(m + 2);
        f[m + 1].insert(0);
        for (int i = m; i; i--)
            for (auto j : f[i + 1])
                f[i].insert(j), f[i].insert(j + b[i]);
        long long pre = 0;
        for (int i = 1; i <= m; i++)
            if (f[i + 1].find(delta - pre - b[i]) != f[i + 1].end())
                pre += b[i], b[i] = -b[i];
        f.clear();
        sort(b + 1, b + m + 1);
        for (int i = 1; i <= m; i++) putch(' '), write(b[i]);
        putch('\n');
    }
    return 0;
}

标程分析

应教练要求解释一下标程。

思路基本相同，但是标程没有使用 map 或是 set 之类的容器存储信息，而是将可能出现的值提前记录，采用 lower_bound 查找元素对应下标。

#include<bits/stdc++.h>
using namespace std;
const int N=10010,S=66;
struct sum
{
    long long s,t,d;
}a[N]={};
bool sum_cmp(const sum &s1,const sum &s2) { return s1.s<s2.s; }
int n,tot=0,f[S][N]={},now=0;
long long s=0,v[N]={},ans[S]={};
void init()
{
    tot=0;
    ++now;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i].s;
        v[i]=-a[i].s;
        a[i].d=0;
    }
    for(int i=1;i<=n;++i)
        cin>>a[i].t;
    s=0;
    for(int i=1;i<=n;++i)
        s=min(s,a[i].s);
    s=-s;
    sort(a+1,a+n+1,sum_cmp);
    sort(v+1,v+n+1);
}
void get_element()
{
    long long d=a[n].s-a[n-1].s;
    ans[++tot]=d;
    for(int i=n;i>=1;--i) // 删去元素 d 对答案产生的影响
    {
        int p=lower_bound(a+1,a+n+1,(sum){a[i].s+ans[tot],0,0},sum_cmp)-a;
        if(a[p].s!=a[i].s+ans[tot])
            continue;
        long long b=min(a[i].t-a[i].d,a[p].t-a[p].d);
        a[i].d+=b,a[p].t-=b; // a[i].d 为转移后的数组，a[i].t 为转移前的数组
    }
    int pos=0;
    for(int i=1;i<=n;++i)
        if(a[i].d)
            a[++pos]=(sum){a[i].s,a[i].d,0};
    n=pos;
}
long long gcd(long long a,long long b)
{
    return b ? gcd(b,a%b) : a;
}
void remove_zero()
{
    long long g=a[1].t;
    for(int i=2;i<=n;++i)
        g=gcd(g,a[i].t);
    while(g%2==0)
    {
        for(int i=1;i<=n;++i)
            a[i].t/=2;
        ans[++tot]=0;
        g/=2;
    }
}
void work()
{
    int tmp=n;
    remove_zero(); // 将 S 中所有存在的 0 取出
    while(n!=1)
        get_element(); // 找出其余元素的绝对值
    n=tmp;
    sort(ans+1,ans+tot+1);
    f[0][lower_bound(v+1,v+n+1,0)-v]=now;
    for(int i=1;i<=tot;++i)
    { // 处理 f[i][j]，表示前 i 个数是否存在和为 v[j] 的子集
        for(int j=1;j<=n;++j)
            if(f[i-1][j]==now)
                f[i][j]=now;
        for(int j=n;j>=1 && v[j]>=ans[i];--j)
        {
            int p=lower_bound(v+1,v+n+1,v[j]-ans[i])-v;
            if(v[p]==v[j]-ans[i] && f[i-1][p]==now)
                f[i][j]=now;
        }
    }
    for(int i=tot,p=lower_bound(v+1,v+n+1,s)-v; i>=1; --i)
    { // 从大往小考虑每个元素，将其尽量取反
        long long y=v[p]-ans[i];
        int t=lower_bound(v+1,v+n+1,y)-v;
        if(v[t]==y && f[i-1][t]==now)
            ans[i]=-ans[i],p=t;
    }
    sort(ans+1,ans+tot+1);
    for(int i=1;i<=tot;++i)
        cout<<ans[i]<<' ';
    cout<<endl;
}
int main()
{
    freopen("recoverset.in","r",stdin);
    freopen("recoverset.out","w",stdout);
    int T;
    cin>>T;
    for(int t=1;t<=T;++t)
    {
        init(); // 输入及一些预处理
        cout<<"Case #"<<t<<": ";
        work();
    }
    return 0;
}