AGC002

AGC002C

找到一个结两边和不小于 $L$ 然后把剩下的依次删除即可。如果不存在显然无解。

AGC002 D

首先一种不动脑子的做法,直接建 kruskal 重构树然后二分 + 倍增跳即可。复杂度 $O(n\log^2 n)$ 。

然后,通过整体二分 + 可撤销并查集也可以做。但是可撤销并查集无法路径压缩,所以也是 $O(n\log^2 n)$。

然后其实是可以做到单 $\log$ 的。

如果我们按照 bfs 的顺序来做整体二分。如果当前加入的边超过了我们期望的边,那么就删掉所有边重做。不难发现由于是 bfs 序,这样的重做操作只有 $O(\log m)$ 次,所以复杂度就是单 $\log$。

AGC002 E

大概算是学到一个套路操作?(下面图源官方题解)

考虑删除操作,本质上就是:

image.png

然后,可以发现本质上就是再这样一个表格上从左下角开始走,知道走到某个边界点就结束了。

image.png

所以我们可以认为边界上的点是 “先手必胜” 点,然后每个点由它的上方和右方做 mex 来决定。不难发现一个对角线上的胜负情况一定相同。

然后一个对角线的情况取决于它上方第一个凸出去的点以及右方第一个凸出去的点与它的距离的奇偶性。如果由任意一方距离是偶数,那么这一个对角线的上方或右方就全是必败,所以这条对角线必胜。否则这条对角线先手必败。判断一下即可。

AGC002F

神仙 $dp$ 题。

发现可以把白球独立出来看。相当于要放 $n$ 个白球,放 $k-1$ 个 $n$ 种颜色的球,满足对于一段前缀来说白球的个数大于等于颜色的种类数。

然后我们把每次的决策分为两种,往当前序列里面最前面的空位塞一个白球,把某种颜色的所有球都塞进去。然后为了保证转移不重,我们让每次塞一个颜色的时候第一个球一定放在当前第一个空位。

然后状态转移就很显然了

文章作者: yijan
文章链接: https://yijan.co/2020/11/18/agc002/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog