CF 绿蓝题做题记录

题单

最近有在经常随机一些 CF 绿蓝难度的题目，用于提升思维。这里专门开个坑，记录一下思路障碍经验什么的。

自然这些内容也在每天本来的做题记录中就有记录，只不过这里只是把它集合在一起罢了。

CF1438D Powerful Ksenia - 洛谷（同步于 2022.6.14 每日做题记录）

CF 的题似乎总是要善于猜结论。

1. 思路分析：

   首先考虑一次操作可以做什么：

   1. 将任意三个不同的数变成相等的一个数；

   2. 如果三个数中有两个相等，那么相当于把前两个相等的数变成与第三个数相等的数。

   分类讨论。

   • 当 \(n\) 为奇数时，一定可以构造出一组解：

     对于序列里除了一个数 \(a_p\) 之外，其它剩下的所有数均能两两配对，使得原序列变成：\((a,a,b,b,c,c,\cdots,k,k,a_p)\)。那么将 \(a_p\) 分别于前面的每一对相等的数匹配，就可以得到新的全为 \(a_p\) 的序列。

     操作次数 \(n-2\) 次。

   • 当 \(n\) 为偶数时，如果是有解的，且数列长度为偶数，那么最后整个数列的异或和一定为 0。

     在有解情况下，可以先把前 \(n-1\) 个数用奇数的方法求解。

     由于异或和为 0，所以最后一个数一定也与前面的数相等。

     操作次数 \(n-3\) 次。

2. 障碍：

   完全没有想到分类讨论，所以通过这道题积累了一个经验，遇到这种无从下手的题可以从 \(n\) 的奇偶角度分类讨论，也可以从 \(n\) 比较小的情况讨论找规律。

CF1133F1 Spanning Tree with Maximum Degree - 洛谷

1. 题意叙述：

   给出了一个由 \(n\) 个顶点和 \(m\) 条边组成的无向无权连通图。它保证在给定的图中没有自环或重边。

   需要找到这个图的一棵生成树，使得树上顶点的最大度数尽可能地大。

   输出构造方案。

2. 障碍：

   • 走到了一个误区中，刚开始一直想通过二分解决。主要是因为题目中：

     使得树上顶点的最大度数尽可能地大。

     看起来非常像二分对应题目特征的“最大值最小”或者“最小值最大”的情况。

     但其实这里求得是“最大值最大”。所以二分是不可行的。

   • 在用“类 Kruskal” 求解时，没有想到要标记最大位置，以为是对所有的度数为最大值的点无脑加一遍边。

3. 思路分析：

   看到：

   使得树上顶点的最大度数尽可能地大。

   应该想到贪心。

   看到"生成树"，应该想到 Kruskal。

   考虑如何将这两个结合起来。

   要使得树上顶点的最大度数尽可能大，可以考虑首先将度数最大的节点加进生成树中，最好情况下是将度数最大的点所有边也加入到生成树中去。由于我们是贪心，那就先无脑把度数最大点的所有边加入生成树中。

   然后无脑加边，直到所有节点都在树上（可以用 Kruskal），即构成一棵生成树即可。

4. 写挂了的地方：

   每次查找度数最大点时，要标记其位置。不能无脑将所有度数最大点的所有边都加入到生成树中去，这样可能导致构不成生成树。所以我们只要加其中一个度数最大点的所有边即可。