• 搬题人：
  • A：cdw。
  • B：hehezhou。
  • C：cdw, Qingyu。
• 组题人：p_b_p_b。
• 题解：cdw, hehezhou, p_b_p_b。

删数

题目来源：International Zhautykov Olympiad 2022, Computer Science, Day 1, Problem 1.

QOJ 链接：https://qoj.ac/problem/3575

官方题解：https://qoj.ac/files/tutorials/IZhO2022/IZhO-draft.pdf

考虑差分数组 $d_i$，操作即为将相邻相同的数合并为它们的 2 倍。

按照符号 和 $d_i/\text{lowbit}(d_i)$ 分段分别做，不妨设 $d_i$ 均为 $2$ 的幂次，$f_i$ 表示考虑前 $i$ 个数时的答案，递推预处理出 $g_{i,j}$ 表示以 $i$ 为右端点合并出 $2^j$ 时的左端点即可递推计算 $f_i$，这样的 $j$ 仅有 $\mathcal O(\log V)$ 个，时间复杂度 $\mathcal O(n\log V)$，期望得分 $100$。

守卫

题目来源：2021-2022 ICPC North America Championships. Problem I.

QOJ 链接：https://qoj.ac/problem/1825

官方题解：https://qoj.ac/files/tutorials/NAC2021/TheKingsGuards.m4v

算法 1

考虑输入的边集如果是一个森林。

将合法条件拆成两个：

1. 任一连通块不能没有守卫。
2. 任一连通块不能有两个守卫。

首先证明：除非无解，否则不考虑第二个条件，答案不变：

反证法，如果一个连通块内有多个守卫，那么只保留一个，其余守卫暂时进入未部署状态。

对于每个未部署的守卫 $v$，由于这组数据有解，根据二分图匹配的性质，一定存在一条增广路如下：$v\rightarrow x_0\Rightarrow v_0\rightarrow x_1\Rightarrow v_1\rightarrow \cdots\rightarrow x_{k-1}\Rightarrow v_{k-1}\rightarrow x_k$，其中 $v_0,\ldots,v_{k-1}$ 表示守卫，$x_0,\ldots,x_k$ 表示村庄，且村庄 $x_k$ 无人入驻，$v\rightarrow x$ 表示 $v$ 可以入驻 $x$，$x\Rightarrow v$ 表示 $v$ 当前入驻 $x$。进行类似二分图的增广操作，即可使得村庄 $x_k$ 变为入驻状态。

此时，村庄 $x_k$ 所在连通块会有两个守卫，简单的删除两个守卫之间的某条边即可，代价不变大。

因此，我们只需要考虑第一个条件，求出的解如果不合法则输出 -1。

仍然考虑贪心，从大到小逐条尝试删边，用二分图匹配判断是否存在合法方案。

这么做是对的，仍然考虑反证：

考虑最大的边，如果删去这条边后无解，这条边必须被保留，但是可以合并两端的点并认为删去这条边。

否则删去这条边后有解，若最优解中保留了这条边，那么：

将假设的最优解称为最优解，删去这条边后找到的解称为合法解，由上面的证明，最优解每个连通块至多包含一个守卫。

在最优解中删去这条边，得到一个不包含守卫的连通块。

若合法解中，这个点集没有守卫，则这个点集一定向外连了至少一条边，连上这条边，总代价变小。

否则这个点集有守卫并且这个守卫被派往了别的村庄，那么将这个守卫派往合法解所在村庄，则多出了一个不包含守卫的连通块，对于这个连通块，重复这两步讨论。

由此可以构建出一个连通块序列 $C_1,C_2,\cdots,C_k$ ，其中 $C_1$ 是我们讨论的第一个不包含守卫的连通块，而对于每个 $1\le i < k$ ，$C_i$ 从 $C_{i+1}$ 抢了一个守卫。到了 $C_k$ 时，会发现其中的守卫在 $C_1,\cdots,C_{k-1}$ 已经用过了，因此 $C_k$ 必然在合法解中存在一条向外连的边，把这条边连上即可。

算法 2

对于一张图，只保留它的最小生成森林后，答案不变。

这是因为，如果最优解中包含了一条不在最小生成森林上的边，删去这条边。

如果形成了一个不包含守卫的连通块，由于最小生成森林不改变连通性，这个连通块对应的点集在最小生成森林中一定向外连边，加上这条边后，方案仍然合法。并且由于最小生成森林的性质：每条非树边的权值大于对于树上路径所有边的权值，加入的边权一定不大于删除的边权，方案不劣。

因此求出最小生成森林后，从大到小逐条尝试删除即可。

为了降低复杂度，可以维护出当前每个连通块对应的某个守卫，而让剩下的守卫为未入驻状态，初始时对于每个连通块尝试增广，删去一条边判断是否有解时，只需从没有守卫的连通块开始尝试增广即可。

由于每个守卫有 $O(n)$ 个可以入驻的位置，所以单次尝试复杂度 $O(n^2)$ 。

总复杂度 $O(m\log m+n^3)$，分别为最小生成森林的复杂度和尝试删边的复杂度。期望得分 $100$。

算法 3

考虑所有守卫的位置已经确定时应当如何删边。

容易想到自底向上树形 DP ：设 $dp_{x,0/1}$ 表示考虑了 $x$ 的子树，并且此时 $x$ 所在的连通块没有/有守卫，能删去的边的最大权值之和。

虽然这个树形 DP 只能解决 $|S_i|=1$ 的部分分，但是受其启发可以得到描述删边的方法：对于每个守卫，它都需要向祖先方向匹配一条边，使得所有守卫匹配的路径没有交点，并最大化被匹配的边权值之和。

这个模型很容易用费用流来描述：

• 源点向每个守卫连容量为 $1$ 费用为 $0$ 的边。
• 每个守卫向其可以被派遣去的点连容量为 $1$ 费用为 $0$ 的边。
• 每个点拆成入点和出点，所有连向它的边连到入点，所有连出去的边连到出点，入点向出点连容量为 $1$ 费用为 $0$ 的边。
• 每个点的出点向汇点连容量为 $1$ 费用为“它到父亲的边权”的边。
• 特别地，根向汇点连容量为 $1$ 费用为 $\infty$ 的边。

在这个图上跑最大费用最大流即可。期望得分 $100$。

直线

题目来源：Romanian Master in Informatics 2020, Day 2, Task "Nice Lines".

QOJ 链接：https://qoj.ac/problem/151

官方题解：https://qoj.ac/download?type=attachments&id=169&r=0

算法 1

取 $x_0=2\cdot 10^4+1$，$F(t):=f(x_0,t)$ 是关于 $t$ 的下凸的分段一次函数，且求出分段点即可求出直线。

直接分治，若 $F\left(\dfrac{a+b}2\right)=\dfrac{F(a)+F(b)}2$ 则中间没有分段点，否则递归到 $\left[a,\frac{a+b}2\right]$ 和 $\left[\frac{a+b}2,b\right]$ 分别做。

询问次数 $\mathcal O(n\log V)$，常数视实现而定。

算法 2

取 $x_0=10^5$，此时可以将 $t$ 的坐标划分为一些区间使得一段区间至多有一个分段点或一定不存在分段点。

同样考虑分治，先在最左侧和最右侧分别询问 $2$ 次，求出分段函数最左侧和最右侧的一段 $l_1,l_2$，设 $l_1$ 和 $l_2$ 的交点横坐标为 $x_0$，查询 $F(x_0)$，若其确实为 $l_1$ 和 $l_2$ 的交点则唯一分段点即为 $x_0$；否则设 $x_0$ 附近选择分治范围内的不含分段点的区间 $[x_1,x_2]$，取两个点求出这一段直线，递归到 $x_1$ 左侧和 $x_2$ 右侧分别做。

返回值约为 $10^{10}$ 数量级，每次求直线所用 $y_1-y_2$ 约为 $8\cdot 10^4/10^4$ 数量级，所以精度足够。

询问次数 $4n+\mathcal O(1)$，期望得分 $100$。

存在更优的做法，但可能对精度要求更高，需要精细实现。