XXI Open Cup GP of Korea

https://official.contest.yandex.ru/opencupXXI/contest/20794/problems/ https://codeforces.com/gym/102759 #### A. Advertisement Matching 假设 $a_1\ge a_2\ge \cdots\ge a_n$，则能够满足当且仅当 $\sum_{i=1}^{k}a_i\le \sum_{j=1}^m\min\{b_j,k\}\pod{0\le k\le n}$。用线段树维护前缀最小值即可。 时间复杂度 $O(n+m+q\log n)$。 #### B. Cactus Competition 先考虑如何判断能否从 $(1,1)$ 到达 $(n,m)$。下面给出了几种无法到达的情况： 1. 存在一行被阻断，即 $\min\{a_i\}+\max\{b_j\}<0$。 2. 存在一列被阻断，即 $\max\{a_i\}+\min\{b_j\}<0$。 3. 起点被阻断，即存在 $1\le x\le n,1\le y\le m$ 使得 $a_x+b_j<0\pod{1\le j\le y}$ 且 $a_i+b_y<0\pod{1\le i\le x}$。 4. 终点被阻断，即存在 $1\le x\le n,1\le y\le m$ 使得 $a_x+b_j<0\pod{y\le j\le m}$ 且 $a_i+b_y<0\pod{x\le i\le n}$。 事实上，这同时也是 $(1,1)$ 无法到达 $(n,m)$ 的必要条件 (即四个条件都不满足时一定能到达)。 **证明** 称 $a_i+b_j\ge 0$ 的点 $(i,j)$ 为好点，其余点为坏点。条件 1 不满足意味着存在一列都是好点，不妨设为列 $c$。条件 2 不满足意味着存在一行都是好点，不妨设为行 $r$。只需证明 $(1,1)$ 能到达 $(r,c)$ 且 $(r,c)$ 能到达 $(n,m)$ 即可。由于过程类似，以 $(1,1)$ 到 $(r,c)$ 为例。 如果 $r=1$ 或 $c=1$ 则得证。否则，一定存在一行 $r'<r$ 使得 $(r',j)\pod{1\le j\le c}$ 都是好点或存在一列 $c'<c$ 使得 $(i,c')\pod{1\le i\le r}$ 都是好点 (否则可以发现条件 3 成立)。于是就转化到了 $r+c$ 更小的情况，重复此过程直到 $r=1$ 或 $c=1$ 即可。 接下来考虑如何计算答案。条件 3, 4 会直接去掉一些起点和终点。剩下的点中，条件 1, 2 为每个起点限定了一个区间，且区间的两端点都是单调的，可以直接用指针维护。于是只需要解决条件 3, 4 即可。 以条件 3 为例。枚举 $x$，找到最小的 $j$ 使得 $a_x+b_j\ge 0$ (排序后用一个指针扫)，那么只需要考虑所有小于 $j$ 的 $y$ 中 $b_j$ 最小的一个。接着找到最大的 $i<x$ 使得 $a_i+b_y\le 0$ (单调栈 + 二分)，那么从 $i+1$ 到 $x$ 的所有起点都不可能到达任何终点 (用差分记录即可)。 时间复杂度 $O(n\log n+m)$。 #### C. Economic One-Way Roads 有向图 $G=(V,E)$ 强连通当且仅当可以通过以下方法构造： 1. 任选一个点 $s$，令 $S=\{s\}$。 2. 重复以下过程直到 $S=V$。 1. 任选两个点 $u,v\in S$。$u$ 和 $v$ 可以相同。 2. 选择 $k\pod{k\ge 0}$ 个不同的点 $w_1,w_2,\ldots,w_k\not\in S$。 3. 连接 $u\to w_1\to w_2\to\cdots\to w_k\to v$，并将 $w_1,w_2,\ldots ,w_k$ 加入 $S$。 这个方法被称作耳分解，路径 $u\to w_1\to w_2\to \cdots \to w_k\to v$ 被称作耳。 由于本题只要求权值和最小，我们可以要求每次至少加入一个点 (即 $k\ge 1$)，加入点时考虑它和已加入点之间的所有边，不在路径上的边取两个方向的较小值即可。 设 $f[S]$ 表示已经加入点集 $S$ 的最小代价；$g[S][u][v]$ 表示当前加入了点集 $S$，还需加入 $u$ 到 $v$ 的一条路径，最小的代价。枚举下一个点是哪个即可转移。 时间复杂度 $O(N^32^N)$。 #### D. Just Meeting 显然条件相当于任意三点 $u,v,w$ 有 $C(u,v)\ge \min\{C(u,w),C(v,w)\}$。求出最大生成森林，令 $C(u,v)$ 为 $u$ 到 $v$ 路径上边权最小值 (不连通则为 $1$) 即可。若有给定的边不满足则无解。 时间复杂度 $O(n+m\log m)$。 #### E. Chemistry 区间 $[L,R]$ 形成一条链当且仅当无环，边数 $= R-L$ 且每个点的度数不超过 $2$。无环的条件可以用 LCT + Two Pointers 处理，和度数的条件一起构成了形如 $R=x$ 时 $L\ge y$ 的条件。由于无环，边数一定不超过 $R-L$，因此只需要用线段树维护边数 $+L$ 的最大值及个数。 时间复杂度 $O((n+m)\log n)$。 #### F. Interval Graph 无环等价于每个点至多被两个区间覆盖，求最大的权值和。这是一个经典问题，可以用最小费用流解决： - 对每个区间，从 $s_i-1$ 到 $e_i$ 连边容量 $1$，费用 $-w_i$。 - 对每个 $x\pod{0\le x<\max\{e_i\}}$，从 $x$ 到 $x+1$ 连边容量 $+\infty$，费用 $0$。 从 $0$ 到 $\max\{e_i\}$ 的流量为 $2$ 的最小费用流的相反数即为答案。注意初始时图中有负边，但是是 DAG，在使用 Dijkstra 算法时将点 $u$ 的势能设为 $-10^{12}\cdot u$ 即可。 时间复杂度 $O(N\log N)$。 #### G. LCS 8 先设计一个 DP 检验一个给定的串 $t$ 是否合法 (当然可以直接用求 LCS 的 DP，但是这里给出的 DP 用到了 $k$ 小的性质)，然后将其 DP 数组作为状态进行计数 DP。 设 $dp[i][j]$ 表示 $t[0,i)$ 删掉 $j$ 个字符后在 $s$ 里面找子序列，至少要跳过几个字符。显然只需要考虑 $0\le j\le k$ 且 $0\le dp[i][j]\le k+1$ (值为 $k+1$ 表示无解)。并且 DP 还有单调性，即 $dp[i][j]\le dp[i][j-1]+1$。 在 $k=3$ 时，合法的状态也仅有 $200$ 多种。转移时枚举字符即可，也可以通过预处理加速。 #### H. Alchemy 如果初始只有一个材料，则答案就是它的权值 ($0$ 会变成 $1$)。 否则，必定需要合并。假设最后一次合并出了 $x \pod{x\ge 2}$，则把用到的 $x-1$ 都变成 $0$，就能合并出 $x-1$，因此答案具有二分性。二分答案后，从后往前倒推，已知需要权值为 $0,1,\ldots,i$ 的材料各多少个，求出需要权值为 $0,1,\ldots,i-1$ 的材料各多少个。 时间复杂度 $O(n\log n)$。 #### I. Query on a Tree 17 一棵点权非负且总和为正的树的所有带权重心位于一条链上，而其中深度最小的点是满足子树和严格大于总和一半的点中最深的。取这棵树的一个 DFS 序，因为其子树和大于一般，因此 DFS 序的带权中位数一定在子树内。找到这个点后在链上倍增即可。 时间复杂度 $O(n\log n+q\log^2n)$。 #### J. Remote Control 离线对所有询问一起处理，每次操作变成所有点向一个方向移动，然后将处在 $(0,0)$ 的点移回去。全局加可以打标记，用 `std::map` 来查找点。合并两个点的时候需要对询问集合启发式合并。 时间复杂度 $O((n+q)\log q)$。 #### K. Sewing Graph 边数至少为 $2n-2$，因此答案至少为 $2n-1$。将所有点按 $x$ 为第一关键字，$y$ 为第二关键字排序后，相邻两个点之间的 $n-1$ 条线段不会在端点之外的点相交。先从前往后连，再从后往前连即可取到下界。 时间复杂度：$O(n\log n)$。 #### L. Steel Slicing 2 我们把顶点分为凸顶点和凹顶点。显然每次操作要么连接两个凹顶点，要么连接一个凹顶点和一条边上的某个点。最终目的是删除所有凹顶点，因此只需要最大化连接两个凹顶点的线段数量。 纵向的线段是平凡的，横向的线段可以用单调栈处理，数量也只有 $O(n)$。选择的线段不能相交，因此问题转化为二分图最大独立集，也即二分图最大匹配。注意到每条横向线段都能匹配一个区间的纵向线段，因此从左到右扫，每次优先匹配右端点最小的即可。 时间复杂度 $O(n\log n)$。