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

无环等价于每个点至多被两个区间覆盖，求最大的权值和。这是一个经典问题，可以用最小费用流解决：

从 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)。