Codeforces 杂题选做 I

feecle6418 · 2022-03-09 22:17:57 · 个人记录

省选快要退役了，非常慌。（more and more vegetable what should I do?）

\color{green}*Black and white tree

换根 dp，充要条件是，存在两个点，两个之中一个到 lca 距离 \le 1。

不过上面做法其实是麻烦了，考虑子树内部推上来，当且仅当

• 儿子能到某个黑点，且儿子内黑点数 \ge 2。

这就真的是 simplify 的魅力了！！

credit：https://www.luogu.com.cn/blog/dottle/solution-cf1626e

\color{green}*A random code problem

容易发现只与 a_i 模上 lcm(1,2,\dots,k-1) 的余数有关。

对每个余数分别 dp，设 f(x,y,z) 表示有几种方式用了 x 次操作，a_i 减了 y，总贡献是 z，复杂度 O(720720\times k^7)。

可以把 z 压掉，设 f(x,y) 表示方案数，g(x,y) 表示贡献和，复杂度 O(...k^4)。

观察到最终求的是 \sum g(x,y)A^x，可以把 x 这位压掉，层间转移乘上 k 的系数，O(...k^3)。

经过卡常，是可以通过的。

然而这种做法忽略了各个值之间的联系。x 做一次变成了 y，y 的信息是可以利用的。

可以设 f(y,z)：做 1\sim z 的操作 x 变成 y 的 方案数 * 原数组中 x 出现次数的带权（操作 o 次，权就是上面的 A^o）和，层间转移乘上系数，可以发现这样是 O(...k) 的。

credit：https://www.luogu.com.cn/blog/sysjuruo/solution-cf1626f

Not escaping

伞兵 dp 题。

\color{red}*Cats on the upgrade

非常好的题！

考虑对括号的包含关系建一棵 括号树，每层括号的儿子就是其内部包含的第一层括号。

给每个点赋值 1+\binom{cntsons}2，表示在这个点这里产生了这么多个 RBS。

那么 easy ver 就变成了子树求和。hard ver 就是从叶子一层一层删上去，只需要用树状数组维护子树和，删的时候顺便算一下 cntsons。对于儿子有多个的点，还需要开一个树状数组维护儿子，因为可能问到一个点的中间（同样地，dfs 序需要保证一个点的所有儿子按位置顺序排列）。

这个题高明于 gyh 出的 艺术家？打脸了 连删除方式都一模一样 这两个题好像完全没区别 唯一的区别是他给的“树”非常隐蔽。

Bipartite array

注意到只要有三元环一定不行。

换个角度，没有三元环，意味着除去前缀最大值剩下的数也是递增的，所以一定是二分图。

也即，充要条件是能分为两部分，都递增。

设 f(i,0/1) 表示 i 取正 / 负的时候 i 不在的那部分的最小值，O(n) dp。

Subsequences galore

容斥，就成子集和变换了。

\color{red}*Too many imposters

其实流程真的是 试错+brainstorm，可惜这种题太少了。

首先分成 n/3 段，每段问出 01。由于题目给的条件，一定至少有一个 0，至少有一个 1。所以一定有相邻两段一个 0 一个 1。abcdef 如果 abc 0 def 1，abc,bcd,cde,def 一定会有两个相邻的是 01。于是就找到了一个 0 一个 1，拿这两个去问出其他的就可以了（这是寻找关键元）。

但是这样要 n/3+n 次询问，可以直接在块内分类讨论优化掉一次询问，看代码就知道了！https://codeforces.ml/gym/367154/submission/145191339

\color{green}*Christmas chocolates

这就是典型的，OI 赛场上做麻烦不影响，CF 直接导致爆炸的题！

题解做法：注意到 x\to 2^k-x 是树形关系，于是求树的直径，从 1 开始找两遍最远点，模拟即可。

虽然很简单但是……

Flipping Range

注意到可以把长度取 gcd。

考虑差分。

对于固定的长度 l，设取不取反变量差分之后为 c，注意到 c_x+c_{x+l}+\dots\equiv 0\pmod 2。可以先把所有负的取反，最后剩余系 S 中的 c 是奇数。那么要把 S 中的两两配对，显然只有两种方式。

如果配对的 1,2 都是奇数，那肯定应该取 1 中最小的，而非 2。因为这个错了两次。

https://codeforces.ml/gym/367154/submission/145206849

\color{green}*Divan and Kostomuksha

直接 dp O(m\log m)。dp 时只枚举质数倍数（显然，只是增加了中间步骤而已）就 O(m\log \log m)。

Divan and a cottage

动态开点线段树上二分出分界点（因为总是增函数）。直接模拟。

Array equalizer

从前往后做可以发现，不存在最优化的问题，方案唯一。进一步发现贡献也是定的形式：|A-a_1|+|B-a_1|+\dots 直接前缀和 + 二分就可以。

Middle Duplication

简单贪心题。如果没有 父亲 - 儿子 的限制，肯定是从前往后能选就选（预处理后一个不同字符）。

现在有了 父亲 - 儿子 的限制，注意到左儿子总在我前面，右儿子总在我后面，如果左儿子里面有一个能够变小的点，那一定会变小，就算会导致我这里变大，我也在左儿子之后。

所以贪心策略是：

• 先递归左儿子，如果需要 duplicate 就把祖先链都 duplicate。
• 如果回溯时发现自己已经 duplicate 了，再去递归右儿子，否则直接返回。

\color{red}*Math Test

最大化含有绝对值的式子的和，可以枚举绝对值的正负号，分别求最大值。因为只要正负号不对就会使答案变小。

\color{green}*Quadratic Set

首先注意到答案总大于等于 n-3，找规律可以发现

• 答案是 n-1,n-2 的时候，删掉的数总在 n/2 与 n 旁边。
• 答案是 n-3 时，n-1 答案总是 (n-1)-2。

故枚举所有可能的删数情况即可。判断合法性比较麻烦，我用到了 floor_sum。

题解给出了更高明的做法：对质因子随机赋哈希值，那可以 O(1) 判断合法性。这样删去 0,1,2 个的都可以构造方案。

接着对 3 个的直接给出构造。

• 如果 n 是奇数，直接删去 n。现在把 (2i-1)!,(2i)! 配对，可以发现只剩下了 2\times 4\times \dots
• 如果 n/2 是奇数，删去 2!，现在 2 的幂次也是偶数。可以直接忽略。
• 剩下的就是 (n/2)!，删去 n/2 即可。

感觉构造还是挺妙。

Tree Coloring

没有变钦定，如果钦定了某些点满足题述条件，其实总方案数就是 (n-C)!。因为每个由钦定的点及其父亲构成的连通块（只能是链）可以看做整体来排列。

现在考虑怎么算选点（其实是选边）方案数：其实就是每个点至多选一个儿子。故就是算 \prod (1+cntsons_ix)，分治 NTT 可以做到 O(n\log^2 n)。

然而有 O(n\log n) 做法，对于同一种 cntsons，将其合并，合并的结果是容易计算的组合数形式。

接着按照 cntsons 从大到小暴力把所有多项式卷起来。

卷积总次数是 \sum_i\sum_{j\in cntsons}[j\ge i]=O(n)。

Crazy Robot

BFS，看周围是否至多有一个方向是目前没有 BFS 到的。

\color{green}*Max Sum Array

我的做法：注意到最优解是按照如下方式生成的：首先把个数最多的放进序列，将序列划分为 2cnt+1 个段，然后个数少的按照奇偶性放在最中间的奇偶性相同的段中。方案数即为每个段内部随便排列方案数乘积。

比如：cnt_{1\sim 3}=6,5,2：

|1| |1| |1 | |1 | |1| |1|
|1|2|1|2|1 |2|1 |2|1|2|1|
|1|2|1|2|13|2|13|2|1|2|1|

这样可以 O(n+a_i) 算方案数，但总代价不好统计（其实是我傻了，算每个位置的贡献即可），我用了线段树。

题解做法：

注意到无论 i 出现在哪些位置，这些位置对答案的贡献系数都是定值，即 1-cnt,3-cnt,5-cnt,\dots,cnt-1。

由于最优方案要最大化贡献和，如果为我们忽略位置关系，最终排出来的位置里面，也一定是 1-cnt,3-cnt,\dots 从左往右顺序排列。

故把贡献系数排个序，按照从小到大的顺序安排位置即可（其实和我的做法就一样了）。如果有很多贡献系数相同，它们可以随意排列，乘上 cnt!

\color{red}*Armor and Weapons

如果 n,m 都差不多大，显然操作次数是 \log 级别的（斐波那契数）。故可以设计 dp，f(x,i) 表示 Armor 一边得到了攻击力为 x 的装备，总共做 i 次操作，能得到的最大攻击力 Weapon。

注意到，就算 n>>m，操作次数顶多变多 O(n/m) 次。这引导我们把 x 这一维取到 \min(n,m) 那边上，总复杂度 O(\min(n,m)(\max(n,m)/\min(n,m)+\log (n+m)))\\=O((n+m)\log (n+m))。

Tree Queries

这题和 Eert Tuc Knil 一模一样，粘过来就过了。

还有一个 n\sqrt n 的做法。