BalticOI 2022

标签：背包上船 LOJ 贡献 2022 BalticOI

有一道题 LOJ 没有，就没做了。

注意到询问次数为 $n$，我们希望每次确定一个数的位置。考虑增量法，前 $i-1$ 次操作构建出 $[1,i-1]$ 的排列，在第 $i$ 次操作的时候插入 $i$。

首先询问 $p={1,2,3,\dots,n-1,n}$，设返回值为 $B_1$。

考虑如何确定 $2$ 在 $1$ 前面还是后面，询问 $p={2,1,3,4,5,\dots,n-1,n}$，设返回值为 $B_2$。如果 $B_2<B_1$，则 $2$ 在 $1$ 前面，否则 $2$ 在 $1$ 后面。

拓展这个做法。对于 $i$，询问 $p={i,1,2,\dots,i-1,i+1,\dots,n-1,n}$，设返回值为 $B_i$。

设 $[1,i-1]$ 中应该在 $i$ 左边的数有 $L_i$ 个，在右边的数有 $R_i$ 个。容易得到
$$
\begin{cases}
L_i+R_i=i-1 \
R_i-L_i=B_{1}-B_{i}
\end{cases}
$$

那么就求出了 $L_i,R_i$，就知道 $i$ 应该处于 $[1,i]$ 排列的什么位置了。

倒着考虑往回跳，则变成选择一个 $r$ 在当前区间里的区间。

贪心地选择区间，那么选择的 $l$ 越小越好。（为什么？）

证明：设当前区间为 $[l,r]$。假如我们希望跳到一个区间 $k$。若 $r_k\ge l$ 则直接跳过去，否则 $r_k<l$。

设我们能跳到的两个区间分别为 $i,j$，则 $r_i,r_j\ge l$，由于 $r_k<l$，这两个区间能否跳到只与 $l$ 有关，取 $l$ 更小的更优。

那么往回跳肯定取能到达的最小的 $l$，过程是唯一的，直接倍增即可。复杂度 $O(n\log n)$。

好像是一个经典的背包问题，一直没做。

这类背包问题通常背包容量 $L$ 很大但是物品体积 $w_i$ 很小（本题 $m=\max w_i$），采取贪心 + 小范围 DP 的做法。

先将体积为负的取了，然后将体积与价值取反。考虑一个贪心：按性价比排序后从前往后取，直到背包放不下。

此时背包内放的物品体积之和 $S$ 必定在 $(L-m,L]$ 之间，否则可以继续取物品。

考虑最终方案，一定是丢掉一些物品，再放入一些物品。我们希望通过对当前的方案进行一些丢掉/放入的操作得到最终方案。

由于 $|w_i|\leq m$，我们可以通过调整操作的顺序来使得 $S$ 始终在 $(L-m,L+m]$ 之间。具体地，如果 $S<m$ 就放入物品，否则丢掉物品。那么我们把 $S$ 的取值范围控制在了 $O(m)$ 的级别。

在操作的过程中，一个 $S$ 不会出现多次。如果出现了两次，那么要么保留这两次中间的操作更优，要么不进行这段操作更优。因此最多操作 $2m$ 次，所以背包大小是 $2m^2$ 级别的。

设体积为 $i$ 的物品原本有 $a_i$ 个，贪心过程中用了 $b_i$ 个。那么有 $a_i-b_i$ 个体积为 $i$，价值为 $1$ 的物品（放入操作），以及 $b_i$ 个体积为 $-i$，价值为 $-1$ 的物品（丢掉操作）。跑多重背包即可。

复杂度 $O(m^3)$。

早就听说过 kruskal 重构树，但是从来没做过相关的题，感觉很 nb。

考虑如何判断一个点是否满足要求。那么就是和它相邻的点中，能被合并就合并。

令一条边 $(x,y)$ 的边权为 $\max(v_x,v_y)$，则当前相连的边中，若存在边权小于等于当前连通块的点权之和，就可以合并。

建出 kruskal 重构树，那么一个点能够合并的边权最小的边一定是当前重构树上的父亲。并且当前连通块的点权之和为子树中的所有点权之和。

那么边权和点权都知道，就能判断一个点能否满足要求了。在重构树上 DFS 一遍即可。复杂度 $O(m\log m)$。

读题的时候没读懂，说明一下题意：可以决定组与组之间的登船顺序，组内可以决定每个人的方向，但是组内上船的顺序是随机的。最小化每个人经过的人数之和的期望。

首先容易发现组内一定是靠左的一些人从左边上船，剩下的靠右的人从右边上船。

状压登船顺序。设当前在船上的组为 $S$，新进加入的组的编号为 $A$。设 $c_A$ 表示 $A$ 的人数。

枚举断点 $k$ 表示 $k$ 左边的人从左边上船，$k$ 右边的人从右边上船。会产生两种贡献：$A$ 内部上船的贡献，以及 $A$ 与 $S$ 产生的贡献。

$A$ 内部上船的贡献是好算的：设断点左边有 $x$ 个人，则右边有 $c_A-x$ 个人。这两边也是独立的，每对人有 $\dfrac{1}{2}$ 的概率产生贡献，那么有 $\dfrac{1}{4}(x(x-1)+(c_A-x)(c_A-x-1))$。

$A$ 与 $S$ 产生的贡献可以拆成 $A$ 与 $B\in S$ 产生的贡献之和。设 $f(A,B,k)$ 为 $A$ 与 $B$ 在断点 $k$ 产生的贡献，这个可以直接预处理出来。

但是转移是不能直接枚举 $k$。注意到 $A,S$ 固定时，$A$ 内部的贡献以及 $A$ 与 $S$ 的贡献是下凸的。那么可以直接三分 $k$ 找到最优决策点。复杂度 $O(2^gg2\log n)$。

标签：背包,上船,LOJ,贡献,2022,BalticOI
From： https://www.cnblogs.com/tevenqwq/p/18217536