专栏文章

题解：P10456 The Pilots Brothers' refrigerator

SSunnysky0
P10456题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipq28io
此快照首次捕获于
2025/12/03 16:05
3 个月前
此快照最后确认于
2025/12/03 16:05
3 个月前
查看原文

一种多项式时间算法

由于每个手柄有且只有 2 种状态，所以可以用二进制 0 和 1 来表示，因此可以将翻转问题建模为异或方程组（或者 GF(2)GF(2) 上的线性方程组）。

异或方程组的构建

对于 4×4 矩阵的 16 个位置，我们定义 16 个变量 xi,jx_{i,j}:
  • xi,j=1x_{i,j} = 1 : 表示翻转位置 [i,j][i,j] 。
  • xi,j=0x_{i,j} = 0 ：表示不翻转位置 [i,j][i,j] 。
对于输入的矩阵，将符号 ++ 定义为 1（表示需要翻转为 −- ），符号 −- 定义为 0（已经是目标状态）。初始矩阵的状态用 0 和 1 表示，例如：
CPP
+--+    1 0 0 1
-++- -> 0 1 1 0
+++-    1 1 1 0
-+++    0 1 1 1
最终目标是使所有位置的最终状态变为 0。
现在考虑翻转操作的影响，显然，对于原矩阵中的每个状态，翻转两次相当于不翻转。翻转位置 [i,j] 会影响：
  • 第 ii 行的所有位置：[i,0][i, 0], [i,1][i, 1], [i,2][i, 2], [i,3][i, 3]。
  • 第 jj 列的所有位置：[0,j][0, j], [1,j][1, j], [2,j][2, j], [3,j][3, j]。
因此，我们可以将位置[p,q][p, q]上的最终状态表示为初始状态加上翻转次数的异或：

  • sp,q=ap,q⊕(⨁j=03xp,j)⊕(⨁i=03xi,q)s_{p,q} = a_{p,q} \oplus(\bigoplus^3_{j=0}x_{p,j})\oplus(\bigoplus^3_{i=0}x_{i,q})

因为目标是所有位置变为“-”（即 0），所以：

  • ap,q⊕(⨁j=03xp,j)⊕(⨁i=03xi,q)=0a_{p,q} \oplus(\bigoplus^3_{j=0}x_{p,j})\oplus(\bigoplus^3_{i=0}x_{i,q}) = 0

  • (⨁j=03xp,j)⊕(⨁i=03xi,q)=ap,q(\bigoplus^3_{j=0}x_{p,j})\oplus(\bigoplus^3_{i=0}x_{i,q}) = a_{p,q}

这就是位置 [p,q][p, q] 上的方程。
接下来就可以写出整个方程组的矩阵表示。总共有 16 个位置，因此需要 16 个方程，并且每个方程涉及 16 个变量 xi,jx_{i, j} 。
为方便处理，将 4×4 矩阵元素的坐标 [i,j][i, j] 映射为 0 到 15 的编号：
idx(i,j)=i×4+jidx(i,j)=i×4+j
对于每个位置 [i,j][i, j]:
  • 第 ii 行的变量 xi,0,xi,1,xi,2,xi,3x_{i,0},x_{i, 1}, x_{i, 2}, x_{i, 3} 的系数为 11
  • 第 jj 列的 x0,j,x1,j,x2,j,x3,jx_{0, j}, x_{1, j}, x_{2, j}, x_{3, j} 的系数为 11
  • 常数项：ai,ja_{i, j}
最终得到一个 16×17 的增广矩阵，如：
CPP
位置  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 常数
[0,0] 1 1 1 1 1 0 0 0 1 0  0  0  1  0  0  0 | 1
[0,1] 1 1 1 1 0 1 0 0 0 1  0  0  0  1  0  0 | 0
[0,2] 1 1 1 1 0 0 1 0 0 0  1  0  0  0  1  0 | 0
[0,3] 1 1 1 1 0 0 0 1 0 0  0  1  0  0  0  1 | 1
...
表示为 AX=BAX = B ，其中 AA 为系数矩阵， XX 为未知数列向量，BB 为常数项列向量
使用高斯消元法（在模 2 运算下）求解此矩阵方程即可。

有解性及唯一性证明

先考虑齐次方程 AX=0AX=0 ，显然 X=0X=0 是解。接下来讨论非平凡解是否存在。
显然， X=[1...1]X=\left[\begin{matrix} 1 \\ ... \\ 1\end{matrix}\right] 不是解， 于是设某个 xi,j=1x_{i, j} = 1 ，那么对于 xi,k=0x_{i, k} = 0 且 k≠jk \not=j， 位置 [i,k][i, k] 上的方程为 1⊕0=01\oplus0=0 ，无解。于是对于第 jj 列的所有 xp,jx_{p, j} ，都有 xp,j=1x_{p, j}=1。 同理，对于第 ii 列的所有 xi,qx_{i, q} ，都有 xi,q=1x_{i, q}=1 。重复这个过程，必然得到 X=[1...1]⊕[1...1]=[0...0]X=\left[\begin{matrix} 1 \\ ... \\ 1\end{matrix}\right] \oplus \left[\begin{matrix} 1 \\ ... \\ 1\end{matrix}\right] = \left[\begin{matrix} 0 \\ ... \\ 0\end{matrix}\right]，于是 X=0X=0 是唯一解。

由此可知，AX=BAX=B 有唯一解。

注意：这里“唯一”指的是翻转位置的集合唯一，而非翻转的顺序（顺序不影响异或结果）。

得到最简步骤

现在我们得到了一个解，但是这个解一定对应着最少翻转次数吗？由于方程组有唯一解，任何其他翻转组合要么无法实现目标，要么与此解相同。从而可知解中的每个操作都是必要的，去掉任何一个都会导致失败。

最优性证明

  • 假设存在一个更小的操作集合 SS，其翻转次数少于解向量中 1 的数量, 设 XSX_S 为 SS 对应的向量。
  • 若 AXS=BA X_S = B , 则得到 XS=XX_S = X ，与 SS 中翻转次数少于解向量 XX 中 1 的数量矛盾。
  • 反之，则得到AXS≠BA X_S \not= B，与 SS 是解矛盾。
于是解向量 XX 便对应唯一的最优翻转操作步骤。 从 XX 得到翻转操作是简单的。令 xi=1x_i = 1 是 XX 的第 ii 个元素，由于使用映射 idx(i,j)=i×4+jidx(i,j)=i×4+j 将 [i,j][i, j] 映射到整数，只需求出其反函数 arcidx(x)=[x/4, xmod  4]arcidx(x)=[x/4,\ x\mod 4] 即可知道翻转 xix_i 对应的行和列。

复杂度 O(N6)=O(4096)O(N^6)=O(4096) 远优于二进制状态枚举

附上高斯消元代码

CPP
int mat[M][M + 1];
vector<int> row_reduction() {
    vector<int> solution(M, 0);
    for(int col = 0; col < M; col++) {
        int pivot = -1;
        for(int row = col; row < M; row++) {
            if(mat[row][col] == 1) {
                pivot = row;
                break;
            }
        }
        if(pivot == -1) continue;
        if(pivot != col)
            for(int j = col; j <= M; j++)
                swap(mat[col][j], mat[pivot][j]);
        for(int row = 0; row < M; row++) {
            if(row != col && mat[row][col] == 1)
                for(int j = col; j <= M; j++)
                    mat[row][j] ^= mat[col][j];
        }
    }
    for(int row = M - 1; row >= 0; row--) {
        int leading = -1;
        for(int col = 0; col < M; col++) {
            if(mat[row][col] == 1) {
                leading = col;
                break;
            }
        }
        if(leading == -1) continue;
        solution[leading] = mat[row][M];
        for(int col = leading + 1; col < M; col++)
            if(mat[row][col] == 1)
                solution[leading] ^= solution[col];
    }
    return solution;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...