【题解】洛谷P4838 P哥破解密码

题目

洛谷P4838 P哥破解密码

题解

对于n<=1e7的数据,可以使用常规的动态规划。用f[i][0/1/2]分别表示长度为i,且以AA/A/B结尾的字符串的数量。可以得到状态转移方程:

f[i][0]=f[i-1][1] , f[i][1]=f[i-1][2] , f[i][2]=f[i-1][0]+f[i-1][1]+f[i-1][2]

对于大数据,使用矩阵优化。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月16日 下午5:35

【小白解析】
此题考验矩阵加速和动态分配的结合。

f[i][0]=f[i-1][1]

f[i][1]=f[i-1][2]

f[i][2]=f[i-1][0]+f[i-1][1]+f[i-1][2]

这三段代码所论述的情况分别是现有长度为i的字符串,其结尾为AA(0),A(1),B(2)的三种情况:

  1. 若现有字符串以AA结尾,长为i-1的字符串必须以A结尾(F[i-1][1]),在此基础上再衔接一个A;
  2. 若现有字符串以单个A结尾,长为i-1的字符串必须以B结尾(F[i-1][2]);/*为毛不能加上F[i-1][1]?因为这种情况下就变成AA了。*/
  3. 若现有字符串以B结尾,长为i-1的字符串无特殊结尾要求。

随后,第30至32行构建的转移矩阵负责上述三种情况的相加。矩阵从左至右,每一列对应一种情况。
29行的st为初始矩阵(列向量),st.s[1][1]是因为没有长度为1而以AA结尾的字符串。
36行的n-1是因为字符串初始时已长度为1,不需要从0到1的操作判断。
38行,最后得出的所有情况相加,即为所求的结果。
*有生之年多看这道题几眼吧。