CodeForces 做题总结

· · 个人记录

本来最初计划每道都写篇题解的啊，但是写不动，或者自己想不出来就不想写，于是在这里简要总结一下。

题目全部来自于 cf, 难度大多为 *2600 和 *3000。

看题解才想出来的后面会打星

CF1762F

*2600

发现每一对符合要求的点对都有一条单调不降/不升的路径，于是考虑单调不降怎么做。

考虑到从后往前扫，对于每一个点找到第一个大于它的点，那么这个大于它的点能走到的点，当前这个点一定能走到；此外大于当前点但是小于第一个大于它的点的所有点也是可达的，于是前一部分直接转移，后一部分开一个权值线段树维护。

CF1762E *

*2600

首先发现只有 n 为偶数时这样的树才会存在。其次一条边边权为 1 当且仅当这条边两边联通块中点的个数都为偶数。

然后考虑按边算贡献。设两侧联通块其中一个联通块点数为 x，则另一个为 n - x。除去边两边固定的两个点，从剩下 n-2 个点中选出 x-1 个点扔到一边的方案为 C_{n - 2}^{x - 1}；由 x 个节点构成的无标号无根树的数量为 x^{x-2}；两个联通块中各选一点连边的方案为 x(n-x)。所有答案就是 \sum_{i=1}^{n-1}{(-1)^{i}C_{n - 2}^{i - 1}(n-i)^{(n-i-2)}i^{i-2}}x(n-x)。

CF1815D *

*2600

发现只有 m=2 的解是不平凡的。按位 dp 即可。

CF1827C

*2600

link

CF1823F *

*2600 link