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之类的压缩操作使得满足题意。

 

2-sat问题,根据我个人理解,大概就是有一些条件,如果选a必须选b,就从a向b连一条边,最后tarjan强连通分量

POJ3648

根据m对关系,将其中一个人向另一个人的对象连边,最后可以搜出新郎这边都有谁,然后输出他们的对象就行了

POJ3648

把1到n拆成两个点,代表i这个位置选1还是选0,再根据关系建边,最后判段i选0和选1是否在一个强连通分量中

POJ2749

二分最大边,当两点距离大于二分值的时候,对另一种情况建边

 

无向图tarjan

今天也接受了许多新概念,割点.桥.边/点双连通分量.今天用了一下午的时间来学习这些知识,写了两道半的题.

POJ3177

求每个边双连通分量,并查集缩点之后找叶子,输出(叶子数+1)/2即为答案

POJ1523

求每个割点,以及割点割出来的连通块,在求割点的同时可以处理好

POJ2942

求出每个点双连通分量,然后不是二分图的分量就是答案

emmm..

今天大概学会了tarjan强连通分量,还是挺有收获的.以前也很多次想学会这种算法,但真的就是学不会啊..

经过一晚上也对这种算法有了一定的理解,照着AC代码写了例题之后,自己也把剩下的两道练习题写完了,以前也没写过强连通分量的题,今天写完了之后还是挺激动的.

例题 POJ2186

求强连通分量后找入度为0的强连通分量中的每一个点都是受欢迎的牛.

代码:

POJ3180

求有多少个大小>1的强连通分量

代码:

POJ1236

求强连通分量,对于task1,显然找有多少个入度为0的点即为答案

task2,对于一个出度为0的点,可以和一个入度为0的点连起来,最后搞成一个强连通分量,答案就是入度为0的点和出度为0的点get_max.