CTS2023 D1T1 最裂解

· · 个人记录

坐牢题。真的坐牢题。没做过不建议点进来。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

观察到构造 n 个排列 p_1,p_2,\cdots.p_n，满足条件：

记 \Huge b_{i,j}=\color{red}a_{j,p_{\small j,i}}，b 每行都是一个排列。

说人话是：n 轮，每轮在每行选一个没有选过的位置删掉，并且选择的位置上的数构成排列。

首先证明存在这样的 p。相当于每次跑一个二分图最大匹配，证明匹配大小一定是 n。

证明考虑 Hall 定理：在删除了 n-x 轮之后，左右边每个点的度数都是 x，对于一个大小 d 的点集连出 xd 条边，那么右边连着的点的数量也一定 \ge d。

然后怎么做呢？对于每个点对 (i,j) 满足 i<j 直接执行 \Huge swap(a_{i,p_{i,j}},\color{red}a_{j,p_{j,i}}\color{black})！

正确性：每个点确实交换不超过一次；交换结束之后第 i 行就是上面限制里的那个排列。这就做完了！！！