2016中国大学生程序设计竞赛 - 网络选拔赛 1007 Mountain hdu5838

Problem Description Zhu found a map which is a  N∗M  rectangular grid.Each cell has a height and there are no two cells which have the same height. But this map is too old to get the clear information,so Zhu only knows cells which are valleys. A cell is called valley only if its height is less than the heights of all its adjacent cells.If two cells share a side or a corner they are called adjacent.And one cell will have eight adjacent cells at most. Now give you  N  strings,and each string will contain  M  characters.Each character will be '.' or uppercase 'X'.The j-th character of the i-th string is 'X' if the j-th cell of the i-th row in the mountain map is a valley, and '.' otherwise.Zhu wants you to calculate the number of distinct mountain maps that match these strings. To make this problem easier,Zhu defines that the heights are integers between  1  and  N∗M .Please output the result modulo  772002 .   Input The input consists of multiple test cases.  Each test case begins with a line containing two non-negative integers  N  and  M . Then  N  lines follow, each contains a string which contains  M  characters.  (1≤N≤5,1≤M≤5) .   Output For each test case, output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module 772002.   Sample Input 2 4 .X.. ...X 4 2 X. .. .. X. 1 2 XX   Sample Output Case #1: 2100 Case #2: 2520 Case #3: 0

CQOI2012原题。听说UESTC的验题人一个都没看出是原题

---------------------------------------------------------------------------------------------------

首先因为n<=5,m<=5，所以X的数量不可能超过9个

然后我们就可以状压了。f[i][S]表示填了前I个数，X的位置状态为S的方案数

S表示填或者没填

转移方程就是

f[i][j]=f[i-1][j]*(cnt[j]-i+1)+sigma(f[i][j]+f[i-1][j^(1<<(k-1))])

其中cnt[j]表示在状态j的时候，可以填的格子数量。

因为我们是从小往大填数的，所以有了上述转移式

题目又要求,的地方一定不能是区域最小值

所以我们要枚举可能成为最小值的位置。然后容斥原理处理一下就可以了

#include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct point { int x,y; }p[10],pp[10]; long long mod=772002; long long f[26][2001],cnt[2001]; int mx[6][6],a[6][6]; bool v[7][7]; int n,m,tot,px; int dx[9]={-1,-1,-1,0,0,1,1,1,0}; int dy[9]={-1,0,1,-1,1,-1,0,1,0}; inline void prepare() { memset(cnt,0,sizeof(cnt)); int i,j,k; for(k=0;k<=(1<<tot)-1;k++) { // if(cnt[k]!=0&&k<=(1<<px)-1&&k!=0) // continue; memset(mx,0,sizeof(mx)); for(i=1;i<=tot;i++) { if(((1<<(i-1))&k)==0) { for(j=0;j<=8;j++) { int x=p[i].x+dx[j],y=p[i].y+dy[j]; if(x>=1&&x<=n&&y>=1&&y<=m) mx[x][y]=1; } } } int sum=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(mx[i][j]==0) sum++; cnt[k]=sum; } } inline long long dfs(int xx,int yy,int s) { if(xx==n+1) { prepare(); memset(f,0,sizeof(f)); f[0][0]=1; int i,j,k; for(i=1;i<=m*n;i++) { for(j=0;j<=(1<<tot)-1;j++) { f[i][j]=f[i-1][j]*(cnt[j]-i+1)%mod; for(k=1;k<=tot;k++) { if((j&(1<<(k-1)))!=0) f[i][j]=(f[i][j]+f[i-1][j^(1<<(k-1))])%mod; } } } if(s%2==1) return -f[n*m][(1<<tot)-1]; else return f[n*m][(1<<tot)-1]; } long long ans=0; if(v[xx][yy]) { int tx=xx,ty=yy; yy++; if(yy>m) { xx++; yy=1; } ans+=dfs(xx,yy,s); } else { bool flag=true; int i; for(i=0;i<=8;i++) { int x=xx+dx[i],y=yy+dy[i]; if(v[x][y]) { flag=false; break; } } int tx=xx,ty=yy; yy++; if(yy>m) { xx++; yy=1; } if(flag) { v[tx][ty]=true; tot++; p[tot].x=tx; p[tot].y=ty; ans=(ans+mod+dfs(xx,yy,s+1))%mod; v[tx][ty]=false; tot--; } ans=(ans+mod+dfs(xx,yy,s))%mod; } return ans; } int main() { int kx=0; while(scanf("%d%d",&n,&m)!=EOF) { memset(cnt,0,sizeof(cnt)); memset(v,0,sizeof(v)); tot=0; px=0; kx++; int i,j,k; string x; for(i=1;i<=n;i++) { cin>>x; for(j=1;j<=m;j++) { if(x[j-1]=='.') a[i][j]=0; else { tot++; a[i][j]=tot; v[i][j]=true; p[tot].x=i; p[tot].y=j; } } } px=tot; bool flag=true; for(i=1;i<=tot;i++) { for(j=0;j<=7;j++) { int x=p[i].x+dx[j],y=p[i].y+dy[j]; if(v[x][y]) { flag=false; break; } } if(!flag) break; } if(flag) printf("Case #%d: %I64d\n",kx,dfs(1,1,0)); else printf("Case #%d: 0\n",kx); } return 0; }