2023.8.8 做题记录
CF525D
题意：有一个仅含 .，* 的图，现要求更改一些 * 使得原图中由 . 组成的联通块是矩形。
分析：这题本身思考方向比较单一，着眼点仅在于这两种符号的规律，但是这两种思考方向都会导向出一个相同的结论：
当且仅当一个 \(2\times 2\) 的方格以这四种方式排列时：
.* *. .. ..
.. .. .* *.
无法组成矩形，其中的 * 需要被消除。
考虑到消掉一个 * 会对其他 \(2\times 2\) 方格造成影响，因此需要在消除掉这个 * 时，继续对其他八个方向进行判定。
复盘：一开始想的是通过连通块的判定来考虑如何消除，但是忽略了这个比较基本的结论。
因此，做题时还是要紧扣题意，多角度去想，推断一些基本的结论。
CF237D
题意：给出一个 \(n\) 个点的树，现要求构造一个由 \(n\) 个点集组成的新树，满足以下几个条件：
记 \(V\) 为原树的点集，\(x_i\) 为新树的某个点集。
- \(x_i\) 是 \(V\) 的某个非空子集。
- \(x_i\) 的并集等于 \(V\)。
- 对于 \(\forall u,v\) 满足原树中 \(u,v\) 有连边，都在新树中能找到一个集合满足 \(u,v\in x\)。
- 对于 \(\forall a\in V\)，在新树中包含 \(a\) 的集合能组成一个连通块。
请在最小化新树中最大集合大小的基础上，给出集合总数最小的一个方案。
分析：这题两个最小化条件不难想，首先由于第三个条件，显然一个点集的大小最小是 \(2\)，因此只要把点集的大小都设为 \(2\) 即可，即是把每个边所含的节点作为点集的元素。
第二个最小化也比较显然，因为这样构造，树上肯定有 \(n-1\) 个节点，相当于原题把两个下界都已经给了我们。
这时候我们可以发现前三个条件已经满足了，考虑如何满足最后一个条件。
不难想到，一个节点与他的儿子之间的连边所构造的节点在新树可以组成一条链，且除去他儿子所在的链，其他链都不会出现包含他的儿子的集合，所以这种做法是合法的。
复盘：这题有一些诈骗，但是如果仔细想的话很容易发现两个限制条件就引导了这题的方案构造，因此，遇到条件较多的问题，可以尝试寻找条件与问题解法之间的关系。
CF1029E
题意：给定一颗有根树（根节点为 \(1\)）。要求往树中加入一些边使得从根节点到其他节点的距离至多是 \(2\)。 求加入边的最小数量。(边全部都是无向的)
分析：从最远的节点考虑，如果一个离根节点最远的节点（与根节点距离大于 \(2\)）想要满足条件，有两种方式：
- 直接与该节点连边。
- 与该节点的父亲连边。
第一种方式只能使得该节点与该节点的父亲满足条件，而第二种方式可以在第一种方式的基础上在使得该节点的兄弟和他父亲的父亲满足条件，显然更优。
于是我们不断与该节点的父亲连边即可。
复盘：这题贪心还是比较巧妙的，有一定的逆向思维因素在，同时是在原来的结论下进行一定的运用，很有学习价值。