寒假复习

树链剖分

按dfs序重排点权,边权需要按照点权来做

对于链查询通过数据结构(线段树,bit等)可以有效降低复杂度

一般采用轻重链剖分

时间复杂度nlogn-nlog2n

【BZOJ1036】【ZJOI2008】 树的统计

裸题,剖完查询和修改直接走数据结构

【NOIP2013】 货车运输

MST+LCA

当然也可以树剖

边权树剖要先dfs序重排编号然后再按重排编号

和点权不同的是查询的时候x=y就直接结束,点权的情况还要加上那个点而边权则不存在那条边

【BZOJ2243】 【SDOI2011】染色

奇怪的线段树

比较难的地方在于两端相邻区间交界处的颜色有可能相同. 那么此时查询结果不能直接简单相加.

用线段树维护三个值 :

区间颜色总数 区间最左端的颜色 区间最右端的颜色,

这样就能把区间分界线的情况表示出来了.

【BZOJ3531】 【SDOI2014】旅行

宗教改变的话会影响整个的路径

考虑对每个宗教建立一个线段树

再考虑空间开销,只能采用动态开点的线段树了

树状数组

【LightOJ1266】Points in Rectangle

二维树状数组维护前缀和直接做

四个矩形加加减减

注意bit不能处理下标为0的,所有下标手动+1

网络流

【LightOJ1071】Baker Vai

本题又叫传纸条

高维dp双线程之类的当然可以做

这类传来传去的问题可以通过网络流建模来做,拆点,加流量限制,跑费用流

根据题意再处理下端点

【UVA11082】Matrix Decompressing

给定矩阵的每行每列的和,矩阵中每个元素在1-20之间

给定上下界的网络流

每个格子拆点,中间限流量19

A点连S,加行限流

B点连T,加列限流

跑一跑最大流输出每个边流量+1

0 条评论
发表一条评论