【BZOJ2669】【JZOJ4700】Garden

Description

有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。 给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。 原题

Data Constraint

Solution

对于20%的数据直接暴力即可。

对于另30%的数据，可以发现局部极小值最多只有8个，可以用状压dp。

对于一个合法的数填写方案，其中的数放置的顺序对其是没有影响的，所以我们把数从小到大填进去。我们用 Fi,S 表示当前填到第 i 个数，“X”被填的状态是S。那么有以下两种情况。

如果我们填的是一个非“X”的格子，我们记没有被填的“X”和它周围的格子的个数是tot，那么这tot个格子都不能填（因为我们填入的是一个非“X”的格子，而且格子周围的数要比格子大，那么我们从小到大填的话必须先填“X”）。那么能填入的位置就有 nm−tot−i+1 个。我们预处理出一个数组 RestS 记录 S 这个状态的nm−tot。

如果我们填的是“X”的格子呢？那么我们可以从没有填这个“X”的状态转移过来。

于是转移方程就可以得出：

Fi,S=Fi−1,S(RestS−i+1)+∑j∈SFi−1,S−j

那么就可以过30%的数据了。

对于100%的数据，如果直接用上面的转移，那么一些被“.”包围的“.”被填入的数小于周围的数的方案数会被统计进答案，所以我们需要用 dfs 找出所有被“.”包围的“.”，然后强制把这个位置改成“X”，计算方案数，然后再容斥一下即可。

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define N 11 #define ll long long #define M 1100 #define mo 12345678 using namespace std; int n,m; char ss[N]; int map[N][N]; int rest[M]; int p=0; ll f[N*N][M]; int fx[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; struct node{ int x,y; }b[N],z[M]; bool bz[N][N]; int cnt; ll find() { p=0; fo(i,1,n) fo(j,1,m) if(map[i][j]) { p++; b[p].x=i; b[p].y=j; } fo(s,0,(1<<p)-1) { memset(bz,0,sizeof(bz)); fo(i,1,p) if(!((1<<i-1)&s)) { bz[b[i].x][b[i].y]=true; fo(j,0,7) { int x=b[i].x+fx[j][0],y=b[i].y+fx[j][1]; if(x<1 || x>n || y<1 || y>m) continue; bz[x][y]=true; } } int tot=0; fo(i,1,n) fo(j,1,m) if(bz[i][j]) tot++; rest[s]=n*m-tot; } memset(f,0,sizeof(f)); f[0][0]=1; fo(i,1,n*m) fo(s,0,(1<<p)-1) { f[i][s]=f[i-1][s]*(rest[s]-i+1)%mo; fo(j,1,p) if(s&(1<<j-1)) f[i][s]=(f[i][s]+f[i-1][s-(1<<j-1)])%mo; } return f[n*m][(1<<p)-1]%mo; } ll ans=0; void dfs(int dep,int t) { if(dep>cnt) { ll tmp=find(); if(t%2) ans=(ans-tmp+mo)%mo; else ans=(ans+tmp)%mo; return; } dfs(cnt+1,t); fo(k,dep,cnt) { bool tf=true; fo(i,0,7) { int x=z[k].x+fx[i][0],y=z[k].y+fx[i][1]; if(x<1 || x>n || y<1 || y>m) continue; if(map[x][y]) { tf=false; break; } } if(tf) { map[z[k].x][z[k].y]=1; dfs(k+1,t+1); map[z[k].x][z[k].y]=0; } } } bool check() { bool tf=true; int X=0; fo(i,1,n) { fo(j,1,m) if(map[i][j]) { X++; fo(k,0,7) { int x=i+fx[k][0],y=j+fx[k][1]; if(x<1 || x>n || y<1 || y>m) continue; if(map[x][y]) { tf=false; break; } } if(!tf) break; } if(!tf) break; } if(!X) tf=false; return tf; } int main() { int T; cin>>T; while(T--) { scanf("%d %d",&n,&m); p=0; fo(i,1,n) { scanf("%s",ss+1); fo(j,1,m) map[i][j]=(ss[j]=='X'); } if(!check()) { printf("0\n"); continue; } cnt=0; fo(i,1,n) fo(j,1,m) if(!map[i][j]) { bool tf=true; fo(k,0,7) { int x=i+fx[k][0],y=j+fx[k][1]; if(x<1 || x>n || y<1 || y>m) continue; if(map[x][y]) { tf=false; break; } } if(tf) { cnt++; z[cnt].x=i; z[cnt].y=j; } } ans=0; dfs(1,0); printf("%lld\n",ans); } }

---

参考资料

http://wenku.baidu.com/view/f11077fc770bf78a6529543e.html