10527

minstdfx · 2024-05-23 21:07:25 · 题解

简单题。

对 U 的每一子集 S，设 F(S)=|\sum_{x\in S}x-\sum_{x\in \complement_US}x|，则答案是 \min_{S\in U}F(S)。接下来我们证明对于每一可能的子集 S，均存在一种构造方案使得答案为 F(S)。

给出一种考场上想出的构造方式：维护两个集合 S,T 表示对应的子集和补集，每次任取 S,T 中的两个元素 a\in S,b\in T，把它们从集合中删去，并将他们的差值 |a-b| 加入 a 和 b 中较大的那个对应的集合中。
接下来证明这么做是对的：考虑对于 |S|\cdot|T|=0 的情况，正确性是显然的，每一步操作也不影响值 |\sum_{x\in S}x-\sum_{x\in T}x|，且由于每步必然有一个集合大小缩减 1，因此必然可以通过有限步操作到达 |S||T|=0 的边界情况。至此我们得到了一种操作方案。

接下来我们考虑如何计算最小值。用 bitset 维护当前所有值域中的值是否可以作为一种方案的答案，即 dp_{i,j}=[\exist S\subset \{a_1,a_2,\cdots,a_i\}(F(S)=j)]，边界条件为 dp_{0,i}=[i=0]。对每个物品考虑是否放入 S 中，则有 dp_{i,j}=dp_{i-1,j+a_i} \operatorname{or}dp_{i-1,|j-a_i|}。一部分可以 bitset 直接位移，另一部分不超过 \max a_i 次更新，可以每次暴力维护。

但是值域达到了 5\times 10^7，只需要构造 x-1 个 x 和 x 个 x-1 就可以使得中途达到的最大值域卡到上界，可以打乱优化。这里不对打乱优化进行证明，相关证明参考[THUPC2021] 混乱邪恶 题解区。

记得加滚动数组。

原题解供喷：

容易发现每次就是对 bitset 左移右移或一下然后暴力做不超过 $5000$ 的部分，再加上打乱优化+开小 bitset 即可通过。

具体地，每次 $dp_{i,j+a_i} = dp_{i,j+a_i} \operatorname{or} dp_{i-1,j}$ 直接维护，$dp_{i,|j-a_i|} = dp_{i,|j-a_i|} \operatorname{or} dp_{i-1,j}$ 拆成 $j\ge a_i$（直接 bitset 移位维护）和 $j<a_i$（不超过 $5000$，直接暴力）。

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=1e4+9;
int a[maxn],n;
bitset<(1<<20)> x[2]; 
int main()
{
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    random_shuffle(a+1,a+n+1);
    x[0].set(0);
    for(int i=1;i<=n;++i)
    {
        x[i&1]=(x[~i&1]<<a[i])|(x[~i&1]>>a[i]);
        for(int j=a[i];j;--j)
            x[i&1][a[i]-j]=x[i&1][a[i]-j]|x[~i&1][j];
    }
    for(int i=0;i<(1<<20);++i)
        if(x[n&1][i]) printf("%d\n",i),exit(0);
    return 0;
}