信息学国家集训队作业0072-superturn

1、题目 0072 Superturn（超级翻转）题目来源：New者：一、英文原文二、中文翻译超级翻转有一个 N*N 的网格，每一“格”上有一个可以翻转的方块，方块的两面分别黑、白两种颜色。另外，有一个沿着网格线活动的东西不妨称之为“动子”。初始时，每个方块随机地被翻成黑或白色，“动子”停在网格线的某个顶点上。例如如图一就是一个 4*4的网格的一种可能的开局情况。动子在网格线上运动时，从一个顶点 A 到相邻的另一个顶点 B 之后，以网格线 AB 为边的两个或一个网格上的方块就会翻转白变黑，黑变白。例如图一的“动子”向右移动一步之后变成图二，向下移动一步之后变成图三。问题是：给定一个初始状态和一个目

2、标状态，求“动子”的一种运动轨迹，可以把初始状态翻转成目标状态，最后“动子”停在哪里是无所谓的。三、初步情况搜索吧。求可行解怎么使用解模方程组的方法，我只尝试用搜索解决，在小数据的情况应该没有问题，但是璟求可行解时怎么用解方程组的方法解决呢？没想到有效算法，不过也以通过解方程来进行初始化。可行解似乎可以通过解方程+构造但最优解不会虽然可以用设未知数解方程的方式，求出每一条边应经过次数的奇偶性。但是要使这些连续，有得是最少，确实不容易。目前的想法：可以先考虑解方程，若方程无解，则问题无解，也可能有多组解，检验一组解的方法：如果度为奇数的点的个数小于等于 2 且为 2 时起点的度为奇数，则该组解能

3、构成路径。于是分度为奇数的点的个数为 0 和 2 的情况：为 0 时，加上一些方程；为 2 时只要枚举终点，并令此点度数为奇数，解方程即可。最优解算法正在研究之中。最优解没什么办法。可行解倒是可以。给每条边设一个未知数，取 0 或者 1，表示经过或者不经过。枚举终点和起点。然后列一些同余方程：1、 可以确定每个格子周围 4 条边的和的奇偶性。2、 除起点和终点外每个点相连的 4 条边（或 3 条边）的和为偶数。3、 起点终点相连的 4 条边（或 3 条边）的和为奇数。即可。看似正确的做法：枚举终点（假设它和起点不同），对于每条（有向的）边 i，设它的经过次数为 Xi，这样就需要满足每个顶点出去

4、的边和进入的边总数相等，特例是起点出度比入度大一，终点入度比出度大一。这样可以列出方程，就可以把方案解出来。但是实际上这样没有办法保证这个图是连通的。不知怎样改进？如果终点和起点相同，也有类似的麻烦。可以先通过解模线性方程组求得“动子”经过每条网格边次数的奇偶性，而后通过 bfs求出最短路径。但 bfs 的效率到底如何好像很难确定。解模线性方程组，每条边是一个未知数，对于每个格子可以列出一个方程，而且还有隐含的条件，就是题目要求移动出一条路来，这样的话，与每个点（除顶点和终点外）相连的被选的边只能是偶数条，而起点终点则必须是奇数条，只是所选的边可以形成一条路的必要充分条件，那这样就可以对每个点

5、都可列出一个方程了。解出模线性方程组就可以找到一组可行解了，但是最优解好像要枚举所有的解。此题的时间复杂度为 O(B4)，（B 为边数）但多数情况下达不到。能够用如下算法构造出可行解，但并不知如何求最优解。解奇偶方程组：1.已知了起点，枚举一个终点；2.设每条边经过的次数依次为 ai（一共有 2N(N+1)条边），则可以根据点的度数（除了起点、终点的任意点 i, i 的度数为偶数）列出 (N+1)22 个奇偶方程（若干未知数之和的为奇或为偶的方程）根据每个格子的初状态和末状态类似的列出 N 2（初末状态相同则相邻 4 边之和为偶，否则为奇），一共有 2N 2+2N 个未知数，2N 2+2N1

6、个方程，求出这个方程的任意一组解就可相应的构造出案（构造方法极其简单，这里不再罗嗦，但有一点值得注意的是：求方程组时可设所有的未知数都等于 0 或 1）。我连构造可行解的方法都不会。听说能用解模线性方程组做，是不是这样的：假设一个单元格 I，如果它的颜色原来都是黑的，则 Ci=1；否则为 Ci=0。单元格的上、下、左、右 4 边经过的次数分别为 x1,x2,x3,x4。则可以得到以下这个方程：x1 + x2 + x3 + x4 abs(Ci-Ci)。对于其他的方格，还可以列出同样的方程。因此就了一个模线性方程组。但我觉得这个方法是有问题的，就是说，可能求出了一组符合条件的 x，但是根据这些x 却无法得到一个符合条件的解。假如用模线性方程组解出了这样的解，该如何产生可行解呢？如图 0072-1，红线为解模线性方程组解出的需要经过的路径。图 72-1以每条边被经过的次数为未知数构造方程组。解模方程组，若方程组无解则问题无解；否则验证一组解，转化为路径判定问题。考虑度数为奇数的点的个数。要