WC2020游记

OI生涯没有WC没有APIO没有CTSC，有点伤心

Day1

路由器，DP推不出来，冬眠。下午没听懂，冬眠

Day2

没听懂，冬眠

Day3

没听懂，冬眠

Day4

没听懂，冬眠

Day5

考试，打铁了

Day6

咕咕咕

---

题解：

「WC2020」有根树

考场思路：考虑父亲肯定比儿子大，考虑维护集合，就在若干链上有分界线。每次修改时维护分界线即可。但是没仔细想怎么维护 实际上存在更简单的log^2做法：不需维护具体分界线，直接维护两个集合即可。具体来说，使用线段树维护集合。我们关心根集合的min，与非根集合的max。那么在修改时，考虑更新答案，即平衡max与cnt两者。这一操作可以通过线段树上二分找极值点实现

「WC2020」猜数游戏

考场思路：看错题了…之后发现是用若干操作覆盖点集，打了个状压跑路 首先容易用阶的那套理论求出若干关系：即用A可以删掉B。特别的，如果数与模数互质，则换另一套理论：这些数在log次幂内就会变成0 注意到这个关系有传递性，那么考虑一个点什么时候选：只有当不存在可以删它的点的时候 考虑题目要求的东西：每个集合里选多少点。这个可以转化为每个点对多少集合贡献。那么求出有多少点不能选后做一下就好了

「WC2020」选课

考场思路：只写了p=0的分。凸包卷积一下，考场不知道为什么没调出来。 还没补，咕咕咕咕咕咕。听说卷完之后加个爬山就能过。做法上面的基础上是自然的：即对特殊的状压即可。具体细节还没研究。。