信息学国家集训队作业0072-superturn_第1页
信息学国家集训队作业0072-superturn_第2页
信息学国家集训队作业0072-superturn_第3页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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以每条边被经过的次数为未知数构造方程组。解模方程组,若方程组无解则问题无解;否则验证一组解,转化为路径判定问题。考虑度数为奇数的点的个数。要

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论