XXII Open Cup. Grand Prix of Korea

发表于 2021-10-29 更新于 2021-10-30

链接

A	B	C	D	E	F	G	H	I	J	K	L	M
$\color{green}{\texttt{+1}}$	$\color{red}{\texttt{+3}}$	$\color{green}{\texttt{+1}}$		$\color{gray}{\texttt{+}}$		$\color{red}{\texttt{+}}$	$\color{gray}{\texttt{+1}}$		$\color{gray}{\texttt{+}}$	$\color{green}{\texttt{+}}$

J. Periodic Ruler

签到题。

H. Or Machine

对于整周期我们按位处理，记录一个数字至少多少轮后该位变成 $1$。这本质上是一个最短路，而且有效转移边边权只有 $0$ 和 $1$。

对于散周期暴力处理即可。复杂度 $O(l+n\log V)$。

C. Equivalent Pipelines

考虑 Kruskal 求最小瓶颈路的过程：从大到小加入一条边，其连接的两个集合之间的最小瓶颈路就是该边边权。

那么显然的想法就是枚举权值，将该权值连接的点集记录下来。可以发现这个过程可以用 Hash 实现：定义一个点集 Hash 函数为其所有点的 Hash 之和，连接两个点集的 Hash 值为两个点集 Hash 之积乘上边权。容易证明这个 Hash 函数与上述点集描述是等价的。

E. Goose Coins

容易证明，假设不考虑硬币数量限制，那么对于任何有解的情况，从大往小贪心地能取就取一定可以恰好达到目标方案。而此时的硬币数量一定是最小的。

同时也容易发现，任何方案可以用上述方案通过将若干 $c_i$ 硬币换成 $\frac{c_i}{c_{i-1}}$ 枚 $c_{i-1}$ 硬币得到。

考虑 dp，用 $f_{i,j,k}$ 表示当前在 $i$ 位置，已经放了 $j$ 个硬币，$c_i$ 硬币还有 $k$ 个的最小/最大重量。枚举 $i$ 硬币分裂几次，可以得到一个 $O(nk^3)$ 的 dp。事实上可以通过。

事实上我们并不关心当前位置到底有多少个硬币，而关心的是当前位置是否存在 $l$ 个硬币。所以我们可以不必枚举 $k$ 而是简单地后缀 $\min$，这样复杂度就变成 $O(nk^2)$。

K. Three Competitions

容易发现，如果把 $i$ 直接击败 $j$ 看做边 $i\rightarrow j$，那么这是一张竞赛图。而竞赛图的一大性质是：给定每个点的出度，可以得到 scc（强连通分量）。

具体来说，将所有点按照出度排序，可以证明如果两个点不在一个 scc 中，出度小的一定在前面，并且一个 scc 的所有点构成一个区间。

这样考虑如果一个区间中的点构成一个环，当且仅当加入这个环前是合法的竞赛图（出度之和 $=\frac{n(n-1)}2$），加入之后是合法的竞赛图，且任何一个真前缀都不是合法的竞赛图。直接扫一遍即可判断 scc。

最后求每个点出度可以直接二维偏序减三维偏序。复杂度 $O(n\log^2 n)$。

A. Automatic Sprayer 2

大概就是根据二阶差分之后结果确定除去第一行和最后一行的所有行上数字之和。

同样也可以确定第一列和最后一列的所有行上数字之和。

然后列方程手动解出第一行和最后一行。

最后构造直接贪心，可以证明如果有解一定可以用贪心构造。

赛时题解

容易构造使矩阵只有唯一解，所以不用想一些乱搞了。  
令 X1|X2|X3|X4|... 表示第 1 行 1,2,3... 列的情况  
令 a1,a2... 表示第 1,2,... 列的总数  
X1=a2+2a3+3a4+...+W  
X2=a1+a3+2a4+...+W  
X3=2a1+a2+a4+...+W  
X4=3a1+2a2+a3+...+W  
D1=S1-S2=-a1+a2+a3+a4+...  
D2=S2-S3=-a1-a2+a3+a4+...  
D3=S3-S4=-a1-a2-a3+a4+...  
D1-D2=2a2  
D2-D3=2a3  
...  
可以求出 a2,a3,...,an-1  
同理 b2,b3,...,bn-1  
考虑求出 a1,an,b1,bn  
可以发现的是:  
S(n,n)=Xn+Yn=(n-1)a1+(n-1)b1+C1  
S(n,1)=Yn+X1=(n-1)a1+(n-1)bn+C2  
S(1,n)=Xn+Y1=(n-1)an+(n-1)b1+C3  
S(1,1)=X1+Y1=(n-1)an+(n-1)bn+C4  
看起来有 4 个方程，然而是线性相关的。。。最后一个方程可以用前三个表示。  
因为少了一个等式：行的点数之和等于列的点数之和。  
换句话说 X1+Xn=Y1+Yn+D  
这样等式就齐了。  
令 R1=C1-S(n,n) , R2=C2-S(n,1) , R3=C3-S(1,n)  
(n-1)a1=(2R1+R2-R3+D)/4  
(n-1)an=(-2R1+R2-3*R3+D)/4  
(n-1)b1=(2R1-R2+R3-D)/4  
(n-1)bn=(-2R1+3*R2+R3-D)/4  
最后贪心构造即可

G. Lamb’s Respite

因为一开始是从满血出发的，一旦血条没了直接挂，这个过程可以看做是对序列求一个最小子段和，要求这个子段和加血量大于零。

然后注意到放技能期间只要小于 $\lceil\frac{H}{10}\rceil$ 是直接锁血的。实际上只需要判断有无触及这条线即可。这个和上面那个差不多。

所有操作可以用线段树维护前缀/后缀/整体最小完成。复杂度 $O(n\log n)$。

B. Cilantro

首先可以证明的是：只要 Y 与 N 个数一样就一定有解。具体可以反证得到。

这样我们可以发现，如果前 $x$ 个元素入栈后仍然合法，那么 $y<x$ 个元素入栈也一定合法。所以我们只需要求出最大的位置，然后该位置前所有与 $t_1$ 相同的字符全部合法。

直接二分可以做到 $O(n\log n)$。然而这题卡常过不去。

考虑优化。可以想到的一个贪心是，如果一个元素留在栈底，干脆就让它一直留在那里，直到最后一个匹配上的位置。

具体来说，我们对$s$ 从前往后，尝试将 $t$ 从后往前匹配。但是注意匹配的前提要求有解，换句话说当前元素后面没有被匹配的元素需要和 $s$ 的后缀 Y/N 的数量一样多。可以再维护一个指针，表示未被匹配部分 Y/N 的数量。

复杂度 $O(n)$。