从来没有写过这样的博客！

问题大概形如：

给定值域为 $[1,W]$ 的序列 $\{a_n\}$，要求将序列划分为两半，使得“两边分别的和”的差的绝对值最小。

一个简单的想法

可以认为将一些元素前挂上 $-1$ 的系数，使得所有元素的和最接近 $0$。这相当于有若干对物品 $\{a_i, -a_i\}$，要从中二选一。

这是一个经典的背包问题，暴力实现是 $\mathcal{O}(n^2W)$，bitset 优化后可以做到 $\mathcal{O}\Big(\dfrac{n^2W}{\omega}\Big)$。

或许有用的优化：

经典结论：一个长度为 $n$ 的随机 $\pm 1$ 序列，其前缀和的最大值是 $\mathcal{O}(\sqrt{n})$。

因此可以认为在 random_shuffle 后，背包大小只需要开到 $\mathcal{O}(\sqrt{n}W)$。这样就优化到了 $\mathcal{O}\Big(\dfrac{n\sqrt{n}W}{\omega}\Big)$。（但是在模拟赛中表现不太好！）

构造一组较优解

接下来给出一个简洁的构造方案，将两侧之差控制在 $W$ 以内。

从 $1$ 到 $n$ 扫描每个 $a_i$，决策当前元素是否 $\times (-1)$。若之前的和 $\le 0$，则 $+a_i$，否则 $-a_i$。容易发现最终序列和在 $(-W, W]$ 之间。

[ZR-NOIP] 均分财产

给定值域为 $[1,W]$ 的序列 $\{a_n\}$，要求删除不超过 $k$ 个，然后把剩下的部分划分为相等的两部分。$a_i$ 在值域内均匀随机。
$W=2\times 10^5, 2\le n\le 2\times 10^5, \min(25, n-2)\le k\le n-2$。

首先通过上述方法，对前 $n-k$ 个元素构造一组差距在 $W$ 以内的解，然后尝试对最后 $k$ 个使用删除操作将差距调整至 $0$。

若前 $n-k$ 个元素构造出的差是 $c\in(-W, W]$，考虑 $k=25$ 个元素的所有子集，元素和均在 $25W$ 以内，而子集个数有 $2^{25}$ 个，由于数据随机，所以大概率存在两个子集的差恰好为 $c$（可以调整至不交），将其他元素删除即可。

需要对 $n\le 25$ 的情况进行特判。

[GCJ Round 1A] Equal Sum

这是一道交互题。有一个长度为 $2n$ 的序列 $\{a_{2n}\}$，需要保证元素互不相同。
你需要给出其中的 $n$ 个数字，剩下 $n$ 个数字由交互器（在确定你的 $n$ 个数后）给出，要求划分为相等的两部分。
交互库将保证有解。
$W=10^9, n=100$。

不论我们构造的是什么，总可以将交互器给出的元素划分为差在 $W$ 以内的两份。只要我们的部分能构造出任意在 $W$ 以内的元素即可。容易发现先加入所有 $2^i$，剩下不够的乱填，最后拿 $2^i$ 调整即可。

一个确定性的做法

在联考中遇到的，可以在 $\mathcal{O}(nW)$ 的时间内解决一个甚至更强的问题：

给定值域在 $[1,W]$ 的序列 $\{a_n\}$，要求找出一个子集使得其元素和 $\le A$ 且最大。

在本问题中 $A=\dfrac{\sum_{i=1}^n a_i}{2}$。

这相当于给每个 $a_i$ 一个系数 $x_i\in\{0, 1\}$。要求 $\sum_{i=1}^n a_ix_i\le A$ 且最接近 $A$。

定义 $b=\min\{t\ |\ \sum_{i=1}^{t} a_i> A\}$，即第一个前缀和 $>A$ 的位置。定义起始解为：$x_i=[i<b]$。

定义平衡解是由以下方式得到的所有解：

  1. 起始解 是 平衡解。
  2. 若平衡解满足 $\sum a_ix_i\le A$，选择 $p\ge b$ 且 $x_p=0$，将 $x_p$ 设为 $1$ 后，新解仍是平衡解。
  3. 若平衡解满足 $\sum a_ix_i> A$，选择 $p< b$ 且 $x_p=1$，将 $x_p$ 设为 $0$ 后，新解仍是平衡解。

容易发现，第二部分中的贪心构造，同样是一个平衡解。并且根据构造过程能够发现，任意平衡解的元素和在 $(A-W, A+W]$ 之间。接下来，我们尝试说明：

最优解，一定可以通过平衡解求得（可以通过起始解，使用上述方法推得）。

若最优解是 $x$，我们考虑两个集合 $A,B$，其中：

$$ A=\{ p\ |\ p<b, x_p=0\} $$

$$ B=\{ p\ |\ p\ge b, x_p=1\} $$

其实也就是 $b$ 之前、之后的，起始解与最优解的不同之处。注意到删除 $A$ 中元素，会使起始解之和变小，删除 $B$ 中元素会使起始解之和变大。于是可以根据上述平衡解的构造方法，得出一种可行的删除元素方案。

从上面的定义和分析，现在我们将问题的值域优化到 $\mathcal{O}(W)$，接下来考虑 $\text{dp}$。

观察平衡解的形式，一定是一个前缀的 $x_i=1$，一个后缀 $x_i=0$，中间 $0,1$ 均有。设 $\text{dp}(l, r, v)$ 表示 $[1,l)$ 的 $x_i=1$，$[l,r]$ 的 $x_i$ 任意，$(r, n]$ 的 $x_i=0$，的所有方案中，$\le v$ 的最大方案。

我们使用三元组 $(l,r,v)$ 表示 $\text{dp}(l, r, v)=v$，即存在一种方案，只支配 $[l,r]$ 内的元素得到 $v$。

注意到，对于两组解 $(l,r,v),(l',r,v)$，若 $l'<l$ 则 $(l',r,v)$ 是毫无用处的。因为 $(l,r,v)$ 区间较短，可供操作的余地更大；对 $r$ 也是同理。

于是，将状态设为 $\text{dp}(r, v)$ 表示所有三元组 $(l,r,v)$ 中最大的 $l$ 是多少。如果不存在这样的三元组，则 $l=0$。接下来给出伪代码：

1.   dp(b - 1, V) = b
2.   for i from b to n
3.       for j from A - W + 1 to A + W do
4.           dp(i, j) = dp(i - 1, j)
5.       for j from A - W + 1 to A do
6.           k = j + a(i), dp(i, k) = max(dp(i, k), dp(i - 1, j))
7.       for j from A + W to A + 1 do
8.           for k from dp(i, j) - 1 to max(dp(i - 1, j), 1) do
9.               o = j - a(k), dp(i, o) = max(dp(i, o), k)

首先 1. 中，V 表示起始解之和。这意味着 $[1,b)$ 全选，$[b,n]$ 全不选是一组方案。接下来，从 $b$ 开始考虑每个元素 $x_i$ 的取值。

3 ~ 4 表示 $x_i=0$，即可以直接从上一个右端点继承最优左端点。

5 ~ 6 表示 $x_i=1$，注意到根据平衡解的定义，只有在元素和 $\le A$ 的时候才能在 $\ge b$ 的地方加入一个元素，所以循环区间是 $[A-W+1,A]$。

7 ~ 9 表示选择一个 $x_k=0$，此时要求元素和 $>A$，于是循环区间是 $[A+1,A+W]$。8. 中，如果循环下界到 $1$ 即是容易理解的（即枚举每个元素是否删除）。

而 $\text{dp}(i - 1, j)$ 的下界的意思是，如果左端点在这之前，那么就存在一个右端点为 $i-1$ 的三元组。这个三元组优于当前三元组，所以无需考虑。

同时注意到 $\text{dp}(i-1,j)\le \text{dp}(i,j)$，所以均摊复杂度是 $\mathcal{O}(nW)$。

标签: none

添加新评论