web analytics

noip提高组必须掌握内容

1、排序算法(快排、选择、冒泡、堆排序、二叉排序树、桶排序)
2、DFS/BFS 也就是搜索算法,剪枝务必要学! 学宽搜的时候学一下哈希表!
3、树
①遍历
②二叉树
③二叉排序树(查找、生成、删除)
④堆(二叉堆、左偏树、堆排序)
⑤Trie树
4、图(图论建模)
①最小生成树
②最短路径
③计算图的传递闭包
④连通分量(其中要掌握并查集技术)
强连通分量tarjin
⑤拓扑排序、关键路径
⑥哈密尔顿环
⑦欧拉回路(USACO 3.3 题1 Fence)
⑧Bell-man Ford、SPFA(能解决负权回路)(USACO 3.2 题6 Butter)
⑨二分图(匈牙利算法)(USACO 4.2 题2 stall)
5、动态规划(背包问题只是其中一种)
①线性动规
②区间动规
③树形动规
④图形动规
6、分治(掌握了动规分治就好学了)
7、贪心
8、位运算(可以用来进行优化)

Post a Comment

You must be logged in to post a comment.