OceanEye's Blog

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

@OceanEye7年前

08/5
16:12
OI 杂记

心情复杂

近来的训练暴露了很多的问题

我已经不会打暴力了

可能是OI比赛玩少了,就不会打暴力了?

但是更心寒的是我的知识点的欠缺

一下是待补的坑:

LCT

SA

数学姿势

DP优化姿势

考试的姿势……

心情复杂

 

心情复杂

@OceanEye7年前

08/4
15:27
OI 杂记

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 →

8.4 小测1

@OceanEye7年前

08/3
11:38
OI

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率

BZOJ1367 [Baltic2004]sequence

@OceanEye7年前

07/13
14:46
OI

BZOJ4361

神奇树状数组优化DP+组合数
思路很暴力……但是就是比较难连起来

第一步:
dp[i][j]表示枚举到第i位结尾且以第i位为结尾时 不下降子序列长度为j的情况数量

\( dp[i][j]=\sum_{k=1}^{j}(dp[i-1][k]) \)

第二步:
令 g[x] 表示所有长度为x的 不下降子序列 的数量

\( g[x]=\sum_{k=1}^{n}dp[k][x] \)

可以发现我们的ans和这个g[x]是由联系的
长度为x的 不下降子序列 的数量……和两个东西有关系

第一类—->从g[x+1]直接减少一位过来 第二类—->从非g[x+1]的过来 【参照定义理解】
第二类的数量是要记入答案的数量的
就稍微的暴力用n阶乘来做就好了,反正n不大

\( ans=\sum_{k=1}^{n}g[k]*(n-k)!-g[k+1]*g[k+1]*(n-k-1)!*(k+1) \)

以下代码

 

BZOJ4361

@OceanEye7年前

07/11
15:00
OI

NOIP2013货物运输

为什么我在写这题的题解……
因为这题我本来想用树剖搞过去的……结果炸了
:-D然后就写了现在的倍增

NOIP2013货物运输