二分

POJ1064

二分绳子长度,可以直接用实数二分,但最后结果注意要向下取整,可以用floor*100再/100去实现

 POJ3273

直接二分额度,可以二分答案的同时二分查找

CF549H

二分差值,当利用这个差值来构造的矩阵最大值>=0且最小值<=0时,一定存在着令其等于0的情况

三分

显然这个x不能太大,也不能太小.

然后就粗略的知道了这是个单峰函数.

三分x,利用前缀和算最大和最小区间和.

然后基于abs比较

BZOJ1857

三分套三分

正确性我不会

在AB上三分一个点,然后在CD上三分一个点算最小距离

POJ1486

将字母在矩形范围内的连边后二分图匹配.

每次去删一条边再跑一边判断这条边是不是必选的.

POJ 2724

二分图匹配

连边的两个数相差一个’1’,显然连边不存在奇环

在连边的时候可以通过c=a^b ,判断c==(c&-c),就可以知道是否只相差1个’1’(学姐太巨了)

还有就是match数组初始化要为-1,因为有0这个数(WA了半天不知道为什么)

 

DINIC求最大流模板

POJ2173

网络流模板题,求1到n的最大流

POJ3041

二分图匹配可做题,把每一行每一列进行匹配即可

POJ3057

还是二分图匹配题,但建图可能比较麻烦,我们把每个时刻的门看做一个节点,枚举时间让人去不断的和门进行匹配,直到一个时刻人匹配上的数量等于总人数就是最小人数.

POJ1149

最大流问题,对于每个买猪的人,可以看做是从上一个人手中买的猪。

这样的话建图就是源点向猪圈建边

猪圈向第一个买猪的人建边

然后每个买猪的人向下一个买这个猪圈猪的人建边

最后人向汇点建边

POJ3281

最大流问题

源点向吃的建边

吃的向牛建边

牛向喝的建边

喝的向汇点建边

但是每头牛只能吃一个喝一个

所以把牛拆成两个点,连一条容量为1的边即可

POJ3469

最小割,按照题中条件建图后跑最小割即可

 

 

POJ1061

exgcd棵题,解方程(m-n)x+Ly=c

POJ2142

exgcd

对于方程的所有解,选出|x|+|y|最小的一组,若有多组,则找到|ax|+|by|最小的一组

 

POJ2115

还是exgcd.

Cx+(1<<K)y=B-A

POJ1006

中国剩余定理(欢迎百度或者访问这里)

POJ2720

两两合并同余方程.

将两个方程相减,得到一个新的标准的exgcd的方程.然后继续两两合并.

CF527A

求更相减损之术的次数,可以用gcd的方法写

 

对一棵带有点权的树,多次对路径进行修改.询问操作

算法思路:把这棵树分成重边和轻边,重边就是指向重儿子的边,重儿子就是所有儿子中子树最大的点.

对于一条重链,用线段树去维护,所以要让一条重链上的所有点在一段连续的序列中.所以我们在dfs的时候把重儿子调成最先遍历的点,这样得到的dfs序列就是满足要求的.

轻重边有几个性质:
性质 1:如果 ( u , v ) 为轻边,则 size ( v )  size ( u ) / 2 。
证明:设 size ( v )  size ( u ) / 2 ,则 size (v ) 必然比其他儿子的 size 要大,那么 ( u , v )
必然为重边,与 ( u , v ) 为轻边矛盾。
性质 2:从根到某一点 V 的路径上的轻边个数不大于 O (log n ) 。
证明:V 为叶子节点时轻边个数最多。由性质 1 可知,每经过一条轻边,子树的节
点个数至少比原来少一半,所以至多经过 O (log n ) 条轻边就到达叶子节点了。
性质 3:我们称某条路径为重路径(链),当且仅当它全部由重边组成。那么对于
每个点到根的路径上都不超过 O (log n ) 条轻边和 O (log n ) 条重路径。
证明:显然每条重路径的起点和终点都是由轻边构成,而由性质 2 可知,每个点到
根节点的轻边个数为 O (log n ) ,所以重路径个数也为 O (log n ) 。

通过这些性质我们就可以加以利用线段树使我们的操作的复杂度变为O( (logn)^2)

ZJOI2008

棵题,利用两次dfs预处理,类lca的做法爬树询问

BZOJ2243

线段树维护右儿子,左儿子颜色,以及区间颜色段数目.

区间修改操作和正常询问差不多

询问时要比较每次重链区间左端点颜色和fa[左端点]的颜色,如果一样,就ans-=1

注意:线段树不要写跪!

谢谢YL大哥

 

POJ3264

st表棵题,st表维护最大最小值

CF359D

二分区间长度,枚举起点,st表维护区间最小值和gcd判断是否可行

 

POJ3630

trie树棵题,经过一个被标记的点,或者在添加一个字符串的最后一个字母没有建一条新边,就存在前缀.

POJ2945

trie树对点打标记计数(map能过)

POJ1816

正常建trie树后跑字符串的时候暴力跑,dfs所有情况

CF633C

dp思想,对于一个位置往回找字符串,如果找到了那个位置正好被更新过,就可以继续dp往下转移,用trie找字符串可以降低复杂度

 

 

POJ3461

模版题.

POJ2406

求字符串中最短循环节个数

循环节长度为l,有n个循环节,则最后一位的next显然是l*(n-1)

(暴力可过)

CF526D

利用next数组求循环节个数,然后判断能否将其中一些ABAB当作一个A之类的压缩操作使得满足题意。