CF 2600-3000 板刷记录

PosVII · 2023-03-07 21:55:44 · 个人记录

过去的事情都过去了，人生没有这么多如果。这一次的失败不怪出题人不怪任何人，是我这么多次看懂一道题思路就以代码难写不写代码的恶果，因此专开一栏记录自己卷题记录，练练思维，也练练码力。

2600 以下的题太水了，不做。

一眼换根，但是确实挺难调的，可以 O(n)，但是用 map 就好写多了。

首先不考虑根不定的情况，这个时候题目就变成了把树划分成不能拐角的链，要求最小链的最大大小。

这时候就是一个 树形dp 再加上一点小小的贪心：因为对于结点 p，其每一个儿子 tmp 都在且仅在一条链，此时这个结点 p 就划归与所有儿子所在的链中最小的一条就行了。可以 O(n) 处理。维护每个根所在的链的大小和其子树中不在 p 的链的最小值。

但是此时根是不定的，考虑换根。可以证明，每次对于一个点，把它变成根只需要考虑其父亲的其他子结点所在树的状态，用 map 存储即可快速查找最小值，然后就很好实现了。

一场 vp 打的题。

开始想费用流，显然把空白格点当作流，然后发现每个空白格点能转移的地方都是黑白染色后颜色相同的地方，于是发现我们需要黑和白两个相邻空白格点，它们的转移过程显然不互相影响。然后普通的费用流时间太高，考虑优化，我们不难发现黑和白两个格点都只需各自一个流，将问题转化成为最短路即可。

感觉还是水题啊，但是我琢磨着我也没跳过题啊，怎么都这么水？

这道题一眼二分，二分完大的次数二分小的次数就行了，二分检验的部分可以整个 树形dp，具体的实现是一个一眼的贪心，不说了。

上强度就是不一样。

看每个 a_{i} 对 b_{j,n} 的贡献，显然，这两点间路径数量就为贡献的次数，因为是异或所以看奇偶性即可。我们发现，a_{i} 对 b_{j,n} 的贡献就是 C^{j-1}_{n-i+j}。也就是说 a_{n-i+1} 对 b_{j,n} 的贡献就是 C^{j-1}_{i-1+j-1}

可以证明，对于组合数 C^{i}_{j}，其为奇数当且仅当 i 是 j 的子集。然后我们可以根据这些条件建立起一个异或方程组，可惜时间复杂度是 O(n^3)，不足以解决问题。

当然可以优化，发现这个异或方程组中最多 n \sqrt{n} 个贡献，可以暴力存下来进行求解，但是会被卡。以下是一个异或方程组矩阵的示例（我将 a 数组反了过来，以便简化组合数）

因为这个异或方程组的矩阵建立方式很特殊，感觉有规律可循，希望能利用这个图快速求解。我们沿着朴素的异或方程组思路走，我们想将这个矩阵消出一个斜三角，于是矩阵变成了这样：

然后再按常规思路把除对角线外的东西消掉：

然后就是答案了，我们发现，我们发现，第一步消元中，对第 i 行消元刚好使用了 i 的所有真子集，这个是可以递推优化的。

第二步中，第 i 行消元刚好使用了所有以 i 为真子集的行，这个同样是可以递推优化的。

然后最后的 a 数组就是答案。

超强思维题。

阅读理解。

猜结论题，来不及调了不然就狠狠场切了！