发表于 | 分类于 | | + s

poj 2763

LCA+树状数组/线段树。

首先本题大致一看就是一个LCA，但是本题有操作更改某边的权，这样会使得原本的far数组变化，不难发现，更改边权后影响该边下面所有点的答案。此时可以在LCA的DFS预处理时求出DFS序列(即时间戳)，找到每个点管辖的范围，修改边权相当于修改该边连接的两个点深度深的那个点所管辖的范围，此时修改可以用暴力，但是由于far数组与LCA本身查询无关，我们可以用数据结构进行维护far数组，树状数组/线段树都可以

阅读全文 »

发表于 | 分类于 | | + s

poj 2299
注意开long long
权值线段树就是线段树每个节点存每个权值出现的次数，本题求逆序对应该算一个比较简单的权值线段树，注意离散化

阅读全文 »

发表于 | 分类于 | | + s

poj 1743

注意用$height$分组如果最后一组最后一个元素在序列末，那么要进行处理！最方便是直接$<=n$，还要注意的是不能重复，而且是$mini+x<maxi$不能是$mini+x<=maxi$

本题求的是长度最少为5的重复子串，并且重复子串可以加上或者减去一个数。我们将数字处理一下取差值，然后直接做，之后再结果$+1$即可

阅读全文 »

发表于 | 分类于 | | + s

poj 2186
Bzoj 1051
这题求所有满足被所有点能够到达的节点，那么我们可以进行缩点，缩点之后得到一个有向DAG图，统计新图的出度，如果有一个强连通分量的出度是=0的，那么输出这个强连通分量的大小，如果有多个，输出0

阅读全文 »

发表于 | 分类于 | | + s

poj 2342
树形DP基础题，具体看注释。
设状态$f[i][0]$为$i$不来，$f[i][1]$为$i$要来
$f[r][1] += f[i][0]$ r要来，i为r的下属
$f[r][0] += max(f[i][0], f[i][1])$ /不来，i为r的下属

阅读全文 »

发表于 | 分类于 | | + s

BZOJ 3531

树剖以后每个宗教建立一棵线段树，节点太多用传统方法开数组肯定不行，这里进行改进，使用了动态开点线段树，即需要这个点再开这个点。

知识点：
1、树剖后的编号注意
2、动态开点没有开到的点赋值不要赋-1而是赋值0，否则要很多细节处理

阅读全文 »