「NOIP2020」移球游戏
个人感觉比 「NOIP2022」喵了个喵 简单
因为数据造的全是颜色 \(1\) 到 \(n\) ，所以代码也不离散化了
假设现在有 \(n\) 种颜色，我们考虑怎么把第 \(n\) 种颜色全部移动到第 \(n+1\) 根柱子上，这样递归下去就可以做出来了
对于每一根柱子考虑，考虑把所有颜色为 \(n\) 的球全部放到一起，假设这根柱子上有 \(sum\) 个，一个初步的想法是随便找一根柱子腾出 \(sum\) 个空位，然后把整根柱子遍历一遍，其实这就是正解，下面给出具体构造方法：
假设我现在在考虑第 \(i\) 根柱子，我让第 \(i+1\) 根柱子腾出 \(sum\) 个空位，将腾出的球放到第 \(n+1\) 根柱子上，然后现在考虑取到第 \(i\) 根柱子的第 \(j\) 个球，如果是颜色 \(n\) 就放到第 \(i+1\) 根柱子上，否则随便放到一根没有提到过的柱子上，注意这里是包含第 \(n+1\) 根柱子的，所以不难发现一定有地方放。
最后要复原，注意我为了腾位置将第 \(i+1\) 根柱子放到第 \(n+1\) 根柱子上的球里面可能有颜色 \(n\) ，所以一定要物归原主，不然就寄了
我的写法被定向卡了，所以要先 \(shuffle\) 一下
CF1804F. Approximate Diameter
首先思考只有一次询问怎么做，发现直接随便找一个点 \(bfs\) ，你求的答案一定在 \([\lceil \frac{d(G_0)}{2} \rceil,d(G_0)]\) 之间，这是显然的，但是有加边操作发现一点也不会了，但是观察现在条件是 \(\lceil \frac{d(G_i)}{2} \rceil \le a_i \le 2\times d(G_i)\) ，后面那个 \(2\times\) 我们还没有用到，发现加边后答案一定是变小，这就启发我们这个答案可以用很多次，那么到底可以用多少次呢？
扔一个结论，我只用 \(log\) 个答案就可以回答所有问题不这么猜复杂度就不对了
考虑怎么证明：考虑我现在算出 \(i\) 的答案 \(a_i\) ，现在我有一个 \(a_j=\lceil \frac{a_i}{2} \rceil\) ，因为 \(\lceil \frac{d(G_j)}{2} \rceil\le a_j \le d(G_j)\) ，所以 \(\lceil \frac{d(G_j)}{2} \rceil\le \lceil \frac{a_i}{2} \rceil \le d(G_j)\) 即 \(d(G_j)\le a_i \le 2 \times d(G_j)\) ，发现还是满足条件的，然后每次 \(a\) 需要更改时都至少乘 \(\frac{1}{2}\) ，所以复杂度就对了
CF717H Pokermon League Challenge
题意：
有 \(n\) 个人，第 \(i\) 个人都有 \(l_i\) 个想加入的队伍
这 \(n\) 个人中的每个人都讨厌一些人，讨厌关系是双向的，讨厌关系总共有 \(m\) 组，并且没有人讨厌自己
你要将这 \(n\) 个人分入队伍中并把这些队伍再分为红蓝两方，使得：
-
每个人都加入了自己想加入的队伍之一
-
红方人员和蓝方人员之间的讨厌关系有至少 \(\lceil \frac{m}{2} \rceil\) 对
-
每个人都在恰好一个队伍里，且每个队伍只能处于红蓝两方之一
构造方案，或者输出无解诈骗的，有解
\(4\le n\le 5\times 10^4, 2\le m\le 10^5, 16\le l_i\le 20, 5\operatorname{s}/256\operatorname{MB}\)
啥东西我都不会证明/ng
但是这个题是直接随
但是直接随又过不了，考虑怎么提高概率，发现我随一个人在哪个队伍非常亏，因为我一共就只有两种颜色，所以我直接随人在那个颜色，每个队伍在哪个颜色就好了，最后判断讨厌限制条件和我这个人有没有集合待就行了
满足讨厌关系限制的概率是 \(\frac{1}{2}\) ，然后一个人没有队伍待的概率是 \(\frac{1}{2^{l_i}}\) ，因为人没有队伍待的概率是不独立的，所以不能直接乘起来，但是可以估算一下这个概率是小于 \(\frac{n}{2^{l_i}}\) ，时限 \(5\operatorname{s}\) 随便过