OceanEye's Blog

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

@OceanEye7年前

05/11
16:46
OI

BZOJ1227

这题很裸,离散化一维本来想写个动态开点的线段树的之后逐行处理答案。

大概就是经过一个点就更改对应节点上的value,这个值要用组合数来算一下。

懒得看怎么处理附属就只去看了HZWER的题解……后来自己写了个很暴力的东西:-D。

具体怎么做下面也有:-D大力安利HZWER

代码

 

BZOJ1227

@OceanEye7年前

05/9
21:15
OI

BZOJ4808

题目名字很有趣

但是看完题面会发现这就是个黑白染色最小割

网络流大法好,ISAP直接跑

好像这几道题是一个系列的233

 

BZOJ4808

@OceanEye7年前

05/7
22:56
OI

BZOJ2434

AC自动机的好题,充分利用了fail树的性质

性质:S串中每个包含了T的后缀的fail指针一定经过若干层指向T

fail指针不成环

把fail树上的点dfs重标号

处理单个询问时可以把S串中的每个节点的DFS序丢进树状数组里面

查询T对应节点的DFS区间即可

处理许多询问的话离线处理即可

为了保证在树上不跑 \(x^2\) 次

可以模拟之前插入节点的方式来计算……

当然开个vector在节点上记录id也是可行的……

代码应该很好看懂

[但是我写的代码一般都巨长所以没多少人看哈哈哈]

 

BZOJ2434

@OceanEye7年前

05/6
13:45
OI

BZOJ2780

广义后缀自动机

良心题,教会了我怎么写广义后缀自动机……

其实就是加完一个串之后把last丢回root接着跑啊qaq

这是非TRIE树版本

 

TRIE树什么的等会再写

BZOJ2780

@OceanEye7年前

05/4
19:49
OI

BZOJ4318

期望DP
题目要求维护三次方
所以要把二次和一次的期望也给维护了,接着考虑我们DP的含义是什么。
DP[3][i]=DP[3][i-1] + (增长幅度=x^3-(x-1)^3)*(增长概率=p[i])
上面那个三次方展开一下就可以做了

BZOJ4318

@OceanEye7年前

04/17
08:26
OI

BZOJ2809可并堆裸题

题面大概是这样子的:

很裸,就学了一下可并堆的姿势然后就写了
1A啊:-D
写的是左偏树,安利百度文库的文章
但是不知道为什么跑了3k+ms
不理了可能是vector的原因吧

BZOJ2809可并堆裸题

@OceanEye7年前

04/14
17:38
OI

BZOJ1858: [Scoi2010]序列操作

题目链接

好久没写过这么长的代码了= =

像狗一样看了一个上午终于在下午的时候狠下心来写对拍

对拍大法好qwq

一份暴力一份正解

以后有空再写线段树

暴力

正解

 

BZOJ1858: [Scoi2010]序列操作

@OceanEye7年前

04/13
21:39
OI

BZOJ4816 莫比乌斯反演

nlogn狄利克雷卷积打表

和普通的差不多,就是和换成积,贡献算一算就可以了

然后死活想不起来  写 O(n根号n) 的TLE到死

安利 金策大爷 的教程

贴完代码跑路qwq

 

BZOJ4816 莫比乌斯反演

@OceanEye7年前

04/12
23:33
OI

BZOJ4299 CodeChef FRBSUM

很强的题目= =超级烦

想来想去想不懂怎么写

一个很朴素的想法就是排序然后一个一个加进去

假设当前已经满足可以取[0,P]之间的取值

新进来一个数q

如果q在[0,P+1]之间的话就可以拓展 P -> P+q

否则停止拓展,因为显然后面那一堆都不满足要求

然后我就不会了= =跑去翻了翻题解  [传送门]

发现可以连着处理一段的sum,时间复杂度大致是单次log方的。

真神奇

 

BZOJ4299 CodeChef FRBSUM