CF Round 819 题解

· · 个人记录

开个坑。争取保持更新最近比赛的题解。争取不要咕。试一下效果。若果没人看就咕了。

个人尝试给一个题目的质量评分，大概是 0~10 分。

4 分算合格。6 分算较好。8 分算很好。

A(5)

如果最后的 (l,r) 不是 (1,n)，那么只有其中一个会改变，并且可以任意改变。

如果是 (1,n)，那么最终是两个相邻的数。

B(6.5)

合法条件即为，除了最大值，所有数的出现次数必须是偶数。

首先 n>m 一定不合法。

假如 n 是奇数，那么可以直接填 n-1 个 1 和一个其他的数。

否则假如 m 是奇数一定不合法，因为这样至少有两个数出现了奇数次，否则填 n-2 个 1 和两个 (m-(n-2))/2。

C(4)

直接递归，每次取不被其它括号包含的所有括号对，这些位置构成一个连通块，然后递归每个区间处理。

D(7.5)

可以发现在两种颜色分别构成树时答案取到 n+n-m，是最优的。

可以直接找一个生成树，由于 m\leq n+2，唯一一种不合法情况是剩下一个三元环。此时将三元环上的的一条边随意调整为另外一条可交换的边即可。

E(5.5)

套路的，将 i 向 p_i 连边，构成若干个环，那么现在的限制就是每个点在环上的的上一个点和环上的下一个点差不超过 1。

分类讨论发现只有 1,2,4 元环合法，对于四元环的限制就是两个对角差不超过 1，可以枚举有多少个 (i,i+1) 被选入四元环，组合数算一算方案，再预处理一下配对的方案，单次 O(n) 是容易的。

F(4.5)

可以看作最小化等待时间。

时间是动的。不好。先平移使得时间不动，这样每个位置可以看成在 [l,r] 之间合法，但时间不会移动。

另外发现，存在一个最优解，使得存在一个位置使得这个位置到达时间为 l_i，否则可以早 1s 出发。

于是令 f_i 表示在 l_i 时刻从 i 出发走到 n+1 的时间，只需要找到下一个需要等待的位置即可，从后往前做一个区间覆盖即可。

G(5.5)

考虑进行了 n-1 次操作的序列，最后一次操作带来的增量一定为 0 或 n-1，再和各种东西取一下上界下界，最终剩下的数只可能是全局最大值或者全局最小值 +n-1。

假设要求最终全部变为 X。

结论，对于除了 b_i=1,a_i=X 的位置，要么不存在合法方案，要么所有合法方案本质相同（即每一次操作的 (a,b) 二元组相同），所以若存在合法方案则答案就是所有等价类出现次数的阶乘的乘积。

可以通过构造证明。

我们称一个位置合法，当且仅当其操作之后变为 X。

对于 b_i=0 的位置，合法的只有一个数，因为数越大会变得越大。

对于 b_i=1 的位置，合法的数可能很多，但只能操作其中最大的一个，如果操作更小的话会导致最大的一个永远不合法。

也就是说每一次对于 b_i=0,b_i=1 的两边分别只有至多一个选择。

假如两边都有，可以用类似的讨论得出其中有一个操作之后会影响其他位置。

上述操作可以直接线段树维护。