题解：P9731 [CEOI2023] Balance
2huk
·
·
题解
MX-WF-C 8.14 最难题。
题意
给定一个 n \times s 的矩阵。保证 s 是 2 的幂。你需要给出一种将矩阵的每一行重排的方案，使得对于每个矩阵中出现的数而言，在所有列中的出现次数的极差 \le 1。
做法
首先考虑 s = 2。不妨设这个矩阵形如 [[u_1,v_1],[u_2,v_2]\dots[u_n,v_n]]。
我们考虑将每个 u_i, v_i 连无向边。我们断言，答案为给所有边定向，使得每个点的入度与出度的差的绝对值都 \le 1 的方案数。
我们考虑一组答案与上述构造的映射关系。对于一条边而言，如果形如 u_i \to v_i，则将这一行的两个数交换（即 [v_i, u_i]）。否则如果 u_i \gets v_i，则这一行保持不变（即 [u_i,v_i]）。那么一个数被放在左边的行数即这个点的入度，右边的行数即出度。所以我们需要保证任意一个点的入度与出度的差的绝对值都 \le 1。
对于新问题，不难想到欧拉路的一系列东西。
若图中任意一点的度数均为偶数，那么我们对于每个连通块都求一遍欧拉回路。可以证明这样的情况下欧拉回路一定存在。那么我们可以根据这条欧拉回路轻易的构造出边的定向方案，且每个点的出度均等于入度。
若图中存在若干个点的度数为奇数。我们建一个 super 点与这些度数为奇数的点连边。可以证明度数为奇数的点的数量一定为偶数（因为所有点的度数和是边数的两倍，是个偶数，所以去除掉所有度数为偶数的点后，剩下的度数为奇数点的度数和也是偶数），即这个 super 点的度数为偶数。
所以这张新图就满足了上一种情况（即所有点的度数均为偶数）。跑一边欧拉回路，再将 super 点去掉即答案。这是因为原来的所有度数为奇数的点，在新图中满足了入度等于出度，所以去掉它的一个度之后，入度出度差至多为 1。
至此我们解决了 s = 2 的情况。考虑更一般的问题。
分而治之好！设 s = 2^k。我们考虑将矩阵的每一行变形：
a_{i,1}&a_{i,2}&\cdots&a_{i,2^{k-1}}&a_{i,2^{k-1} +1 }&\cdots&a_{i,2^k}
\end{bmatrix}
\longrightarrow
\begin{bmatrix}
a_{i,1} & a_{i,2^{k-1}+1} \\
a_{i,2} & a_{i,2^{k-1}+2} \\
\vdots & \vdots \\
a_{i,2^{k-1}} & a_{i,2^k}
\end{bmatrix}
然后对于这个新矩阵执行上面的算法。换言之我们连边所有 a_{i,j}, a_{i,j+2^{k-1}} 然后跑欧拉回路。
发现这样做我们能保证每个数字在 a_{1\sim n,1 \sim 2^{k-1}} 中的出现次数与在 a_{1\sim n, 2^{k-1}+1\sim 2^k} 中的出现次数相差至多 1。然后递归处理 [1,2^{k-1}] 和 [2^{k-1}+1, 2^k] 即可。