P12705 呃呃
- 鸽巢原理运用
通过鸽巢原理找到原问题的一个必要条件，从而缩小预处理的规模。
在此题中，每一次计数会使两个数 \(+1\) ，当有数到 \(2\) 时一定有解。
[20260418] 关卡
对于一种不同排列形式，存在不同代价。给定树形的限制，顺序必须是树的一种拓扑序，求最小代价。
此题的代价为 \(\sum_{i=1}^n c_i\Pi _{j=1}^{i-1}p_j\) 。
- 考虑没有树形限制，推出排序关键字。
先只考虑两个数的情况，若 \(u\) 排 \(v\) 前更优：
得到 \(\frac{c_i}{1-p_i}\) 就是关键字，对于多个数的情况，可以用调整法证明。
- 考虑树形限制
树形限制一般使用从上到下和从下到上两种方法，但这类模型两种方法都不见得能做，我们考虑一种每个点向上合并的方法。
Lemma：对于任意子树，选了根之后，若关键字最优的节点是根的儿子，下一步直接选这个儿子一定不劣。
proof：调整法。
首先视每个点为一个连通块。对于上述的根后直接选一个儿子，相当于儿子的连通块合并向父亲，将连通块数量视作势能，通过合并操作我们能得到一个代价相同势能减小的状态。
具体的，找到全局最优的节点，将它向它的父亲合并是满足条件的，合并的变化为 \(c_u+=c_v，p_u\times =p_v\) 。反复执行，知道连通块个数为1。
可以用可删堆实现，用并查集维护连通块，时间复杂度 \(O(nlogn)\)。
Minesweeper
- 平面图
结论：对于无向连通平面图，存在一种边定向的方式，使得每个点的入度不超过 \(5\)。
proof：连通平面图满足 \(|E|\le 3n-6\)，根据鸽巢原理，可知度数最小的点度数 \(\le 5\) 。那么每次将度数最小的点取出来，将与它相连的边都指向它，并将它删除，递归到子问题。
Kodowanie macierzami [B]
- 图同构一种判法
每个点的初始信息为其度数。接下来称一轮操作为将每个点的信息变成其领域信息的可重集（可以用集合hash）。多做几轮就很对了。