【游记】ZROI 21noip赛前20天 赠送赛1

发表于 分类于 阅读次数： Valine：

比赛链接（正睿）

T1 T2 T3
得分 0 0 30
估分 0 0 60

第一题花了半个小时并没有理解题意，跳过。

第二题没有手模出样例，跳过。

第三题看起来比较可做。定义\(s_n=s_{n-1}+s_{n-2}\)定义字符串的权值为最大的\(i<|s|\)满足\(s\)的长度为\(i\)的前缀等于长度为\(i\)的后缀。给定\(n,m\)，求字符串\(s_n\)的前\(m\)个字符的权值。

首先很容易就想到，权值的定义就是\(\text{KMP}\)中\(border\)数组的定义，所以递推出\(s_n\)后跑\(\text{KMP}\)即可，可以拿到\(30\)分。之后将答案打表，就能发现一些规律，可以获得\(60\)分。但由于我忽略了答案要取模，\(60\)分挂成了\(30\)分X﹏X