20221020考试总结
T1
套路状压题，有一些关于分支的常数优化技巧
T2
有趣的容斥原理题，但是不太适合出在考试。
首先猜想答案比较多，所以考场上直接一个随机化过掉。
考虑两人集合交的大小 \(\sum|S_i\bigcap S_j|\) ，如果能算出这玩意，很容易用鸽巢原理算出答案个数的下界。
考虑每个元素对它的贡献，是 \(\binom{cnt_i}{2}\) 的，所以 \(cnt\) 的分布需要尽可能平均，不妨让它就为 \(cnt_i\)。
所以上面那个式子的下界是 \(\dfrac{n^3}{4}\) 级别的。鸽巢原理，集合总个数为 \(\dfrac{n\times(n+1)}{2}\)，每一个集合先分配 \(\lfloor\frac{n-1}{2}\rfloor\) 个，剩下的数级别是 \(O(n^2)\) 的，因此答案个数是 \(O(n)\) 的，期望随机 \(n\) 次可以找到一组合法解。
T3
能看出很多问题的题。
题目本身不难，但是坑点极多。
考虑转化问题的时候一定要搞清楚转化的前提条件，以及对应的充要条件。
第一次出错：认为选定合法的删除子序列后一定有解，实际上没有位置放 \(1/0\)
第二次出错：认为必须留位置给 \(1/0\)，但实际上有可能根本不存在 \(1/0\)，留位置是没有意义的，需要特判。
另外还有必要提的一点是，这种选择一个元素，移动到任意位置的题，往往可以考虑最终结果，也就是选择了哪些，或者是选择了哪些不动。
和求改为最长不下降子序列最小代价的题目一样，可以考虑补集转化，最多的，能不动的元素个数，就是 LIS，LCS 的长度。
多次出错的原因也就是误以为只要选择合法，那么就一定可以构造合法的方案。
T4
有趣的贪心题。
我们给矿工分级，并认为操作是放一组矿工，每个矿工只能挖一个，\(k\) 级矿工能挖掉距离小于 \(k\) 的点。
考虑有一条线从下往上扫描，我们需要尽可能把矿工往上放，这样能够到更多的点。
先考虑最深的必须放矿工的点，它一定满足，\(k\) 级儿子有一个还没有被挖的宝藏，否则可以继续往上，这一定不劣，不妨从最简单的情况开始。
假设在这个点放了矿工，那矿工必须挖掉 \(k\) 级儿子，否则上面就处理不了了。如果矿工还能挖，那么需要让他把 \(k-1\) 级儿子也尽可能挖，因为如果让父亲处理，需要付出一个 \(k\) 级矿工的代价，但是这个点的矿工上到父亲的时候降级为 \(k-1\) 级，矿工等级显然越高越好，对于等级低的儿子，在这里挖可以看成于先上去降级再挖。
所以在第一个必须放矿工的点，矿工必须挖掉 \(k\) 级儿子，尽可能挖 \(k-1\) 级儿子，意思是如果还有 \(k-1\) 级儿子没有挖完，那就没必要再放矿工，可以留给父亲处理。
接下来的点就有不同等级的矿工了，对于 \(i\) 级矿工，他会尽可能挖掉和它同级的儿子，如果还有剩余，会挖掉 \(i-1\) 级儿子，这个过程一定要从等级小的矿工到等级大的矿工考虑，否则会变劣。
剩余的矿工降级后上传，儿子升级后上传。
按照这个策略贪心即可。