A 送信卒
考场上唐了，把方向搞反导致挂零。。。
然后就是跑一边 bfs，算出来最短路，并且记录横纵位移，就好了。
好像也可以二分然后去跑 djikstra。
其实有个 hack，会让我的代码在特定情况下不稳定地输出错解：
10 10
1 1 5 5
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 1 1 1 1 1
0 1 0 0 0 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
16
B 共轭树图
首先的结论，是 \(G\) 图是一棵树。
然后省略证明，然后考虑 dp：
设 \(f(x,i)\) 表示以 \(x\) 为根的子树，且 \(x\) 只允许与它的第 \(i\) 个祖先在 \(G\) 连边时，子树中的方案数。考虑枚举 \(x\) 在 \(G\) 中的父亲具体是哪一个，有转移：
\[f(x,i)=\sum_{j=1}^i \prod f(y,i-(j-1)+1) \]然后在统计时用前缀和优化即可。
C 摸鱼军训
可算是搞懂了。
首先，我们需要确定一个数在 \(k\) 次冒泡排序后的位置，有以下几种可能：
-
第 \(k\) 次排序后前面仍有比他大的数；
-
没有比他大的数
-
他已经不会再移动（前缀已经有序）
首先，有几个比较重要的引理：
若 \(x\) 后方有 \(k\) 个小于它的数，第 \(k+1\) 个数大于它，那么本次移动 \(x\) 和下一个大于 \(x\) 的数中间的数都会移动到 \(x\) 前方。
证明：
我们设小于 \(x\) 的数为 \(p_1,p_2...p_k\)，大于 \(x\) 的数为 \(q_1,q_2,...q_k\)
假设一次排序前的序列为 \(x,p_1,p_2,p_3,q_1,p_4,q_3\)，那么显然，\(x\) 会与 \(p_1\) 交换，然后指针依然在 \(x\) 上，会与 \(p_2\) 交换，直到 \(q_1\) 为止。而接下来 \(p_4\) 会从 \(q_1\) 和 \(q_2\) 中间移动到 \(x\) 和 \(q_1\) 中间，以此类推。
若 \(x\) 前方已无大于它的数，且保证接下来的序列一定会变，那连续 \(k\) 次排序，第 \(i\) 次排序后 \(x\) 应该距离 \(p_i\) 在序列中的原位置有 \(i\) 长度。
证明：
我们已知一次排序后 \(x\) 会处在某个大于它的数的前面，那么根据上面的结论，第 \(i\) 次排序会使 \(q_{i-1}\) 和 \(q_i\) 中间的所有 \(p\) 移动到 \(q_{i-2}\) 和 \(q_{i-1}\) 中间，
此时，我们假设序列中没有 \(<x\) 的数，那排序到 \(k\) 次时确实距离 \(p_k\) 为 \(i\)。
那现在有了 \(<x\) 的数，原序列中且 \(p_k\) 后面的、\(<x\) 的数来到了 \(x\) 的正后方，假设有 \(m\) 个，
也就是原 \(p_k\) 的位置向后推了 \(m\)，设现在 \(x\) 到 \(p_k\) 距离为 \(n\)，那有 \(n=m+k\)
就是每次向后使所有 \(p\) 产生位移的 \(m\) 加上本身距离的 \(k\)，就是现在的距离。
那么 \(x\) 到 \(q_k\) 的原位置不就是 \(n-m\)，那不就是 \(k\) 吗。
情况 \(1\)：
若 \(x\) 前面仍有大于它的数，那距离 \(x\) 最近的、大于 \(x\) 的数一定会移动到 \(x\) 后方。证明可看引理 1。
那么，有 \(i\) 个大于 \(x\) 的数，就一定需要 \(i\) 轮去把它们移动到 \(x\) 后方。并且，每移动一轮，\(x\) 的位置都会 \(-1\)。
因为有一个在它前面的大于它的数到了后面，且只有一个，所以会 \(-1\)。
记原序列中在位置 \(p\) 前方且大于 \(a_p\) 的数的个数为 \(rev_p\)，那么对于所有 \(k\le rev_p\) 的轮，\(a_p\) 的位置一定是 \(p-k\)。
情况 \(2\):
此时，\(x\) 的前方已经没有比它大的数了，那我们根据引理 2，在第 \(k\) 轮，\(x\) 到 \(p_k\) 原位置的距离为 \(k\)，只需要维护所有大于 \(x\) 的数的位置，并且找第 \(k\) 大的，那么本次排序后 \(x\) 的位置就是 \(pos_{p_k}-k\) 了。
情况 \(3\)：
在第 \(i\) 轮，编号为 \(n-i+1\) 的数一定会被移动到最终位置。