2019 Multi-University Training Contest 2 task:8/8/12

TCO20 Parallel 3B: ShortBugPaths

• 分类：DP，计数
• 题意：一个 $n\times n$ 的方格，跳 $j$ 次，每次可以跳 $d_1$ 步或 $d_2$，… 或 $d_m$ 步，问可能的路径条数。$n\leqslant 10^9, 0\leqslant j \leqslant 10, 0\leqslant d_i\leqslant 10$
• 解法：边界只对位于边界 100 格内的格子起作用（因为 100 格以外的不会撞上墙），那么对于较大的 $n$ 我们可以直接按照 $n=300$ 来做，然后直接复制填充计数即可。
• 评论：状态精简，小心 fst

HDU6599

• 分类：PAM,manacher/hash
• 题意：给定字符串，一个字符串满足条件当且仅当本身是回文串且前一半也是回文串，求每个长度满足条件的串个数
• 解法：直接manacher求出每个点最长的回文串，建立pam时对pam上每个点存下他的长度lenth以及在原串中的位置pos，pam上每个新点，通过lenth和pos和manacher求出的回文串长度来判断该点的回文串是否满足条件，最后遍历parent树，统计所有满足条件的节点
• 评论：不熟PAM，开始还以为不能这么做

无

ABC175，TCO20R3B

AGC047E, ABC175D, ABC175E, TCO20R3B[300 / 500 / 1000]

无

ABC175，TCO20R3B

Educational Codeforces Round 93 C,D,E,F,G

ABC175 A,B,C,D,E