Codeforces Global Round 17 简要题解

比赛质量比较不错。题不是非常难但也不很容易想出做法。

A. Anti Light's Cell Guessing

注意判断 \(1 \times 1\) 的情况。

B. Kalindrome Array

一种数一定是删完最优,且只会删两端第一次不匹配的两种数(否则一定不合法),暴力判断即可。

C. Keshi Is Throwing a Party

发现二分长度之后可以直接贪心选择是否加入。

D. Not Quite Lee

用 Bezout 定理,直接考虑 GCD \(2\) 的次幂即可(其他质因子一定满足)。

E. AmShZ and G.O.A.T.

比赛结束刚想出来。

发现不合法的只需要用 \(3\) 个数就能判定了(证明:写出合法需要满足的不等式限制,考虑枚举中间数 \(a_m\),则第一个一定选 \(a_1\),第三个一定选 \(a_{m+1}\),那么如果这一步合法,下一步选择 \(a_2, a_{m+2}\) 一定合法)

枚举剩余序列的第一个数 \(a_i\),因为只考虑相对大小,将它置为 \(0\),则后面非 \(0\) 的数只有最多 \(\log V\) 个,那么直接贪心即可。

F. Mashtali: a Space Oddysey

我们构造使得每个邻边权值和为奇数的点都合法。这种问题可以考虑通过定向欧拉回路解决(因为欧拉回路保证出入度相等)。

如果只有 \(1\) 权边,那么可以直接用树上翻转路径/欧拉回路解决。

因为 \(2\) 权边不影响奇偶性,我们将每个点拆成 \(1\) 点和 \(2\) 点。

新建一个源点 \(s\)。

如果 \(1/2\) 点度数为 \(1\),将其与 \(s\) 相连。如果度数都为 \(1\),则将两者直接相连(这样保证差最大为 \(1\))。这样一定可以满足条件。

注意判断图不连通。

G. AmShZ Wins a Bet

注意到我们删去的是一个合法括号串。考虑一对匹配的括号,形如 (s) 的形式,我们证明存在一组最优方案使 s 全部为空:

  • 如果 \(s\) 只含 (,那么可以改变匹配的括号使 s 为空;
  • 如果 \(s\) 含 ),那么我们不匹配这对括号答案字典序变小。

因此对于每个字符有两种决策:匹配一对极小的括号对并将中间的字符全部删去(需要能匹配上)、不匹配。

注意这相当于在 NFA 上走,所以贪心很难解决。

考虑直接 DP 一个后缀的最小答案。注意每步转移只加一个字符,因此可以直接维护一棵树,用倍增 hash 维护字典序。

好像也有更简单的做法,但是不会。

H. Squid Game

先考虑只有直上直下的链。

考虑一个贪心:从下往上,尽可能在浅的地方放关键点。

类似 NOI2020 Day2T2 那样,记录每条链的底端要求在什么位置必须放关键点,DP 即可。

注意对于 u-LCA-v 链,关键点越浅越优,所以上面的贪心没有满足这样的链,那么在 \(1\) 放个关键点即可。

复杂度可以做到 \(\mathcal O(n)\)。

I. Mashtali vs Atcoder

不会证结论,咕了。

上一篇:14.2.4HTML5约束API验证


下一篇:函数的嵌套闭包以及装饰器的了解