首页 > 代码库 > 一周总结

一周总结

          一周总结

树状dp

在一棵树上进行状态转移,一般在树上遍历的时候,

有返回到父节点的有不需要返回的,有无根树的遍历

(即任意一点都可作为一个根),但状态方程的转移还是从父结点到儿子节点的递归转移。

Hdu 1296 题意:求任意一个点作为根,求该树的半径

两次dfs 第一次求出以该点为根的最大距离和次大距离,带二次比较一下用dfs就行了

POJ 2486 apple 状态转移方程有3个,刚开始想了两个,少想一种情况,那就是何时走当前子节点的问题了。

POJ 1947  删最少的边,形成一个有p个节点的子树

树上的背包,要从大到小枚举

POJ 2378

高斯消元

POJ 1830 其实就是求自由元的个数。

POJ 3185 求最优方案,枚举自由元求最优方案

Hdu 3949 求异或第k个满足条件的数,对a[i]直接进行处理,处理后每个a[i]对应一位

POJ 1681 求高斯消元以后的结果,注意不存在自由元

SGU 275 求异或之后的最大值,与hdu 3949

Hdu 3364 POJ1830

 

后缀数组:

后缀数组关键对sa[],rank[],height[]三个数组的理解

题目

Hdu 4416

SPOJ PHRASES

POJ 3294

POJ 1743

POJ 3261

SPOJ DISUBSTR

POJ 3693

POJ 3581

 

 

数学费马小定理,斯特灵数,贝尔数,欧拉函数等还没看完,做了45道题,感觉东西挺多的。