• 牛题:超级翻转,遗憾的是没找到judge online的地方。
  • 出处:IOI2003国家集训队原创题目,连接地址[直接贴题]

题目5(0072):超级翻转
推荐者:许智磊

有一个N*N的网格,每一“格”上有一个可以翻转的方块,方块的两面分别涂成黑、白两种颜色。另外,有一个沿着网格线活动的东西——不妨称之为“动子”。初始时,每个方块随机地被翻成黑或白色,“动子”停在网格线的某个顶点上。例如图一就是一个4*4的网格的一种可能的开局情况。

“动子”在网格线上运动时,从一个顶点A到相邻的另一个顶点B之后,以网格线AB为边的两个或一个网格上的方块就会翻转——白变黑,黑变白。例如图一的“动子”向右移动一步之后变成图二,向下移动一步之后变成图三。

 
问题是:给定一个初始状态和一个目标状态,求“动子”的一种运动轨迹,可以把初始状态翻转成目标状态,最后“动子”停在哪里是无所谓的。

知识点:模线型方程组,UFS[DFS连通块],欧拉路

只看这三个知识点,就晓得要好好研究下了! 

1。理论证明:

  • 一个格子的初末状态不同,那么其四周的边必然被经过了2k+1次,否则为2k次。[充要]
  • 对于任何一个“动子”中间位置V[V!=Start,End],或者初末一致[S=T],其四周的相邻边必然被经过了2k次;若是初末不同[S!=T]状态,则被经过了2k+1次。[充要,可以反证]

2。求解:[黑书上说的很清楚]

  • Xi[i=1,2n+1]偶数则为0,奇数则为1。
  • 利用格子顶点分别建立模线形方程组,求出其解,无解则不存在通路。
  • 合并连通块,如下图所示。多个连通块则要进行添边合并,这个比较简单,加2即可。

  • 求出一条从S到T的欧拉路。

说起清楚,编码却并不轻松。

3。编码准备工作

  • 棋盘类问题,首先是要解决坐标映射问题,这道题目里面存在三个对象:格子以及顶点。研究了下,做了一个简单的映射函数,关系如下图所示:

  • 随后的问题就是模线型方程组的建立,这块不是很熟悉,转化下![暂时放下,感觉应该有现成的方法]
  • 合并连通块,这个可以用UFS来实现,不用多想2N(N+1)
  • 从S到T的欧拉路,这个让我有点犯难,怎么做呢?最好不建立显式的图结构,用传统的图结构还要转化,根据图的特点,我们可以把Edge[x]作为其默认的边,向四个方向查找即可。
  • 好了,这点补在最后,问题还在于是否能解出有解的方程就一定能有连通路呢?实际上是一定存在的,为什么呢?想想我们怎么设定模方程的,对于途中的点V,所有相邻边经过为偶数[0],这个条件等价于对于途中的任意结点其出度等于入度,这正是欧拉路的充要条件,因此只要模方程组有解,欧拉路是存在且不一定唯一的。[这点我对IOI2003大牛们的分析深有同感,所以这道题目是可行解易求,思路清晰,但最优解不容易。这相当于要回溯所有的欧拉路,然后再比较其步长。]

4。编码的最后方案

  • 棋盘转化方案上面已经有了,就不多说了
  • 解多元一次模线型方程组的方法,网上有很多论文都看不成,那只有用最笨的办法,CSP作搜索了,但由于是2^(2n(n+1)),n=4时,规模是2^40!唉!数学不好就只能这样做了!
  • 剩下的没啥说的,连通查找和欧拉路!

Advertisements