@OceanEye7年前
08/4
15:27
题目放出来不是很好……就不放题目和代码了
稍微记录一下考试时候的一些记录
T1
dp[i][j][0/1]
pos : i
cnt : j
Connecting : 0/1
可以留意到最大字典序的子串一定包含了答案
而且一定是从开头包含
可以考虑利用这一点瞎搞
比如我们二分它这条最长串的长度，之后尝试构造？
这里的构造是我们要造出最大串是二分得到串的，且个数尽量小
可以考虑用kmp解决
kmp 匹配之后 在匹配结束的地方砍一刀
没有匹配就继续
这样子就是nlogn的
但是怎么找到最长的子串还是个问题……
我想到的是用SAM
好烦啊不想用SAM啊
T2
F(0,n) = n+1
F(m,0) = F(m-1,1)
F(m,n) = F(m-1,F(m,n-1))
打个表找找规律吧
日哦……真的烦
有点像是
F[0,n]=n+1
F[1,n]=n+2
F[2,n]=2*n+3
F[3,n]=F[2,F[3,m-1]]
F[3,0]=2+3
F[3,1]=4+3*(1+2)
F[3,2]=8+3*(1+2+4) = 29
F[3,3]=2*29+3
打完表
应该是30分
回去看T1
思路没什么错……就是代码量比较大
T3还剩五十分钟看出来是一个树链剖分套四tag线段树
mdzz码农题写个皮皮虾