LargeDumpling

我只负责打字,内容我也不知道从何而来。

LYDSY 3690 棋盘

传送门

        可以看出来是解一个异或方程组嘛。我们将每个位置摁或者不摁设为变量,将这些位置之间的关系作为方程,然后打个标准的高斯消元就能拿到暴力分了,暴力代码就没必要放上来了吧。

AC代码

        这道题想要AC还是需要一点技巧,我们发现这道题中的方程太多了,完全没有必要列出来。先放个图


        我们设每个格子与和它有关系的格子之间的关系为上图。若我们能确定0、1、2、3、4、5、7、8号位的摁与不摁的状态,6号位的状态就能唯一确定。所以我们从上到下,从左到右,对一每一个格子我们找到它左边一列,上边两行的格子(就是以这个格子为0号位的话,它2号位的格子)并称之为该格子的P格子,以它为0号位(此时该0号位对应的0、1、2、3、4、5、7、8号位的状态已经确定),来确定这个6号位(也就是我们最开始枚举的那个格子)的状态。

        由于以某些格子是没有P格子的,如下图



        上图灰色部分的格子是没有P格子的,所以它的状态没法通过上面的那种方法来确定,那我们就设它的状态为变量好了。

        我们这样推推推,就能把整张图的状态都用这两行一列内的变量表示出来。可以知道,我们每确定一个格子的状态,实际上就用掉了它P格子对应的方程。

        有一些格子的方程是没有被用掉的,如下图


        上图灰色部分的格子的方程没有被用掉,因为它们不是任何格子的P格子,那我们就把这些格子的方程拿出来,高斯消元一下,方程数和变量数都是相等的两行一列,都是是O(n)级别的,高斯消元之后自由元对应的格子表示这些格子摁或者不摁都是有解的。设自由元数量为k,那么答案就是2的k次方。

        完结,撒花~

后话

        老师讲这道题的时候,我曾问过“为什么我们应该想到这么做?”

        老师告诉我,这道题怎么想到这么做,完全是因为做过类似的题才能想到,要是没有做过类似的题,他也想不到。

        我曾得到过很多次这样的回答,但总觉得不满意。我认为这些题,或者说是更多的题,如果做出来了,应该是可以讲出自己从零思路到想出这个题的整个思路历程的,如果只是通过题海训练让自己见更多的题才能做出题目的话,是很失败的啊...

        我就是很失败啊,大部分没见过的题完全不会做啊。

评论
热度 ( 3 )

© LargeDumpling | Powered by LOFTER