专题题解 - XXI Open Cup, Grand Prix of Korea

发表于 分类于
https://codeforces.com/gym/102759

本场比赛中的大约三四道题目在之前的联测或 APIO 讲课中出现。

打 * 号表示没有写的题，可能是不打算写了，也可能是暂时没来得及写。

A. Advertisement Matching

难度：$\bigstar\bigstar$

题目大意：

有 $n$ 种广告，第 $i$ 种有 $a_i$ 份，还有 $m$ 个用户，第 $i$ 个用户可以接受 $b_i$ 份广告，每个用户不能接受多份同种广告。

接下来有 $q$ 个操作，每个操作为将某个 $a_i$ 或 $b_i$ 加一或减一，每次操作后请计算是否存在将所有广告分发完的方案。

$1\leq n,m,q\leq 2.5\times 10^5$

题目解法：

霍尔定理扩展的经典问题，朝这个方向稍微想想就可知道，将 $a_i$ 从大到小排序后，当且仅当对于每个 $x\in [1,n]$ 都满足 $\sum\limits_{i=1}^x a_i\leq \sum\limits_{i=1}^m \min(x,b_i)$ 时答案才为肯定。

用线段树维护上述式子，由于都是加减一所以可以假设没有大小顺序的变化，时间复杂度为 $O(q\log n+n+m)$。

B. Cactus Competition

难度：$\bigstar\bigstar$

题目大意：

有 $n\times m$ 网格，给定数组 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_m$，当且仅当 $a_i+b_j\ge 0$ 时 $(i,j)$ 是黑格，现在请问有多少对 $(s,t)$ 满足：存在一条从 $(s,1)$ 到 $(t,m)$ 的每次仅能够向右或向下行走一步的只通过黑格的路径。

$1\leq n,m\leq 2\times 10^5$

题目解法：

先讲我的做法：

将满足 $a_x+\min(b_i)\ge 0$ 的行 $x$ 称为桥。

那么显然从 $(s,1)$ 可以走到 $(t,m)$，当且仅当可以从 $(s,1)$ 走到一个桥，再从同一个桥可以走到 $(t,m)$。

把桥从上到下依次编号，我们只需要求出从每一个 $(s,1)$ 可以走到的最大编号的桥，和可以走到 $(t,m)$ 的编号最小的桥，然后就是一个平凡的二维偏序问题。

以前一个问题为例，求 $(s,1)$ 可以走到的编号最大的桥，这个问题可以递推，容易证明如果 $s$ 不是桥，那么设 $p$ 是满足 $p>s$ 且 $a_p\ge a_s$ 的最小的 $p$，则如果从 $(s,1)$ 可以到达第 $p$ 行那么 $(s,1)$ 的答案与 $(p,1)$ 相同，否则 $(s,1)$ 走不到任何一个桥。

于是只需要用 ST 表和二分的基本技巧就可以求出上面问题的答案了，再结合树状数组解决二维偏序即可通过。

时间复杂度为 $O(n\log n)$。

大众做法大概就是考虑 $(1,1)$ 到 $(n,m)$ 什么情况可以走通，就是起点终点不能被封锁，并且不能有行列被封锁，然后基于此考虑，复杂度应该是一样的。

C. Economic One-way Roads

难度：$\bigstar\bigstar\bigstar\bigstar$

题目大意：

给定 $n$ 个点的无向图，你需要给每条边定向，每种方向各有一个边权，你需要使得定向后的图强连通，求定向边权和的最小值。

$2\leq n\leq 18$

题目解法：

本题需要用到强连通图的耳分解相关知识。

设点集为 $V$，对于其一个子集 $S$，如果 $u,w\in S$，而 $v_1,\ldots,v_k\in V-S$，并且存在有向路径 $u\to v_1\to \ldots\to v_k\to w$，那么就称这条路径是 $S$ 的一个耳。

一个有向图是强连通图，当且仅当：

  • 设有一个点集 $S$，初始为 $\{1\}$；
  • 每次选择 $S$ 的一个耳，将其中所有点加入 $S$ 中；
  • 重复上述过程，可以使得 $S=V$。

所以在本题中，我们设 $f(S)$ 表示上述过程中的点集为 $S$ 时，$S$ 内部定向边权和的最小值。

简单的想法是枚举耳的点集，将它加到 $S$ 中，但复杂度可达 $O(3^n\operatorname{poly}(n))$。

考虑一个点一个点地加入一个耳，设 $g(S,v,w)$ 表示当前点集为 $S$，目前正在加一个耳，终点为 $w$，当前这个耳构造到了 $v$（可以发现耳的起点 $u$ 不用算入状态），那么每次枚举 $v$ 的后继 $v’$，转移到 $g(S\cup \{v’\},v’,w)$ 即可。

注意到 $(v,w)$ 和 $(w,v)$ 两条边不能同时出现，所以还需要额外记录一个 $b$ 表示耳的上一条边是否就是 $(w,v)$，如果是的话则不能在下一步选择 $(v,w)$ 这条边使得耳闭合。

时间复杂度为 $O(2^n\times n^3)$。

D. Just Meeting

难度：$\bigstar$

题目大意：

定义一个 $n$ 个点的无向带权完全图（$i,j$ 之间边权为 $w(i,j)$ 为正整数）是正规的，当且仅当对于任意不同的 $1\leq i,j,k\leq n$，都有 $w(i,j),w(j,k),w(k,i)$ 三个数中最小值不唯一。

给定点数 $n$ 和 $m$ 条带权边，问是否可以将图补全成正规的图，如果可以则请求出补全后图的边权和最小值。

$1\leq n,m\leq 3\times 10^5$

题目解法：

每个连通块是独立的，连通块之间的所有边权都设为 $1$ 即可。

首先容易证明 $w(i,j)\ge \min(w(j,k),w(i,k))$，所以如果我们构建图的一个生成树，那么非树边 $(i,j)$ 的权值必须大于等于它们树上路径权值的最小值。

再联想到最大生成树中有 $w(i,j)\leq \min(w(j,k),w(i,k))$，所以如果我们取最大生成树，就应该有 $(i,j)$ 间的权值应该恰好等于它们树上路径权值的最小值。

于是用维护子树大小的并查集处理一下即可，注意判定是否有解需要支持查询树链最小值。

时间复杂度为 $O((n+m)\log n)$。

*E. Chemistry

难度：$\bigstar\bigstar$

F. Interval Graph

难度：$\bigstar\bigstar$

题目大意：

给定 $n$ 个带权区间，你可以删除一些区间，对剩下的区间建区间图（每个区间对应一个点，两个区间有交就连边），要求该图无环，求剩下的区间权值和的最大值。

$1\leq n\leq 2.5\times 10^5$

题目解法：

区间图是弦图，因此有环当且仅当有三元环，也等价于有三个区间存在公共点。

所以我们需要挑选一些区间，使得被这些区间覆盖后每个点至多被覆盖两次，这是经典的 Delight for a Cat 型费用流建模，建出图后用原始对偶费用流求解即可，最大流只为 $2$ 所以只要做两次最长路。

初始势能有一种简单设法：$E_i=-W\times i$，其中 $W$ 是权值最大值。

时间复杂度为 $O(n\log n)$。

G. LCS 8

难度：$\bigstar\bigstar\bigstar\bigstar$

题目大意：

给定长度为 $n$ 的字符串 $S$ 和 $k$，求长度为 $n$ 的字符串 $T$ 的数量，使得 $S$ 与 $T$ 的最长公共子序列长度不小于 $n-k$，字符集为大写字母。

$1\leq n\leq 50000, 0\leq k\leq 3$

题目解法：

解一（代码区发现的解法）：

考虑用 DP 解决 LCS 问题时需要用到的结构，尝试对这一结构进行递推计数。

设 $dp(x,a_0,a_1,a_2,a_3)$ 表示已经填入 $T_1,\ldots,T_x$，并且 $a_i$ 是使得 $\operatorname{LCS}(T_1\ldots T_x,S_1\ldots S_{x-i+a_i})=x-i$ 成立的最小自然数，其中下标取 $x-i+a_i$ 的理由是注意到这个下标应当在 $[x-i,x-i+3]$ 之间（否则就是无用的状态），也就是说 $a_i\in [0,3]$，特别地如果 $a_i$ 不存在则认为其等于 $4$。

增加一个数时通过简单的讨论转移即可。

时间复杂度为 $O(k^k\times n|\Sigma|)$。

解二（题解）：

直接尝试刻画求 LCS 时 DP 数组的形态。

设 $f(i,j)$ 表示 $\operatorname{LCS}(T_1\ldots T_i,S_1\ldots S_j)$，将状态设为 $(i,f(i,i-k),\ldots,f(i,i),\ldots,f(i,i+k))$，事实上由于 $f(i,j)-f(i,j-1)\in [0,1]$，并且我们只需要 $f(i,i)\in [i-k,i]$ 的状态，所以总的状态数是 $O(2^{2k}\times nk)$。

转移需要进行一定的预处理，比之上一种做法复杂得多。

最终的时间复杂度为 $O(2^{4k}|\Sigma|+2^{2k}\times nk)$。

H. Alchemy

难度：$\bigstar$

题目大意：

现在有一堆 $[0,n)$ 中的数，其中 $i$ 有 $c_i$ 个，你每次可以选择一些数将它们删除，然后加入它们的 $\operatorname{mex}$，最后你需要使得只剩一个数，问这个数的最大值。

$1\leq n\leq 10^5$

题目解法：

假设 $\sum c_i=1$，那么答案是显然的（但注意并不一定是那个为 $1$ 的 $c_i$，当 $i=0$ 时）。

否则，先考虑枚举 $x$，要拼出 $x$，首先可以把所有 $\ge x$ 的数都回收成 $0$，然后这样考虑：要拼出一个 $x$ 需要 $0,\ldots,x-1$ 各一个，要拼出 $x-1$ 需要 $0,\ldots,x-2$ 各一个，要拼出两个 $x-2$ 需要 $0,\ldots,x-3$ 各两个，以此类推一直分解到 $0$，看看 $0$ 够不够用即可，如果过程中某个 $c_i\ne 0$，那么如果 $c_i$ 小于等于实际需要，那么可以将实际需要的抵消掉 $c_i$，如果 $c_i$ 大于实际需要那么可以将多余的回收成 $0$。

根据上述过程可知答案具有可二分性，二分答案并判定，显然答案不超过 $2\times 10^5$，时间复杂度为 $O(n\log n)$。

I. Query on a Tree 17

难度：$\bigstar\bigstar\bigstar$

题目大意：

维护 $n$ 个点的以 $1$ 为根的点带权树，支持 $q$ 次子树或路径修改点权，每次修改后输出最浅的带权重心。

$1\leq n,q\leq 10^5$

题目解法：

一个结论是：写出树的 DFS 序，并且将 $i$ 重复 $a_i$（点权）次，那么最浅的带权重心的子树对应的区间一定包含这个序列的中位数（因为其长度应该大于等于总长一半，否则可以再往上走一步）。

于是我们维护这个序列长度和按照 DFS 序的点权前缀和，这当然就契合重链剖分的维护特点，于是我们每次查询中位数，然后从那个点树上倍增就可以找到带权重心。

时间复杂度为 $O(n+q\log^2 n)$。

J. Remote Control

难度：$\bigstar$

题目大意：

给定长度为 $n$ 的操作序列，包含 $\text{L,R,U,D}$ 四种指令，一个机器人从坐标系中某点出发，依次按照对应指令向左右上下行走一个单位长度，特别的是，如果行动后会到达 $(0,0)$，那么机器人会忽视这个指令。

现在给定 $q$ 组 $(x,y)$，表示机器人的起点，问每组起点对应的终点。

$1\leq n,q\leq 3\times 10^5$

题目解法：

首先预处理 $f(i)$ 表示如果机器人位于执行一次第 $i$ 个指令后就会到达 $(0,0)$ 的位置，那么它依次执行指令 $i+1,\ldots,n$ 后会到哪里，状态数是 $O(n)$，而转移只需要考虑机器人下一次碰到 $(0,0)$ 四周的时刻即可。

对于询问，也是找到机器人第一次碰到 $(0,0)$ 四周的时刻，然后根据 $f(i)$ 计算答案。

时间复杂度为 $O((n+q)\log n)$。

K. Sewing Graph

难度：$\bigstar$

题目大意：

给定 $n$ 个平面上的点，请构造一个尽可能短的由这些点组成的序列 $s_1,\ldots,s_m$，使得：

  • 分别连接 $s_{2k}$ 和 $s_{2k+1}$，构成的图连通且没有两条边交叉；
  • 分别连接 $s_{2k-1}$ 和 $s_{2k}$，构成的图连通且没有两条边交叉；

求构造 $m$ 和点列。

$2\leq n\leq 1000$

题目解法：

按横坐标第一关键字，纵坐标第二关键字排序为 $p_1,\ldots,p_n$，然后令序列为 $p_1,\ldots,p_{n-1},p_n,p_{n-1},\ldots,p_1$ 即可。

时间复杂度为 $O(n\log n)$，这是本场比赛的签到题。

*L. Steel Slicing 2

难度：$\bigstar\bigstar\bigstar$