最近校内开始打联赛模拟题了。感觉一直做散题可能会找不到打比赛的感觉,于是就随便打了一场。

比较正常的联赛难度,花了1.5h AK(加上各种对拍接近2h)。感觉状态还是在的,就怕真的到了场上又是另外一个样子了。。。


T1

题意是给$n$个数,$n\leq500$,让你用这些值排出一个序列,使得满足斐波那契序列的性质($f_n=f_{n-1}+f_{n-2}$)。

没啥难度,直接枚举前两个数,由于fib序列的值是指数级的,所以这个序列会比较短,直接暴力一个个往后找就行了。


T2

让你构造一个$n$个字母的排列($n\leq26$),使得这个排列的第$k$小子串为给定串。

由于是个排列,所以子串的顺序比较好确定。转化模型之后就变成了一个背包,直接枚举给定子串出现位置后$O(n^4)$瞎DP就行了,总复杂度$O(n^5)$。


T3

给一个字符串(长度$2\times10^5$内),让你统计有多少个本质不同的子串,满足这个子串循环左移一位后依然是该字符串的子串。

SAM裸题,跑出SAM之后直接考虑每个状态的可行转移,根据字符左端点在不在该状态内,分两种情况统计一下就行了(一种是左端字符还在该状态内,另一种是怼到parent树中的别的儿子的状态里面去了,需要另外统计一下)。