题解 P5023 【填数游戏】

这里提供一种非常快的暴力打表算法 **2s打出(8,9)** 怎么做到的呢？首先我的思路受了楼上某位大佬的启发，他的题解里说了如下两条规律： 一个棋盘是合法的，当且仅当 1. 对于每一条自左下到右上的对角线，填数是非严格单调递减的。 1. 如果(i-1,j)和(i,j-1)的填数相同，那么以(i,j)为左上角、以(n,m)为右下角的子矩阵内所有对角线内的填数各自相等。 （以上引自那位大佬的题解） 第一点是再显然不过了，但是第二点怎么证明呢？  如图，对于从（1,1）出发的两条路线，第一条（粉色）第一步是向右，而第二条（黄色）第一步是向下，所以$w(P_1)>w(P_2)$，因此必须满足$s(P_1)≤s(P_2)$，但是因为（1,2）与（2,1）格子上的数字相同，而以（2，2）为左上角的矩阵中存在一条对角线中的数字不相同，那么同时走到（3,3）时的两条路线，第一条往下，得到数字1，而第二条往右，得到数字0，此时$s(P_1)$就会大于$s(P_2)$，不符题意，所以图中棕色框起的矩阵中的每一条对角线中的所有数字必须相同。 由此，可以得出一个O(2^(nm)×nm)的算法，即先暴搜出一种填法，然后设$a[i][j]$表示在第j列中，从第i行到第n行上的所有数字状压得到的结果（其中最高位表示第i行数字，最低位表示第n行数字），设$b[i][j]$表示当前棋盘以$(i,j)$为左上角的矩阵中是否每一条对角线上的数字都相同，于是有 $b[i][j]=b[i][j+1]$&&$(a[i][j+1]>>1)==a[i+1][j]$ 然后再扫描一遍整个棋盘，检查上述第2点即可。 但是这样还是太慢了，于是我们可以在填数的时候就处理出a和b，然后每填一个数就判断一下与这个格子有关的b的值，如果不符合就直接返回，这样不仅省去了填完棋盘后的$O(nm)$的判断，还给搜索提供了很有效的减枝，于是就能在2s内跑出（8,9）的答案啦！这个暴力算法交到洛谷上，可以过35分的数据点（即$n≤8,m≤8$的数据点），可以说效率十分之高。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define N 13 #define M 13 int g[N][M],a[N][M],ans,n,m; bool b[N][M]; bool check(int x,int y) { a[x][y]=a[x+1][y]|(g[x][y]<<(n-x)); if(y==m) b[x][y]=true; else b[x][y]=b[x][y+1]&&(a[x][y+1]>>1)==a[x+1][y]; if(x<n&&y>1&&g[x][y]==g[x+1][y-1]&&!b[x+1][y])return false; return true; } void dfs(int x,int y) { if(y<1)return dfs(x-1,m); if(x<1) { ans++; return; } if(x==n||y==1||g[x+1][y-1]==1) { g[x][y]=1; if(check(x,y))dfs(x,y-1); } g[x][y]=0; if(check(x,y))dfs(x,y-1); } int main() { scanf("%d%d",&n,&m); dfs(n,m); printf("%d",ans); return 0; } ```