OceanEye's Blog

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

@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年前

05/11
16:46
OI

BZOJ1227

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

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

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

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

代码

 

BZOJ1227

@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/2
20:40
OI

BZOJ3236

看着这道题觉得很神啊

于是写了个n根号nlogn的就开始跑了

然后就跑过去了……

95s的AC

不过写这份代码好像只花了我十分钟?说明我码力还算不错么qwq[单身狗的怨念]

 

BZOJ3236

@OceanEye7年前

04/21
16:09
OI

BZOJ3262

CDQ分治做三维偏序
很裸很裸
直接看代码吧= =

[CDQ分治的思想就是一段询问有三个维度,离散化两个维度,对第三个维度我们扫一遍来计算贡献]
[通常取mid是比较优秀的]

BZOJ3262