题目

分析

其实原题就是【cqoi2012】【bzoj2669】局部极小值。

有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。

给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。

发现，X的位置最多有8个，那我们考虑状压dp。

我们从小到大把数填进去，用\(f_{i,j}\)表示，把第i个数填进去后，每个X是否被填了数，用二进制数j表示。

预处理出\(rest_j\)表示填充状态为j时共有多少位置是可以填充的(包括已填充的局部极小值位置)

转移：

\[f_{i,j}=f_{i-1,j}*(rest_j-(i-1))+\sum_{k\in{j}}f_{i-1,j-2^{k-1}}
\]

但是有些不是为X的位置有可能也是局部极小值，那么我们用容斥，每次把一下有可能出现局部极小值的地方改为X，当额外增加的X的个数为奇数，ans就减去dp得所得的答案，否则ans加上dp得所得的答案。

其中dp方面这篇论文（第5页到第8页）讲的非常清楚

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=12345678;

const int N=10;

int z[9][2]=

{

{-1,-1},

{-1,0},

{-1,1},

{0,-1},

{0,1},

{1,-1},

{1,0},

{1,1},

{0,0}

};

int a[N][N],T,n,m,ans,f[N*N][2000],mi[10],sign[N][2],tot,rest[2000];

char c[N][N];

bool bz[N][N];

int val()

{

	tot=0;

	int state=0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

		{

			if(c[i][j]=='X')

			{

				state+=mi[tot];

				sign[++tot][0]=i;

				sign[tot][1]=j;

			}

		}

	for(int i=0;i<=state;i++)

	{

		memset(bz,true,sizeof(bz));

		rest[i]=0;

		for(int j=1;j<=tot;j++)

			if((mi[j-1]&i)==0)

			{

				for(int k=0;k<=8;k++)

				{

					bz[sign[j][0]+z[k][0]][sign[j][1]+z[k][1]]=false;

				}

			}

		for(int j=1;j<=n;j++)

			for(int k=1;k<=m;k++)

			{

				if(bz[j][k])

					rest[i]++;

			}

	}

	f[0][0]=1;

	for(int i=1;i<=n*m;i++)

		for(int j=0;j<=state;j++)

		{

			f[i][j]=0;

			(f[i][j]+=f[i-1][j]*(rest[j]-i+1)%mo)%=mo;

			for(int k=1;k<=tot;k++)

			{

				if(mi[k-1]&j)

				{

					(f[i][j]+=f[i-1][j-mi[k-1]])%=mo;

				}

			}

		}

	return f[n*m][mi[tot]-1];

}

int dg(int x,int y,int z1)

{

	if(x>n)

	{

		(ans+=(val()*(z1%2?1:-1))%mo)%mo;

		return 0;

	}

	int xx=x,yy=y+1;

	if(yy>m)

	{

		yy=1;

		xx++;

	}

	dg(xx,yy,z1);

	bool q=true;

	for(int i=0;i<=8;i++)

	{

		if(c[x+z[i][0]][y+z[i][1]]=='X')

		{

			q=false;

			break;

		}

	}

	if(q)

	{

		c[x][y]='X';

		dg(xx,yy,z1+1);

		c[x][y]='.';

	}

}

int main()

{

	mi[0]=1;

	for(int i=1;i<=9;i++)

		mi[i]=mi[i-1]*2;

	scanf("%d",&T);

	while(T--)

	{

		tot=0;

		ans=0;

		memset(c,0,sizeof(c));

		scanf("%d%d",&n,&m);

		for(int i=1;i<=n;i++)

		{

			for(int j=1;j<=m;j++)

			{

				c[i][j]=getchar();

				while(c[i][j]!='X' && c[i][j]!='.')

					c[i][j]=getchar();

				if(c[i][j]=='.')

					tot++;

			}

		}

		if(tot==n*m)

		{

			printf("0\n");

			continue;

		}

		for(int i=1;i<=n && ans!=-1;i++)

		{

			for(int j=1;j<=m;j++)

			{

				bool q=true;

				if(c[i][j]=='X')

				for(int k=0;k<=7;k++)

				{

					if(c[i+z[k][0]][j+z[k][1]]=='X')

					{

						q=false;

						ans=-1;

						break;

					}

				}

				if(!q)

				{

					ans=-1;

					break;

				}

			}

		}

		if(ans==-1)

		{

			printf("0\n");

		}

		if(ans!=-1)

		{

			dg(1,1,1);

			printf("%d\n",(ans%mo+mo)%mo);

		}

	}

}

巴特西

【NOIP2016提高A组模拟8.15】Garden

题目

分析

最新文章

热门文章