Codeforces 题目选做 IV

feecle6418 · 2022-08-05 16:16:08 · 个人记录

More and more vegetable, what should I do???

Xor Tree

自底向上贪心显然最优。一个代码坑点是，即使这棵子树已经删掉了也要继续 dfs 完，因为子树内部还有贡献。

Multiset of Strings

给定 \{c\} 时，显然可以自底向上 dp；现在计数，就把 dp 值作为状态。卷积即可。

Qpwoeirut and Vertices

Kruskal 重构树。

\color{green}* Chopping Carrots (Hard Version)

空间 O(n\sqrt n) 的做法很显然：整除分块存下值，然后双指针。

其实可以换种方式整除分块，枚举 floor(x/y)=z 的 z 再枚举 y，合法的 x 是一段区间，暴力把所有 x 取出来即可。这样访问 x 的次数还是 O(n\sqrt n)，外加 O(n\log n) 枚举 x,y 的时间，但空间变成了线性。

其实这样还是麻烦了！枚举左端点 l，我们只关心对于每个 i，最小的 \ge l 的值的最大值，设为 f_l。不妨把每个 i 的可能值数组从小到大排序，假设为 [b_1,\dots,b_k]，则执行 f_{b_i+1} 对 b_{i+1} 取 max 的操作。最后对 f 做个前缀 max 即可。这样额外时间也是线性的。

Text Editor

如果固定了哪些位置最终被保留，一定是一段前缀用 right，一段后缀用 left，中间用至多一次 home。据此 dp。

\color{green}* Three Days Grace

这题挺强阿！其实自己走的路完全偏了，但是还是误打误撞得到了一个能过的做法。

我的做法：对于某个数 x，至多有 O(d(x)) 个可行的区间（枚举每个约数作为左端点）。但如果直接用背包 dp 来得到这些区间，预处理时间太大，空间带 log 也存不下。

考虑寻找一些性质：

• 设 L_x 表示最大的 y\le \sqrt{x} 且 y|x。如果最终结果里出现了两个数 a\le b，一定有 a=L_{ab}。
• 如果最终集合里出现了三个数 x,y,z，一定有 xy>z。

其实，上面的性质暗示了合法集合的数量不多，比如二元集合只可能形如 (L_x,x/L_x)。经过爆搜，合法的多于二元的集合只有不超过 2\times 10^6 个，可以存下来。

这样，询问时再加上一元和二元集合（它们只有 O(n) 而非 O(m) 个，因此也存得下来），用这些集合去双指针即可。

题解做法：考虑沿用最初的思路，对于某个 x 及其某个约数 y，求出最小的 z，使得仅用 [y,z] 内的数能表示出 x。直接对此 dp，设 f(y,x) 表示 z，倒序枚举 y，转移：

• 若 y\not| x，f(y,x) 不变。
• 否则 f(y,x) 更新为 f(y,x/y)（这里顺序枚举，类似完全背包，需要 x/y\ge y）

注意到不只有一个数也可以沿用该 dp！第一维可以滚动，所以空间是 O(m)。代码很好写。

https://www.luogu.com.cn/blog/YGB-XU/cf1699e-three-days-grace-ti-xie

PermutationForces II

一看就猜只要每个数往左移动的距离都不超过 s 就合法，证明没细想。

\color{red}* Equal Reversal

牛逼题啊！

我的做法：

先猜个结论：记 A\to B 表示 A 能变成 B。如果 A\to B，A_1=B_1，A_2=B_2，则删去 A_1,B_1 后仍有 A\to B。这结论一眼看上去就很对，但我不会证。

这样就可以从左往右一个位置一个位置构造了，不妨假设现在要让 B_2 归位。注意到，设可重集 S_x=\{a_{i-1},a_{i+1} |a_i=x\}（即，A 序列中所有等于 x 的位置相邻的数构成的集合），则 S_x 不随操作变化。所以，如果 A_1\notin S_{B_2} 就输出 No。否则：

• 如果存在位置 i，A_i=A_1,A_{i-1}=B_2，执行 (1,i)。
• 否则，因为 A_1\in S_{A_2}，一定存在 A_i=A_1,A_{i+1}=B_2。这时，必须要执行一次操作 (k,l)，使得 k\le i,l\ge i+1。如果能执行这样的操作就完了；否则输出 No，因为永远无法把 A_{i+1} 换到前面来。

唯一令人疑惑之处就是第一个结论。根据题解做法，其实可以反向证明第一个结论。

题解做法：

建无向图，连边 (a_i,a_{i+1})。则每个序列给定了原图上一条欧拉路径，每次操作相当于选一个欧拉路径上的环将其反转（不就是 Flip and Reverse 吗！）

我们断言：只要起点终点相同且图相同，就有解。

考察两条路径走过的边中，第一条不同的，设在 x 出现了分歧，A 走了 (x\to y)，B 走了 (x\to z)。根据欧拉路的性质，在走过这条分歧边之前，x 剩余的还未经过的边有奇数 2k+1 条。

• 如果 A 中将 (z\to x) 定为入边（或 B 中将 (y\to x) 定为入边），则翻转 x\to y\to \dots \to z\to x 这个环（或者环反向）即可。
• 否则，A,B 中都有 (x\to y),(x\to z)。剩下 (2k-1) 条边中，A,B 都有 k 条入边，一定存在一条边 (w\to x) 在 A,B 中都存在。A 里翻转 x\to y\to \dots\to w\to x，B 里翻转 x\to z\to \dots\to w\to x 即可。

其实这个做法给出的构造和我的做法给出的构造是一样的。

\color{red}* Long Binary String

牛逼题啊！显然可以看成是 F_2 上的多项式加法，故就是给出 F(x)，问最小的 k，F(x)|(x^k+1)。

如果 F(x) 是数怎么做？变形为 x^k\equiv 1\pmod v，BSGS 即可。其实 BSGS 套到多项式上也可以，而且由于 \gcd(x,F(x))=1 保证了逆一定存在，所以不存在任何特殊边界之类的。

这题很有启发意义。虽然核心题解就一句话（用 BSGS），但惊人地长的思考时间后（actively try 的时间应该有三个小时以上）才发现这一点，可能是因为需要真正的思维”延拓“？其实也体现”化归“的技巧不熟练。

\color{green}* Serega the Pirate

又双叒叕做麻烦了！

我的做法：假设从前往后扫描第一个不合法位置是 p。那要么把 p 和后面某个数交换，要么把 p 前面的某个数和 p 后面的某个数交换。

通过用并查集启发式合并动态维护“每个点相邻的有几个比他前”这个信息（这里想错过一次），再加上分段分类讨论合法的条件，是可以得到 O(nm\log nm) 的解法的，常数很小，但细节很多。

题解做法：注意到，如果交换某两个至多使得 4（度数）个点变得合法！所以可能参与交换的格子只有 4\times (4+1)=O(1) 个，因此分别枚举判断即可。时间复杂度 O(nm)。

\color{red}* Puzzle

思想非常重要：先最小化什么，再最小化什么。（道路费用）

因为只有两列，容易发现横着走的最小步数（\sum |s_i|）必定取到。在此基础上，我们要最小化竖着的步数，那横着走配对要尽量和同一行的配。所以，当务之急是搞清楚什么配对情况下能取到这个最小步数，找出条件，然后在条件限制下尽量同行配。

容易发现，条件就是类似于括号匹配，如果出现了右括号可以匹配前面任意一个左括号，但不能留着，除非没有左括号。据此贪心即可。

Ambiguous Dominoes

考虑直观化思考，把多米诺骨牌视作连接格点的边，两种方法分别着色黑、白，得到一个图，图的边有两种颜色，并且图由几个回路拼成，回路走的边还是黑白交错的，回路覆盖了所有边。

所以做法就很显然了，建出该图，求一条黑白交错的欧拉回路即可，容易发现只要连通块边数不只 1 一定有解。把每个回路放到一个 2\times sz 的长条里即可构造方案。注意欧拉回路是出栈的时候加边！

Coloring

被阴到了，O(n^2) 出 n\le 100，3 秒？

直观化思考，发现就是要求每个同色连通块

• 内部距离全相同。
• 往外的距离都要严格大于内部距离。

这个条件就是 Clusterization Counting，做法也一样，树形背包。

\color{green}* ANDfinity

先忽略 0，答案至多是 2，考虑 lowbit 最大的数，减一之后它和所有 lowbit 比它小的数连通了。如果有多个 lowbit 最大的数就再选一个加 1，所有都连通了。于是暴力枚举第一次操作 check，O(n^2\log V)。直接线段树分治可以 O(n\log n\log V)。

然而有更高明的 O(n\log V) 做法，需要观察一点性质：

• 如果操作是 +1，操作的一定是偶数。由此，判断“+1”操作是否可以就只需要看是否恰有两个连通块，并且一边有奇数。

  证明：若操作奇数，则该点会少连接很多边，多连接恰好一条边。如果多连接的边使得图连通了，考虑连通的另一头，那些数一定是含有这一位的偶数，因此不如操作那些数。

• 如果操作是 -1，操作的一定是 lowbit 最大的数。由此，可以枚举操作谁，并预处理 lowbit 取到最大的数的前缀后缀 OR，以及所有 lowbit 非最大的数的 OR，这样就知道操作后该数与其它 lowbit 最大的数还是否有边。

  证明：若不然，首先，操作的数一定在操作前就和 lowbit 最大的数连通。否则，操作后不可能变得连通。这说明 lowbit 最大（设该位为 i）的数所在连通块内有数同时包含 <i 的位和 \ge i 的位。

  • 若存在同时包含 <i,=i 的位的数，一定合法。
  • 若不存在这样的数，一定存在同时包含 <i,>i 的数，并且这样的数至少有一个和 lowbit 最大的数直接有边。那不如操作那个数。

\color{green}* Number of Groups

两个区间有交当且仅当其中一个包含另一个的某个端点。因此做两次，每次把白色线段插入线段树，查询黑色线段的过程中暴力 merge。

还有更简单的方法。若某个点被两种颜色的线段包含，称其为关键点。只需取出关键点，把每个区间包含的“关键点区间”取并。

K-set Tree

算贡献。

Labyrinth Adventures

线段树维护有结合律的信息。

Unique Occurrences

建虚树求 size。其实可以把所有颜色一起做：https://www.luogu.com.cn/blog/LinkZelda/solution-cf1681f

Hemose on the Tree

显然答案是 n，构造方案：随便选一个点当根，填 n。接下来，对于某个点和其父边，根据深度奇偶性填 (x,x+n) 或者 (x+n,x)。

Jee, You See?

数位 dp。

Star MST

固定 (1,i) 的权值 a_i 后，剩下边 (x,y) 的方案数是 (k-\max(a_x,a_y)+1)。按照 a 从小到大 dp，同时赋顺序即可，O(n^2k)。

Words on Tree

直接对给出的条件间互斥关系建 2-sat，因为字符串长度总和很小，所以可以暴力爬树。

Sum of Matchings

枚举每个环上连通块算贡献。

Tower Defense

首先，怪物移动速度都相同，根据相对性可以认为速度都是 0。注意每次一定推平一段前缀，用栈维护推平时间相同的连续段，每次暴力弹栈。其中涉及到询问“最小的 r，满足 [l,r] 区间内 \sum \min(Rt,C)\ge V”，可以对 C/R 建线段树，线段树上以 r 为下标。这样就可以线段树上二分了。