【BZOJ2973】石头游戏

Description

石头游戏的规则是这样的。

石头游戏在一个n行m列的方格阵上进行。每个格子对应了一个编号在0~9之间的操作序列。

操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。它包括：

数字0~9：拿0~9个石头到该格子。

NWSE：把这个格子内所有的石头推到相邻的格子。

D：拿走这个格子的石头。

石头游戏的问题是：当这个石头游戏进行了t秒之后，所有方格中最多的格子有多少个石头。

注意：所有格子的操作同时执行。

Input

第一行三个整数n, m, t, act。

接下来n行，每行m个字符，表示每个格子对应的操作序列。

最后act行，每行一个字符串，表示从0开始的每个操作序列。

Output

一个整数：游戏进行了t秒之后，所有方格中最多的格子有多少个石头。

Sample Input

1 6 10 3
011112
1E
E
0

Sample Output

3
【样例解释】
这是另一个类似于传送带的结构。左边的设备0间隔地产生石头并向东传送。设备1向右传送，直到设备2。10秒后，总共产生了5个石头，2个在传送带上，3个在最右边。
【数据约定】
0≤n, m≤8。
1≤act≤10。
1≤t≤10^9。

题解：跟沼泽鳄鱼那道题差不多，只不过周期变成了60。那我们构造60个转移矩阵f[0..59]，它们的乘积为x。那么ans=x^(T/12)*f[0..T%12]。至于怎么构造矩阵。。自己yy一下就好了吧？

又一次get了惨痛的历史教训，矩乘不满足交换律，所以一定要先ans*=x^(T/12)再ans*=f[0..T%12]。

#include <cstdio>

#include <cstring>

#include <iostream>

#define P(A,B) ((A-1)*m+B)

using namespace std;

typedef long long ll;

typedef struct matrix

{

	ll v[100][100];

}M;

M ans,x,emp,f[65];

int n,m,tim,act;

int len[20];

ll maxx;

char A[20][20],B[20][20],ch;

M mmul(M a,M b)

{

	M c=emp;

	int i,j,k;

	for(i=0;i<=n*m;i++)

		for(j=0;j<=n*m;j++)

			for(k=0;k<=n*m;k++)

				c.v[i][j]+=a.v[i][k]*b.v[k][j];

	return c;

}

void pm(int y)

{

	while(y)

	{

		if(y&1)	ans=mmul(ans,x);

		x=mmul(x,x),y>>=1;

	}

}

int main()

{

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

	int i,j,k,l,a,b;

	for(i=1;i<=n;i++)	scanf("%s",A[i]);

	for(i=0;i<act;i++)	scanf("%s",B[i]),len[i]=strlen(B[i]);

	for(i=0;i<=n*m;i++)	x.v[i][i]=1;

	ans.v[0][0]=1;

	for(l=0;l<60;l++)

	{

		f[l].v[0][0]=1;

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

		{

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

			{

				k=A[i][j-1]-'0',ch=B[k][l%len[k]];

				if(ch>='0'&&ch<='9')	f[l].v[P(i,j)][P(i,j)]=1,f[l].v[0][P(i,j)]=ch-'0';

				if(ch=='N'&&i>1)	f[l].v[P(i,j)][P(i-1,j)]=1;

				if(ch=='W'&&j>1)	f[l].v[P(i,j)][P(i,j-1)]=1;

				if(ch=='S'&&i<n)	f[l].v[P(i,j)][P(i+1,j)]=1;

				if(ch=='E'&&j<m)	f[l].v[P(i,j)][P(i,j+1)]=1;

			}

		}

		x=mmul(x,f[l]);

	}

	pm(tim/60);

	for(i=0;i<tim%60;i++)	ans=mmul(ans,f[i]);

	for(i=1;i<=n*m;i++)	maxx=max(maxx,ans.v[0][i]);

	printf("%lld",maxx);

	return 0;

}

巴特西

【BZOJ2973】石头游戏矩阵乘法

【BZOJ2973】石头游戏

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

【BZOJ2973】石头游戏 矩阵乘法

【BZOJ2973】石头游戏

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

【BZOJ2973】石头游戏矩阵乘法