bzoj 1814 Fornula 1

Formula 1

题意

在\(n*m\)的矩阵中，有些格子有树，没有树的格子不能到达，找一条回路，吃完所有的树，求有多少种方法。

解法

因为只要一条回路，所以我们必须维护插头的连通性。

具体的可以参照 这位大佬的博客

代码

注意开long long。

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <cstring>

#include <cctype>

#define del(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

template <typename T>

inline void read(T &x) {

	x=0;char c=getchar();T k=1;

	while(!isdigit(c)) {if(c=='-') k=-1;c=getchar();}

	while(isdigit(c)) {x=x*10+c-'0';c=getchar();}x*=k;

}

const int maxn=15;

const int maxhash=100000;

char G[maxn][maxn];

int _hash[maxhash];

ll sta[2][600000],sum[2][600000];

int cur,n,m,en,em;

int tot[2];

int jz[maxn];

void _init() {

	read(n),read(m);

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

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

			cin>>G[i][j];

			if(G[i][j]=='.') en=i,em=j;

		}

	for(int i=1;i<=m;i++) jz[i]=i<<1;

}

void hash_insert(ll s,ll data) {

	int pos=s%maxhash;

	while(_hash[pos]) {

		if(sta[cur][_hash[pos]]==s) {

			sum[cur][_hash[pos]]+=data;

			return;

		}

		if(++pos==maxhash) pos=0;

	}

	++tot[cur];

	_hash[pos]=tot[cur];

	sta[cur][tot[cur]]=s;sum[cur][tot[cur]]=data;

}

ll ans;

void work() {

	tot[0]=1;sum[0][1]=1;

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

		for(int k=1;k<=tot[cur];k++)

			sta[cur][k]=sta[cur][k]<<2;

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

			cur^=1;

			tot[cur]=0;

			del(_hash,0);

			del(sta[cur],0);

			del(sum[cur],0);

			for(int k=1;k<=tot[1-cur];k++) {

				ll s=sta[1-cur][k],data=sum[1-cur][k];

				int x=(s>>jz[j-1])%4;

				int y=(s>>jz[j])%4;

				ll temp;

				if(G[i][j]!='.') {

					if(x==0&&y==0) hash_insert(s,data);

				}

				else {

					if(x==0&&y==0) {

						if(G[i][j+1]=='.'&&G[i+1][j]=='.') {

							temp=s+1*(1<<jz[j-1])+2*(1<<jz[j]);

							hash_insert(temp,data);

						}

						continue;

					}

					if(x==0&&y>0) {

						if(G[i][j+1]=='.')

							hash_insert(s,data);

						if(G[i+1][j]=='.') {

							temp=s-y*(1<<jz[j])+y*(1<<jz[j-1]);

							hash_insert(temp,data);

						}

						continue;

					}

					if(x>0&&y==0) {

						if(G[i+1][j]=='.')

							hash_insert(s,data);

						if(G[i][j+1]=='.') {

							temp=s-x*(1<<jz[j-1])+x*(1<<jz[j]);

							hash_insert(temp,data);

						}

						continue;

					}

					if(x==1&&y==1) {

						int f=1;

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

							int fff=(s>>jz[v])%4;

							if(fff==1) f++;

							if(fff==2) f--;

							if(!f) {

								temp=s-2*(1<<jz[v])+1*(1<<jz[v]);

								break;

							}

						}

						temp=temp-1*(1<<jz[j-1])-1*(1<<jz[j]);

						hash_insert(temp,data);

						continue;

					}

					if(x==2&&y==2) {

						int f=1;

						for(int v=j-2;v>=1;v--) {

							int fff=(s>>jz[v])%4;

							if(fff==1) f--;

							if(fff==2) f++;

							if(!f) {

								temp=s-1*(1<<jz[v])+2*(1<<jz[v]);

								break;

							}

						}

						temp=temp-2*(1<<jz[j-1])-2*(1<<jz[j]);

						hash_insert(temp,data);

						continue;

					}

					if(x==2&&y==1) {

						temp=s-2*(1<<jz[j-1])-1*(1<<jz[j]);

						hash_insert(temp,data);

						continue;

					}

					if(x==1&&y==2) {

						if(i==en&&j==em) {

							ans+=data;

						}

					}

				}

			}

		}

	}

}

int main() {

	_init();

	work();

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 1814 Fornula 1

Formula 1

题意

解法

代码

最新文章

热门文章