题解 P2576 【[ZJOI2005]梦幻折纸】

· · 题解

先考虑最后折成的小正方形，它有n* m层，假设我们把它立起来，并从正面看这个小正方形，它的左右两侧的前后连接即为每一行上一格格的连接，上下两侧的前后连接即为每一列上一格格的连接。

那么只需分别再现出行和列究竟是哪些格子被连起来，再看是否有交点（即重合）即可。

先考虑行

看样例第三组：

2 1 6
3 4 5

我们发现，显然，在矩阵中相邻的一定被连在一起，问题在于最终它们究竟是左侧相连，还是在右侧相连（在之前说的小正方形中）。

不妨设第1行的第1个与第2个是最后在左边相连的。

那么不管你怎么折，第2行的第1个与第2个也总是最后在左边相连的。

类似地，所有行的第1个与第2个都是最后在左边相连。

又发现，不管你怎么折，第1行的第2个与第3个总是最后在右边相连的。于是同上理所有行的2，3号之间最后全在右边相连。

这样可以推出，任意行的i,i+1号最后在i&1这一侧相连（左1右0）

那么，我们就能把所有的链接情况用一个表来记录，然后看会不会有交叉。如样例：

1 1 3 3    //左边
1 2 3 4 5 6
2     4 4 2//右边

数字相同表示连在一起。列与行是一样的。 只上部分代码：(即行的处理)

```cpp
        t=co=0,yes=1;
        FOR(j,1,m-1)FOR(i,1,n) s[j&1][a[i][j]]=s[j&1][a[i][j+1]]=++co;
        FOR(k,0,1){
            FOR(p,1,pro)if(s[k][p]){
                st[++t]=s[k][p];
                if(t>1) if(st[t]==st[t-1]) t-=2;
            }if(t) yes=0;
        }