-->

BZOJ 好题记录

做一道好题 比做十道水题还要有意义
这些大多数都是大赛的题目
多做好题 好好总结 提升实力
一步一个脚印 !


bzoj3206: [Apio2013]道路费用

Solution:最小生成树 + 搜索

首先我们考虑当某条边加进最小生成树上面 肯定是这条边是联通两个联通块的 值最小的
我们又观察 K是非常小的
不妨我们首先把这K条边加进去 然后再把原图的边加进去 然后再把K条边删掉
然后原图就变成了K+1个块 我们不妨把这K+1个块缩成一个点
然后我们用搜索搜出你要选那些边

现在就变成了K+1个点 原图上有边相连 你现在要加入一些边 且标上权值 使得这些边在生成树上 且权值最小
首先第一点 缩成K+1个点后 原图上剩余的边只有K条 其它边要不在块内 要不权值大 不在生成树上

我们已经搜索出你要选的边
先把这些边给连上 然后再把原图的边加进去构成一个生成树 这颗生成树就是你选出的边 然后构成的生成树
然后你在生成树上DP 把下面去到1的点权和给加上

然后用原图上的K条边去更新那些新的边
假设原图上有一条(x,y)的边
就把生成树上的所有新边给改掉
我是用idx[x]维护在生成树上x的新边 如果使原图上的边 idx[x]=0
然后统计答案就好了


bzoj4327: JSOI2012 玄武密码

Solution: SAM
因为是子串 直接把母串的SAM给建出来 然后其他串直接在上面跑就好了


bzoj4198: [Noi2015]荷马史诗

Solution: Huffman Tree
从题面可以简单的看出来 这是一颗K叉的哈夫曼树
但是我们有一个问题 就是不能直接像二叉那样 每次都选最小k个的合并
比如说有16个数 分三叉树
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
变成了
3 3 3 3 3 1
下一步按道理来说是变成了
9 7
16
其实应该变成
9 4 3
16
这样显然比较小
这是因为这个树不是满的K叉树 导致有些在下面的分支可以移上去上面空的地方
那我们就直接补0使得是满的K叉树就好了
是不是满的K叉树可以用
$$ (N-1) \equiv 0 \pmod{(K-1)} $$ 来判断
就是最后剩下一个 所以是N-1 每次消失K-1个 所以是%(K-1)


bzoj3881: [Coci2015]Divljak

Solution: AC-Trie+dfs序+树链的并
首先我们发现不变的是S集合 那么我们先把S集合用AC自动机建出来
然后建出fail树 那么一个S集合的末尾所在的子树下面的和 就是2询问时候这个串的答案
然后我们考虑建出一个T串 应该怎么维护这个fail树上的信息
这个T串会在自动机上 走到很多个点 这些点都在自动机的下面 也就是说是最长的子串
我们想想 如果直接把这些点都标上+1 是会出问题的
因为下面的点fail到上面已经出现过的点 在上面那个点的子树下 会标记了两次
我们要避免这种情况的出现 首先要排序去重 就是经过的点经过两次及以上要去掉
然后就是在树上的一系列点 这些点只对到根节点的链产生贡献 而我们要求的就是这些链的并
做法是 对于dfs序相邻的两个点 点分别是x和y
那么就是在:
dfn[x]上打+1标记
dfn[y]上打+1标记
dfn[LCA(x,y)]上打-1标记
然后子树询问也是一段dfs序的和