分析
读完题我注意到以下几点:
+ 状态之间的递推是线性的(只有一次项)
+ 变化次数特别多,但是每次的变化量相对较小
这时我想到可以用矩阵快速幂加速递推
于是我接着寻找矩阵加速递推的其他条件:
+ 状态可以抽象为一维向量
+ 状态之间的转移矩阵不变
我发现本题不满足第二条,于是我偷看了题解,之后晓得了:
+ 转移矩阵的变化呈循环式,最小循环节最大为60
,即LCM{1,2,3,4,5,6}
之后我尝试计算时间复杂度上界,应为O( 65^3*lg(T/60) )
其中65^3
为矩阵乘法的时间花销,lg(T/60)
为快速幂的时间花销,我忽略了无法整除的部分,时间较为紧张,大概进行6e6
次运算;之后尝试计算空间花销,约为8^4*60*8
字节,特别地,应考虑每个64位长整型的储存占用8个字节,空间允许。
设计
将二维数据转化为一维向量的方法:使用函数将二维数组下标[i][j]
映射到一个整数代表其值在一维向量中储存的位置,具体地说,我构造了[i][j]
到(i-1)*m+j
的映射。
状态向量:1行n*m+1
列的一维向量,任何时候保证第一行第一列的元素为1。
将输入数据转化为转移矩阵(方阵):遵守上述映射,我进行如下构造:
+ N操作:Tran [ pos ( i,j ) ][ pos ( i-1,j ) ] = 1
(其中Tran
为转移矩阵,pos ( i,j )
为映射函数,下同)
+ S操作:Tran [ pos ( i,j ) ][ pos ( i+1,j ) ] = 1
+ W操作: Tran [ pos ( i,j ) ][ pos ( i,j-1 ) ] = 1
+ E操作: Tran [ pos ( i, j ) ][ pos ( i,j+1 ) ] = 1
+ 取石子操作: Tran [ pos ( i,j ) ][ pos ( i,j ) ] = 1;Tran [0][ pos ( i,j ) ] = num
(其中num为取得的石子数,特别地,我使状态向量的0位置始终为1(通过赋初值和Tran [0][0] = 1
实现),这样的话Tran [0][x] = y
就表示使x位置增加y)
+ 将转移矩阵的其他位置均赋为0
特别地,对于前四种操作,应注意边界问题,由此可以将输入数据转化为转移矩阵。
运算:用快速幂计算整60
秒(完整循环节)的部分,逐个计算不满60
秒的部分,将前两部分相乘的结果与初状态向量相乘即为最终地图上每个格子的石子数,取最大值即可。
Mat 结构体储存矩阵
Mat I 为单位矩阵
Mat tran [] 为每秒的转移矩阵
Mat abr 为60秒的转移矩阵的连乘积
int ope [] 为某个格子对应的操作类型
char how [][] 为某个操作字符串
编码
#include<bits/stdc++.h>
namespace OI
{
#define il inline
#define rg register
typedef long long LL;
using std :: getchar;
using std :: max;
using std :: min;
bool rd ( int &k ){
char c = getchar (); while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) ){ c = getchar (); }
if ( c == EOF ){ return false; } bool neg = false; if ( c == '-' ){ neg = true; k = 0; }else{ neg = false; k = c - '0'; }
c = getchar (); while ( c >= '0' && c <= '9' ){ k = (k<<1)+(k<<3)+c-'0'; c = getchar (); }
if ( neg ){ k = -k; } return true;
}
const int N = 65;
const int O = 10;
const int L = 6;
struct Mat{
int r, c; LL s [N][N];
Mat ( int r = 0, int c = 0 ):
r (r), c (c) { memset ( s, 0, sizeof ( s ) ); }
} I, tran [N], abr;
Mat operator * ( const Mat &a, const Mat &b ){
Mat c = Mat ( a.r, b.c );
for ( rg int i = 0; i < c.r; ++i ){ for ( rg int j = 0; j < c.c; ++j ){ for ( rg int k = 0; k < a.c; ++k ){
c.s [i][j] += a.s [i][k] * b.s [k][j];
} } }
return c;
}
int n, m, ope [N], len [O], side;
char how [O][L];
il int pos ( int i, int j ){ return (i-1)*m+j; }
il void table ( int sec ){
tran [sec].s [0][0] = 1;
for ( rg int i = 1; i <= n; ++i ){
for ( rg int j = 1; j <= m; ++j ){
int myPos = pos ( i, j );
char c = how [ ope [myPos] ][ sec % len [ ope [myPos] ] ];
if ( c >= '0' && c <= '9' ){
tran [sec].s [myPos][myPos] = 1;
tran [sec].s [0][myPos] = c - '0';
}else if ( c == 'N' && i > 1 ){
tran [sec].s [myPos][ pos(i-1,j) ] = 1;
}else if ( c == 'S' && i < n ){
tran [sec].s [myPos][ pos(i+1,j) ] = 1;
}else if ( c == 'W' && j > 1 ){
tran [sec].s [myPos][ pos(i,j-1) ] = 1;
}else if ( c == 'E' && j < m ){
tran [sec].s [myPos][ pos(i,j+1) ] = 1;
}
}
}
}
il Mat power ( Mat base, int ind ){
Mat ans = I;
while ( ind ){
if ( ind & 1 ){ ans = ans * base; }
base = base * base; ind >>= 1;
}
return ans;
}
void Main (){
rd ( n ); rd ( m ); int time, act; rd ( time ); rd ( act );
char temp [N];
for ( rg int i = 1; i <= n; ++i ){
scanf ( "%s", temp );
for ( rg int j = 1, k = 0; j <= m; ++j, ++k ){
ope [ pos(i,j) ] = temp [k] - '0';
}
}
for ( rg int i = 0; i < act; ++i ){
scanf ( "%s", how [i] );
len [i] = (int)strlen ( how [i] );
}
side = n * m + 1;
I = Mat ( side, side ); for ( rg int i = 0; i < I.r; ++i ){ I.s [i][i] = 1; }
abr = I;
for ( rg int i = 0; i < min ( time, 60 ); ++i ){ tran [i] = Mat ( side, side ); }
for ( rg int i = 0; i < min ( time, 60 ); ++i ){ table (i); }
for ( rg int i = 0; i < min ( time, 60 ); ++i ){ abr = abr * tran [i]; }
Mat begin = Mat ( 1, side ); begin.s [0][0] = 1;
begin = begin * power ( abr, time/60 );
for ( rg int i = 0; i < time%60; ++i ){ begin = begin * tran [i]; }
LL maxStone = 0;
for ( rg int i = 1; i < begin.c; ++i ){ maxStone = max ( maxStone, begin.s [0][i] ); }
printf ( "%lld", maxStone );
}
}
int main (){
OI::Main();
return 0;
}
编码中遇到的问题包括但不限于:
+ 混淆了n
和m
+ 未将abr
矩阵的初值设为I(单位矩阵)
更新
- 修改了时间复杂度上界
orz🐮搬
码风清奇 还有 $6e6$ 是完全可以接受的时间 c++如果卡常甚至可以跑 $5e7$ 的运算量 你又不用
stl
又不是别的什么语言 为什么不可以呢好活当赏