OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

8.4 小测1

题目放出来不是很好……就不放题目和代码了
稍微记录一下考试时候的一些记录
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码农题写个皮皮虾

READ MORE →

BZOJ1367 [Baltic2004]sequence

 

1367: [Baltic2004]sequence

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 1346  Solved: 550
[Submit][Status][Discuss]

Description

Input

Output

一个整数R

Sample Input

7
9
4
8
20
14
15
18

Sample Output

13

HINT

所求的Z序列为6,7,8,13,14,15,18.
R=13

Source

[Submit][Status][Discuss]
这题很神……左偏树论文题 百度文库有论文【之前我的左偏树也有挂过】
论文看不是很懂的可以去看看徐姥爷的题解
打错一个下划线wa N次,心痛一波ac率