CF1975 记录

一些吐槽

考虑到我老是忘记自己做过什么题，而且这次打的实在太唐，就打算每次 vp 或者比赛完补完题写个总结，先说结论，D 分讨了一年然后胃疼去睡觉，三题遗憾离场，赛后发现状态好冲到 F or G 问题不大，寄。

A 到 C 不标注数据范围。

CF1975A

给定一个序列，问是否能在若干次切断-交换操作后使其单调递增。

简单题，但是想了五分钟，怎么回事呢？

考察一个操作可逆，思考一个递增序列操作若干次之后会怎样，不难发现肯定是先由 \(\text{ABCD}\) 变成 \(\text{CDAB}\) 这样一个一半递增另一半也递增的序列，然后继续手玩发现每次切出来都这样，所以你只要枚举判以下原序列是不是一半一半递增即可。

CF1975B

给定一个序列，问序列中是否存在两个数 \(i\) 和 \(j\) 使得每个数要么是 \(i\) 的倍数要么是 \(j\) 的倍数。

比 A 简单。考虑去重排序，最小数一定是两个数其中一个，从小到大扫看有没有冲突的，有久设成 \(j\) 然后继续比。

CF1975C

给定一个颜色序列，你每次可以选一个子数组将它所有位置的颜色全染成该子数组颜色中位数的颜色，问颜色最大是多少。

简单分讨。但是赛时想了有点久，感觉不太会猜结论。

考虑每个数是否能留到最后，如果旁边有数比它大一定可以，如果有数隔一个比它大也一定可以。其他情况似乎只能上一个小于变 -1 大于变 1 的 trick 然后线段树维护。

但是真的需要这样吗？考虑如果有其他情况还可以，那一定是 \(\text{AAACCACCA}\) 其中 \(\text{A}\) 是大于等于该数的数，\(\text{C}\) 相反，不难发现如果有出现这种情况一定有连续的 \(\text{A}\)，那你完全可以不用考虑当前这个点了。

CF1975D

给定一棵数和点 \(P_A\) 和 \(P_B\)，一开始所有点都是白色，\(P_A\) 走过白点会把它染成蓝色，\(P_B\) 走过蓝点会把它染成红色，每个时刻 \(P_A\) 先走，两个点都必须走一步，问最早什么时候树能变成全红。\(n \leq 2\times 10^6\) 。

现在看来简直是弱智题，当时没仔细考察性质一直在分讨，警钟长鸣。

考察 \(P_B\) 第一次走到 \(P_A\) 走过的节点之后怎么走最优，不难发现这之后最短答案就是 \(2(n-1)-maxdep\)，原因在于你必须走到每个节点，且在他们相遇之前或之后，\(P_A\) 可以走到相遇点的任何一个子树（分讨在于 \(dep_{P_B}\) 的奇偶性）。

然后我们就要最小化相遇时间，虽然 \(maxdep\) 也有影响但是你为了 \(maxdep\) 延长的时间其实得失抵消或者得不偿失。

CF1975E

给定一棵树，初始所有节点都是白色，每次翻转一个节点颜色，然后问现在所有黑点是否构成链（必须是联通块）。\(n\leq 1\times 10^5\)。

赛时一直在想什么静态 toptree 上 ddp 这种东西，虽然思维难度没有，但是大分讨，感觉我是蠢货。

这个东西看着就性质很好，我们看看能不能找个充要条件直接判掉。

首先是联通块，考察一个节点怎么连在联通块，要么是块根要么连着父亲，不难发现我们只要判有多少个节点父亲没染色就行。

接着是链，先把大于三个儿子和至少两个节点两个儿子判了，然后还有个特殊情况是一条直链分叉，判以下有两个儿子的节点父亲是不是黑色就行。

CF1975F

你需要求出一个集合 \(S\subset \{0,1,2,\cdots,n-1\}\) 满足对于任意 \(T\) 都有 \(|S\cap T|\in f_T\)，\(f_T\) 给出。\(n \leq 20\) 。

首先有个暴力做法：枚举所有的集合然后检查是否对所有约束都合法，这显然不太能过。

这样做的缺点在于你对两个相差不大的集合进行检查时会进行一些冗余操作（这也是大多数类似问题的突破口），于是我们考虑能不能用一些方法压缩约束快速判断。

考虑什么样的约束容易合并，由于这题里集合类似的约束其实相关性很大，我们尝试把这样的约束合并。

考察集合 \(S\) 和集合 \(S \cup v\)：

• 如果我选 \(v\)，那么 \(S\cup v\) 的约束直接右移一位和 \(S\) 并上就是在剩下里面选数的约束

• 如果我不选 \(v\)，那么 \(S\cup v\) 的约束直接并上 \(S\) 就是新的。

注意这里讨论的是约束不是合法取值，所以用并，合法取值是类似的。

有了这个性质其实解法就很明了了：我们从高到底考虑是否选取当前位置上的数，然后根据选择合并约束，最后判断即可。

简单来说就是考虑合并约束然后关注只差一个元素的两个集合，找到性质分治下去。

CF1975G

给两个包含小写字母、\(\text{*}\) 和 \(\text{-}\) 的字符串，你需要把 \(\text{*}\) 换成任意可空字符串，\(\text{-}\) 换成任意小写字母，问能否使两个字符串相同。\(n \leq 2\times 10^6\) ，时限 12s。

感觉是套路题，先把开头末尾都是 \(\text{-}\) 或者字符的判了，然后剩下的两个字符串如果都有 \(\text{*}\) 那么不难发现一定合法，否则就是把没有的字符串里所有小子串放到另一个里面找匹配，这个可以 NTT 优化，但是注意每次只需匹配小子串长度的两倍，没有则可以删掉一倍长度，直接匹配开销太大。

CF1975H

给定一个字符串，你可以任意重排，定义一个字符串的权值是该字符串的最大字典序后缀，问你能达到的最小权值是多少。\(n\leq 1\times 10^6\)。

妙妙题，一个容易想到的做法是每次加字符然后转判定，但是你发现这个判定不是很能做，于是考察这个最小字符串的一些性质来直接求解。

首先，开头肯定是最大字符，我们设其为 \(m\)，如果整个字符串里只有一个最大字符，那答案显然就是 \(m\) 否则答案肯定是一个 \(m\) 开头的字符串，其中洒着若干 \(m\)，设其为 \(ms_1ms_2ms_3\)，值得一提的是结尾肯定也是 \(m\)，因为如果不是的话我们可以考虑把 \(s_3\) 放到某个 \(m\) 的前面，答案肯定变小。

由于我们只用考虑第一个 \(m\) 后面所有的字符，我们肯定会尝试先枚举用了几个 \(m\)，然后考虑怎样在 \(m\) 中间插入字符使得最大后缀最小。但是这个也很难做，思考一下原因，发现其实是限制太死了，我们不能直接把答案字符串固定。

考虑弱化一些条件，比如我们不固定 \(m\) 的个数，先考虑目标字符串把 \(s_i\) 排序之后的形态，之后再把 \(s\) 换序找后缀，也即确定所有 \(s_i\)。你发现如果我们能找到其中一个最优解对应的 \(s\) 集合，那整个问题就被缩小成了一个规模更小的子问题，我们要把所有绑定完的字符串换序找最小，这好像很行。

考虑我们应该怎样确定 \(s_i\)：

• 如果最大字符的个数大于其他字符个数，那显然就是把 \(m\) 接上小字符，最后剩一些零散的 \(m\) 一起递归下去。注意如果最大字符个数很大，需要压缩操作过程。

• 否则考虑从小到大枚举其它字符，插到 \(m\) 后面，你可能会想直接从左到右分配几遍就行，因为要保证长度尽量平均，但是有一个性质是如果有 \(mc\) 和 \(md\) 其中 \(d\) 比 \(c\) 大，那么后面的字符如果接在 \(d\) 后面会更优，这个简单分讨就能证明。

最后只要递归到平凡的情况即可。