2023.6
1. Niyaz and Small Degrees
这个题做完才发现是 APIO2021T3 的原题，感觉当时被这套题干爆的时候还近在眼前。
考虑确定 \(x\) 的话有一个比较显然的 dp + 排序后贪心的 \(O(n\log n)\) 解法。
我们考虑如果一条边 \((u,v)\)，在 \(x\ge \max\{deg_u,deg_v\}\) 之后就不会删了；如果 \(x\le \min\{deg_u,deg_v\}\) 那我们保留这条边；这样 \(n\) 个时刻的连通块大小显然还是 \(O(n)\) 的，问题就在于介于 \(\min,\max\) 之间，这个时候是一个存在的点挂了一个限制已经无所谓的叶子。
考虑对连通块的每个点做树形 dp，用数据结构维护每个点挂着的额外的叶子（按照 weight 排序），然后合并的时候我们需要一个和额外挂着的叶子的数量无关的做法。
考虑实际上是把两个序列归并起来：一个序列是额外的叶子，一个序列是所有的儿子。
第二个序列的大小是可以接受的，所以我们在他上面二分出到底要选多少个，这样的话我们的数据结构只需要支持 k-th prefix sum 还有 \(\le x\) 的值的个数两个东西，用平衡树去维护即可。
这样时间复杂度是 \(O(n\log^2 n)\) 的。
记录
2. Puzzle Lover
这个题初看不难，但其实细节讨论很多，非常考验实现（当然也能写的很短）。
对于 \(k\le 2\) 的需要特判，因为他们可以只在一列间游走。
如果只能走左右上三个方向那是比较容易 dp 的，但多了一个方向就比较困难。
发现走回头路一定在开始和中间：换言之假设起点在终点的左边（同一列最后单独算）则就是起点向左再向右，然后中间段是右上下三个方向，到终点所在列的时候进入第三阶段：向右再向左。
第二个过程用 dp 算，第一个过程暴力枚举两个边界作为初始值，然后把第二过程的值用到第三过程的枚举上。最后反过来再做一次，时间复杂度 \(O(n^2)\)，判的时候要用哈希。
好像还卡哈希模数，素质真低。
记录
3. Number of Binominal Coefficients
根据 kummer 定理，组合数 \(\dbinom{n+m}{m}\) 含 \(p^a\) 的幂次，等价于 \(n,m\) 在 \(p\) 进制下做加法的进位次数。
因此问题变成了求 \((x,y)\) 满足 \(x+y\le A\) 且两人在 \(p\) 进制下加法进位次数 \(\ge \alpha\) 的对数。
把 \(A\) 转成 \(p\) 进制后暴力数位 dp，时间复杂度 \(O(len^2)\)。
记录