单题分析
矩阵是CSP的高频考点,截至2021-9-16,已有以下考题(据不完全回忆)
-
AcWing 3206. 拼图
a)状态含义:状态表示单列的摆放情况,由于小物块有两列,所以前一列能影响后一列,状态转移由此产生,状态转移的后果是可能方案数的倍增。
b)结合:状态压缩(没有DP)。
c)初始转移矩阵:[i][j]表示状态i经过1列的转化后有几个可能(即几种不同的摆放方式)成为状态j,该矩阵需要结合题意宽搜或深搜计算得到。
d)初始计算矩阵:[i][j]表示第0列(列号0~n-1)只有0这一种可能状态,而且经过0列转换后只能变成0,且变成0只有一种可能,所以第0行除了[0][0]=1,其余列均为0。其余行的值不影响结果,见“最终结果”可知。
e)计算公式:C[i][j]+=A[i][k]*B[i][j],因为求可能方案数是乘积再累加。
f)最终的结果:求第0列经过n列后到达第n列时,有多少种可能由最初的状态0变成最终的状态0,故答案在[0][0]。 -
AcWing 3221. 最佳文章
a)状态含义:AC自动机中的点号,假若父为i,某子为j,则父i到子j的移动可视作一次状态转移,转移的后果是重要度的增加。
b)结合:AC自动机(没有DP)。
c)初始转移矩阵:[i][j]表示状态i经过向下找一次儿子j(即增加一个字母a~z)后能增加的cnt数(即儿子上的cnt),该矩阵遍历一遍AC自动机的所有父子对即可建立。
d)初始计算矩阵:[i][j]表示出发点是第0个点(root),找0次儿子后到达点0时,拥有的最大重要度为0,所以[0][0]初始化为0,第0行的其他列都初始化为极小值。同理,其他行的初始值不影响结果。
e)计算公式:C[i][j]=max(C[i][j],A[i][k]+B[i][j]),因为状态转移对重要度的影响是增加,而且记录的是最大值。
f)最终结果:点0经过n步跳转到达若干点,求其中的最大值。即第0列的最大值。 -
AcWing 3226. 矩阵
该题过于牛逼,不在笔者理解范围内,也不属于矩阵乘法的经典考法。不过私以为该题用strassen 矩阵乘法可以AC。 -
AcWing 3290. 1246
a)状态含义:若干个2到1位数(特别的是,虽然原本的四个1位数作为状态也能求解,但收敛速度明显慢,后20%的算例会超时),转移指一次数字的幂计算,结果是一个状态裂变成一个或两个状态。
b)结合:对数字的敏感、勇于尝试和一些想象力。还有结果值的倒溯
c)初始转移矩阵:[i][j]表示状态i对应的数I经过一次幂计算,能够得到状态j对应的数J的个数。需要人为计算后打表得到。
d)初始计算矩阵:数1对应的状态0经过0次幂计算得到1个0,故第0行除了第0列是1,其余列都是0。其余行同理不影响。
e)计算公式:C[i][j]+=A[i][k]*B[i][j],因为求个数是裂变乘积再累加。
f)最终结果:该题结果需要对查询值倒溯,直到得到一个状态数,查询第0行该数所在列即可。
总结
-
巧妙的是,初始状态矩阵只需要人为思考一步转移的情况,能节省很多脑力。
-
状态含义的提取、初始状态矩阵的计算、最初和最终计算矩阵的含义,这三点是解决该类题目的纲目。
-
状态压缩和AC自动机不一定就是DP,也有可能是矩阵乘法,不用DP而用使用矩阵乘法兼备可行性和必要性。可行性是因为状态或点之间,有清晰的状态一对一转移或一对多裂变,必要性是因为题目所给数据量太大,只能用矩阵的快速幂才能解。
-
状态转移不一定就是矩阵乘法,例如使用线段树的Acwing3286魔数一题,不用矩阵乘法主要是因为区间问题需要同时解决多个问题,而一个计算矩阵只能解决一个问题,同时该题没有超高的数据量,不能也没有必要用矩阵乘法。