题意

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

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

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

  • 数字 0 ~ 9:拿0 ~ 9个石头到该格子。
  • NWSE:把这个格子内所有的石头推到相邻的格子。
  • D:拿走这个格子的石头。

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

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

思路

考虑构造只有 1n\times m + 1 列的状态矩阵 F,然后给原方阵中 ij 列的元素标号 f(i, j) = (i – 1)m + j。然后由于所有操作序列长度不超过 6,所以最多 \operatorname{lcm}(1, 2, 3, 4, 5 ,6) = 60 次之后就会出现循环,所以考虑 t = 60q + r,r\in[0, 60)。然后构造 t\in[1, 60] 中每个时间的转移矩阵 A_k,令 A_0 = \prod A_k,则答案为 F_0 \times A_0^q +\times \prod_{k = 1}^rA_k

转移矩阵的构造想通了就很简单了:

A_k 的左上角赋为 0,如果操作为数字那就 A_k[0, f(i,j)] = opt, A_k[f(i,j),f(i,j)] = 1,如果是移动的话那就 A_k[f(i, j),f(i’,j’)] = 1

但是要注意细节:

  • 矩阵初始化问题
  • 乘千万不要写成 A_0\times F 了,是错的。
  • long long
#include <cstdio>
#include <cctype>
#include <cstring>
#define R register
#define il inline
#define FOR(i, a, b) for (R signed i = a; i <= b; ++i)
#define int long long
#define dbg printf("debug\n")

char act[11][7], org[11][11];
int actlen[11];

int n, m, acts, t;
int a[81];

il int num(int i, int j)
{
    return (i - 1) * m + j;
}

il int max(int a, int b) {return a > b ? a : b;}

struct Matrix
{
    int r, c, a[81][81];
    void init(int _r, int _c)
    {
        r = _r, c = _c;
    }
    int max_element()
    {
        int ret = -1e9;
        FOR(i, 0, r)
            FOR(j, 0, c)
                ret = max(ret, a[i][j]);
        return ret;
    }
    Matrix()
    {
        memset(a, 0, sizeof a);
    }
} ans, A[61];

Matrix operator*(const Matrix &a, const Matrix &b)
{
    Matrix ret;
    ret.init(a.r, b.c);
    int r = ret.r, c = ret.c, p = a.c;
    FOR(i, 0, r)
        FOR(j, 0, c)
            FOR(k, 0, p)
                ret.a[i][j] += a.a[i][k] * b.a[k][j];
    return ret;
}

signed main()
{
    scanf("%lld %lld %lld %lld", &n, &m, &t, &acts);
    FOR(i, 1, n)
        scanf("%s", &org[i][1]);
    FOR(i, 1, n)
        FOR(j, 1, m)
            a[num(i, j)] = org[i][j] - '0';
    FOR(i, 0, acts - 1)
        scanf("%s", &act[i][1]), actlen[i] = strlen(&act[i][1]), act[i][0] = act[i][actlen[i]];
    int N = n * m;
    ans.init(0, N);
    ans.a[0][0] = 1;
    FOR(k, 0, 60)
        A[k].init(N, N);
    FOR(k, 1, 60)
    {
        A[k].a[0][0] = 1;
        FOR(i, 1, n)
            FOR(j, 1, m)
            {
                int idx = k % actlen[a[num(i, j)]];
                char opt = act[a[num(i, j)]][idx];
                if (isdigit(opt))
                    A[k].a[0][num(i, j)] = opt - '0', A[k].a[num(i, j)][num(i, j)] = 1;
                else
                {
                    if (opt == 'N' && i - 1 > 0)
                        A[k].a[num(i, j)][num(i - 1, j)] = 1;
                    else if (opt == 'E' && j + 1 <= m)
                        A[k].a[num(i, j)][num(i, j + 1)] = 1;
                    else if (opt == 'S' && i + 1 <= n)
                        A[k].a[num(i, j)][num(i + 1, j)] = 1;
                    else if (opt == 'W' && j - 1 > 0)
                        A[k].a[num(i, j)][num(i, j - 1)] = 1;
                }
            }
        if (k == 1)
            A[0] = A[k];
        else A[0] = A[0] * A[k];
    }
    int q = t / 60, r = t % 60;
    for (; q; q >>= 1)
    {
        if (q & 1)
            ans = ans * A[0];
        A[0] = A[0] * A[0];
    }
    FOR(i, 1, r)
        ans = ans * A[i];
    printf("%lld\n", ans.max_element());
    return 0;
}
最后修改日期:2021年1月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。