石头游戏[CH3401]

欢迎大家访问我的老师的OJ———caioj.cn

题面描述

传送门

思路

题目可以理解为是一个$n\ast m$的矩阵，在里面进行一些玄学的操作。

不难发现，操作序列的长度不超过6，那么1~6的最小公倍数是60，

即每经过60秒，所有操作序列都会重新处于最开始的字符处。

那么第$k(1\le k\le 60)$秒，第$k+60$秒执行的字符与第$k$秒一定是相同的。

得到了这个结论，我们就可以很容易想到递推，因为这是单调的。

之后发现递推中都是加法。

之后我们就可以运用矩阵乘法来加速运算。

设状态矩阵为$F$,我们用这样的方法去表示$i$行$j$列的石头数:

$$F[num(i,j)]，num(i,j)=(i-1)\ast m$$

根据题目定义，我们可以得到$F$的初始状态是 [ 0 0 . . . 0 ] \begin{bmatrix}0&0&...&0\end{bmatrix} [0​0​...​0​]

我们不妨多一个源点$p=n\ast m+1$,使$F[p]=1$.

因为矩阵乘法，必须要有一个不为$1$的数，才能正常进行操作，否则操作等于无效

那我们也需要一个转移矩阵$A$来转移状态吧。

对于第$k(1\le k\le 60)$秒，构造一个转移状态 A k A_k Ak​,行，列下标均为$1$~$n\ast m+1$

构造方法类似于跑图:

1. 若网格$(i,j)$第k秒的操作字符为“N”，且$i>1$,则令 A k [ n u m ( i , j ) , n u m ( i − 1 , j ) ] = 1 A_k[num(i,j),num(i-1,j)]=1 Ak​[num(i,j),num(i−1,j)]=1，意思就是把石头推到上边的格子。字符"W",“S”,"E"类似。

2. 若网格$(i,j$)第$k$秒的操作字符时一个数字$x$，则令 A k [ 0 , n u m ( i , j ) ] = x A_k[0,num(i,j)]=x Ak​[0,num(i,j)]=x。

3. 令 A k [ p , p ] = 1 A_k[p,p]=1 Ak​[p,p]=1。

4. A k A_k Ak​的其它部分均赋值为$0$.

上述结构实际上把“状态矩阵”的第$p$列作为“石头来源”, A k [ p , p ] = 1 A_k[p,p]=1 Ak​[p,p]=1保证$F[p]=1$

A k [ p , n u m ( i , j ) ] = x A_k[p,num(i,j)]=x Ak​[p,num(i,j)]=x相当于从“石头来源”获取$x$个石头,放到格子$(i,j)$上。

设 A = ∏ i = 1 60 A i , t = q ( 60 + r ( 0 ≤ r < 60 ) A=\prod\limits_{i=1}^{60}A_i,t=q(60+r(0\le r<60) A=i=1∏60​Ai​,t=q(60+r(0≤r<60).根据上面的讨论:
F t = F 0 ∗ A q ∗ ∏ i = 1 r A i F_t=F_0*A^q*\prod\limits_{i=1}^rA_i Ft​=F0​∗Aq∗i=1∏r​Ai​

用矩阵乘法和快速幂计算该式， F t F_t Ft​第$1$~$n\ast m$列中的最大值即为所求。

另外，对于 A k [ n u m ( i , j ) , n u m ( i − 1 , j ) ] = 1 A_k[num(i,j),num(i-1,j)]=1 Ak​[num(i,j),num(i−1,j)]=1，其实也是另类建边，使石头能够“流过去”。

#include
#include
#include
#include
#include
#define ll long long
#define gc getchar()
using namespace std;
int n,m,t,act,p;
inline int num(int i,int j){return (i-1)*m+j;}
inline void muls(ll a[66][66],ll b[66][66])
{ll w[66][66];memset(w,0,sizeof(w));for(int i=1;i<=p;i++)for(int k=1;k<=p;k++)if(a[i][k])for(int j=1;j<=p;j++)w[i][j]+=a[i][k]*b[k][j];memcpy(a,w,sizeof(w));	
}
inline void mul(ll f[66],ll a[66][66])
{ll w[66];memset(w,0,sizeof(w));for(int j=1;j<=p;j++)/*for(int i=1;i<=p;i++)*/for(int k=1;k<=p;k++)/*for(int j=1;j<=p;j++)*/w[j]+=f[k]*a[k][j];/*w[i]=f[j]*a[j][i]*/memcpy(f,w,sizeof(w));
}
char b[20][20],s[100];
ll f[66],e[66][66][66],d[66][66];int a[20][20],c[20][20];
int main()
{scanf("%d%d%d%d",&n,&m,&t,&act);for(int i=1;i<=n;i++){scanf("%s",s+1);for(int j=1;j<=m;j++)a[i][j]=s[j]-'0'+1;}for(int i=1;i<=act;i++)scanf("%s",b[i]);p=n*m+1;for(int k=1;k<=60;k++){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x=a[i][j],y=c[i][j];if(b[x][y]>='0'&&b[x][y]<='9'){e[k][p][num(i,j)]=b[x][y]-'0';e[k][num(i,j)][num(i,j)]=1;}else if(b[x][y]=='N'&&i>1)e[k][num(i,j)][num(i-1,j)]=1;else if(b[x][y]=='S'&&i<n)e[k][num(i,j)][num(i+1,j)]=1;else if(b[x][y]=='W'&&j>1)e[k][num(i,j)][num(i,j-1)]=1;else if(b[x][y]=='E'&&j<m)e[k][num(i,j)][num(i,j+1)]=1;c[i][j]=(y+1)%strlen(b[x]);}e[k][p][p]=1;}memcpy(d,e[1],sizeof(e[1]));for(int k=2;k<=60;k++)muls(d,e[k]);ll ans=0;f[p]=1;int w=t/60;while(w){if(w&1)mul(f,d);muls(d,d);w>>=1;}w=t%60;for(int i=1;i<=w;i++)mul(f,e[i]);for(int i=1;i<p;i++)ans=max(ans,f[i]);printf("%lld\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！