专栏文章

题解：P10498 石头游戏

JJHR100330
P10498题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipb2kjm
此快照首次捕获于
2025/12/03 09:05
3 个月前
此快照最后确认于
2025/12/03 09:05
3 个月前
查看原文

题目大意

根据题目模拟操作，输出 tt 秒后石头最多的格子里有多少个石头。

分析

首先，1≤t≤1081 \le t \le 10^8，暴力枚举必然超时，我们发现，操作序列的长度极短，仅有 11 至 66，所以每 6060 秒为一个周期，所有操作序列均会回到第一个操作，然后循环，故考虑矩阵快速幂加速递推。
先要考虑如何构建矩阵。

一、考虑放置操作

我们先将其简化一下：只考虑网格是一维，且每个格子上的操作也只有一种的情况。
假设我们输入的数据为：
CPP
1 3 2 3
012
0
1
2
根据题目，我们可以知道，每秒钟我们在第一个格子上放 00 个石头，在第二个格子上放 11 个石头，在第二个格子上放 22 个石头。
然后让我们思考一下如何创建状态矩阵，三个时刻每一格石头的个数即为 0 0 0，0 1 2，0 2 4。
我们发现每一秒某个格子上增加的石头数量都是一样的。
我们将这三个网格上的石头的数量设为 a1,a2,a3a_1,a_2,a_3，代表第 00 秒时的状态（转移前的状态），a1′,a2′,a3′a_1',a_2',a_3' 表示第 11 秒时的状态(转移后的状态)。
通过分析我们可以列出下列表达式：
a1′=1×a1+0a2′=1×a2+1a3′=1×a3+2a_1' = 1 \times a_1 + 0 \\ a_2' = 1 \times a_2 + 1 \\ a_3' = 1 \times a_3 + 2
变换一下：
a1′=1×a1+0×a2+0×a3+0a2′=0×a1+1×a2+0×a3+1a3′=0×a1+0×a2+1×a3+2a_1' = 1 \times a_1 + 0 \times a_2 + 0 \times a_3 + 0 \\ a_2' = 0 \times a_1 + 1 \times a_2 + 0 \times a_3 + 1 \\ a_3' = 0 \times a_1 + 0 \times a_2 + 1 \times a_3 + 2
但是还要解决一个问题，那就是结尾加上去的 0,1,20,1,2。
我们知道结尾加上的数是不会随着时间的变化而变化的，所以我们设 a0=1a_0 = 1，则：
a0=a00=0×a01=1×a02=2×a0a_0 = a_0 \\ 0 = 0 \times a_0 \\ 1 = 1 \times a_0 \\ 2 = 2 \times a_0
将其与上面的式子结合我们就可以得到：
a0′=1×a1+0×a1+0×a2+0×a3a1′=0×a1+1×a1+0×a2+0×a3a2′=1×a1+0×a1+1×a2+0×a3a3′=2×a1+0×a1+0×a2+1×a3a_0' = 1 \times a_1 + 0 \times a_1 + 0 \times a_2 + 0 \times a_3 \\ a_1' = 0 \times a_1 + 1 \times a_1 + 0 \times a_2 + 0 \times a_3 \\ a_2' = 1 \times a_1 + 0 \times a_1 + 1 \times a_2 + 0 \times a_3 \\ a_3' = 2 \times a_1 + 0 \times a_1 + 0 \times a_2 + 1 \times a_3
（a0′a_0' 为 a0a_0 转移后的值）
这样我们就得到了状态矩阵：
[1000]\begin{bmatrix} 1 & 0 & 0 & 0 \end{bmatrix}
和转移矩阵：
[1012010000100001]\begin{bmatrix} 1 & 0 & 1 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}

二、考虑移动操作

若当前状态矩阵为：
[a0a1a2a3]=[1234] \begin{bmatrix} a_0 & a_1 & a_2 & a_3 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 & 4 \end{bmatrix}
变化一下：
a0′=1×a1+0×a1+0×a2+0×a3a1′=0×a1+0×a1+0×a2+0×a3a2′=0×a1+1×a1+1×a2+0×a3a3′=0×a1+0×a1+0×a2+1×a3a_0' = 1 \times a_1 + 0 \times a_1 + 0 \times a_2 + 0 \times a_3 \\ a_1' = 0 \times a_1 + 0 \times a_1 + 0 \times a_2 + 0 \times a_3 \\ a_2' = 0 \times a_1 + 1 \times a_1 + 1 \times a_2 + 0 \times a_3 \\ a_3' = 0 \times a_1 + 0 \times a_1 + 0 \times a_2 + 1 \times a_3
所以转移矩阵为：
[1000001000100001]\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}
矩阵的构建就实现完了。

三、考虑代码实现

设 ∀i∈[1,n],j∈[1,m],num(i,j)=(i−1)×m+j\forall i \in [1,n],j \in [1,m],num(i,j) = (i - 1) \times m + j。
把网格看做 n×mn \times m 的一维向量，定义 11 行 n×m+1n \times m + 1 列的状态矩阵 FF，下标为 00 至 n×mn \times m，其中 Fnum(i,j)F_{num(i,j)} 记录格子 (i,j)(i,j) 中石头的个数。
特别地，令 F0F_0 始终等于 11。
FF 会随着时间的增长而不断变化。设 FkF_k表示 kk 秒之后的状态矩阵。
在游戏开始时，根据题意和 FF 的定义，有：
F0=[100⋯0]F_0 = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 \end{bmatrix}
注意到操作序列的长度不超过 66，而 11 至 66 的最小公倍数是 6060，所以每经过 6060 秒，所有操作序列都会重新处于最开始的字符处。我们可以统计出第 kk 秒（1≤k≤601 \le k \le 60）各个格子执行了什么字符，第 k+60k + 60 秒执行的字符与第 kk 秒一定是相同的。
对于 11 至 6060 之间的每个 kk，各个格子在第 kk 秒执行的操作字符可以构成一个转移矩阵 AkA_k，矩阵行、列下标都为 00 至 n×mn \times m。
构造方法如下：
  1. 若网格 (i,j)(i,j) 第 kk 秒的操作字符为 N，且 i>1i > 1，则令 Ak[num(i,j),num(i−1,j)]=1A_k[num(i,j),num(i - 1, j)] = 1，表示将石头推至上方的格子。字符 W，S 与 E 类似。
  2. 若网格 (i,j)(i,j) 第 kk 秒的操作字符为数字 xx，则令 Ak[0,num(i,j)]=x,Ak[num(i,j),num(i,j)]=1A_k[0,num(i, j)] = x,A_k[num(i,j),num(i,j)] = 1，表示该格中原有的石头不动，再拿 xx 块石头。
  3. 令 Ak[0,0]=1A_k[0,0] = 1。
  4. 令 AkA_k 剩余部分均为 00。
上述构造实际上把状态矩阵的第 00 列作为"石头来源"，Ak[0,0]=1A_k[0,0] = 1 保证了 F0F_0 始终为 11，Ak[0,num(i,j)]=xA_k[0,num(i, j)] = x 相当于从"石头来源"获取 xx 个石头，放到格子 (i,j)(i,j) 中。
使用矩阵乘法加速递推，遇到常数项时，经常需要在状态矩阵中添加一个额外的位置，始终存储常数 11，并乘上转移矩阵中适当的系数，累加到状态矩阵的其他位置。

四、考虑答案统计

设：
A = \displaystyle \prod_{i = 1}^{60} A_i $$
t = q \times 60 + r(0 \le r \lt 60)
根据上面的讨论： 根据上面的讨论：
F_t = F_0 \cdot A^q \cdot \displaystyle \prod_{i = 1}^r A_i
使用矩阵乘法和快速幂计算该式，$F_t$ 第 $1$ 至 $n \times m$ 列中的最大值即为所求。 ## AC Code ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long const int N = 10, M = 65; struct matrix{ // 矩阵 ll c[M][M]; matrix(){memset(c, 0, sizeof c);} // 生成函数：初始值均为0 }; int n, m, t, act, x, y; ll mx; int idx[N][N], now[N][N]; matrix cg[M], sum, ans; char c, seq[N][N]; matrix operator*(matrix a, matrix b){ // 新定义矩阵乘 matrix u; for(int i = 0; i <= n * m; i ++) for(int j = 0; j <= n * m; j ++) for(int k = 0; k <= n * m; k ++) u.c[i][j] += a.c[i][k] * b.c[k][j]; return u; } int gt(int a, int b){return (a - 1) * m + b;} // 将网格中的点降维 matrix qpow(matrix a, int b){ // 矩阵快速幂 matrix u, x = a; for(int i = 0; i < M; i ++) u.c[i][i] = 1; for(; b; b >>= 1){ if(b & 1) u = u * x; x = x * x; } return u; } int main() { scanf("%d %d %d %d\n", &n, &m, &t, &act); for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++){ scanf("%c", &c); idx[i][j] = c - '0' + 1; } scanf("\n"); } for(int i = 1; i <= act; i ++) scanf("%s", seq[i]); for(int tim = 1; tim <= 60; tim ++){ // 生成前60次转移矩阵 for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++){ x = idx[i][j], y = now[i][j]; if(isdigit(seq[x][y])){ // 操作字符为数字 cg[tim].c[0][gt(i, j)] = seq[x][y] - '0'; // 从“石头来源”取x个石头 cg[tim].c[gt(i, j)][gt(i, j)] = 1; // 原来的石头数不变 } // 操作字符为NWSE if(seq[x][y] == 'N' && i > 1) cg[tim].c[gt(i, j)][gt(i - 1, j)] = 1; if(seq[x][y] == 'W' && j > 1) cg[tim].c[gt(i, j)][gt(i, j - 1)] = 1; if(seq[x][y] == 'S' && i < n) cg[tim].c[gt(i, j)][gt(i + 1, j)] = 1; if(seq[x][y] == 'E' && j < m) cg[tim].c[gt(i, j)][gt(i, j + 1)] = 1; // 该位操作位数+1 now[i][j] = (y + 1) % strlen(seq[x]); } } cg[tim].c[0][0] = 1; } // 统计前60次转移 sum = cg[1]; for(int i = 2; i <= 60; i ++) sum = sum * cg[i]; // 快速幂计算每60秒后的矩阵 ans.c[1][0] = 1; ans = ans * qpow(sum, t / 60); // 剩余的不到60次操作 for(int i = 1; i <= t % 60; i ++) ans = ans * cg[i]; // 统计最大石头数 for(int i = 1; i <= n * m; i ++) mx = max(mx, ans.c[1][i]); printf("%lld\n", mx); return 0; } ```

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...