c++&oi

迎接初中同学——整理OI知识点(building)

这次省赛被初中小朋友虐爆了。
然后中考快(到了)结束了。
迎接一下初中的小朋友。
整理一下个人认为MAS的OIer成长所需的练习。

目录
零。说明
一。学习内容
二。练习题
三。推荐书目
四。资料

零。说明
   -第一部分列举了所有我所知道的要学的知识(不仅仅是的NOIP所需的知识),不要被数量吓到,具体的人我可以具体推荐学习内容。
   -可以直接跳到第二部分做练习,然后对照第一部分,看看自己掌握了那些知识。
   -仅代表个人观点,请以老师的要求为准。
   -我也很弱,互相学习。


一。学习内容(不是很好区分难度,详见练习题):
0.windos及linux基本的系统命令以及对拍方法。
1.基础知识(待扩展,但觉得只要做USACO就可以掌握)
2.搜索(我们全队都太弱了,一定要加强)
   -N重循环
   -BFS
      =双向
      =判重
         +HASH(尤其是字符串HASH)
         +分段HASH
         +各种数据结构判重(Tire数、平衡树等)
      =A*
   -DFS
      =各种剪枝
   -ID-DFS
   -ID-A*
   -DLX
   -近似算法及其他
      =模拟退火
      =遗传算法
      =随机调整
      =随机贪心
3.DP(主要是自己做题总结,感悟+数学能力)
4.字符串操作
   -c++的string
   -KMP
   -ExKMP
   -最小表示法   
   -Tire树
   -AC自动机
   -后缀数组
   -后缀树(好像被淘汰了)
   -后缀自动机【这个可以忽略】
5.数据结构
   -链表
      =普通链表
      =跳跃表
      =Dancing links
   -队列
      =普通队列
      =循环队列
      =单调队列
   -栈
      =手工栈搜索
      =表达式处理
   -堆
      =哈夫曼树
      =可合并堆
         +左偏树
         +斜堆
         +二项堆
   -并查集
   -树状数组
   -线段树(重点推荐)
   -平衡树
      =红黑树(知道理论+会用set和map)
      =AVL
      =Treap
      =超快SBT(重点推荐)
      =万能Splay(重点推荐)
   -块状链表
   -树链剖分(我也不知道)
6.图论与树
   -图的联通性
      =floodfill
      =BFS分层
      =两次BFS求强连通分量
      =拓扑排序
      =关键路径
      =求环
      =欧拉回路
      =汉密尔顿回路
      =Tarjan算法
         +求强连通分量
         +求割点
         +求桥
   -最短路
      =floyd
      =dijstra
      =SPFA
      =dijstra+heap
      =Bellman-ford求差分约束系统
      =floyd*求最小环
      =K短路
      =限制条件最短路
      =分层图最短路
      =状态压缩最短路
   -生成树
      =prim
      =Kruskal
      =prim+heap
      =破环法求最小生成树
      =动态最小生成树
      =次小生成树
      =最大价值比生成树
      =特殊生成树
      =统计生成树的个数(组合数学)
   -树上问题
      -LCA和RMQ
      -节点到根的距离
      -树的直径
      -树的中心
      -任意点对间距离
   - 2-SAT问题
7.网络流(我总结在了第三本笔记本)
   -二分图
      =匈牙利算法
      =KM算法
      =覆盖集与独立集
      =最小路径覆盖
   -最大流
      =DINIC
      =SAP   
      =HLLP
      =有上下界的最大流
   -最小割   
      =求当前流的最小割
      =平面图最小割转最短路
      =闭合图
      =最小点权覆盖集与最大独立点权集
      =0/1分数规划
      =最大密度子图
   -费用流   
      =最短路增广费用流
      =zkw-费用流最小费用可行流
   -构图技巧(请学习网络流24题,作者:郭家宝)
8.数论(我总结在了最终笔记本)
   -gcd
      =stein算法
      =欧几里得算法
      =拓展欧几里得算法
   -质数
      =MR测试
      =快速幂
      =sqrt(n)判定
      =反质数
      =算数基本定理及推论
   -同余
      =威尔逊定理
      =费马小定理
      =欧拉定理
      =中国剩余定理
   -进制相关
      =精制转换=高精循环小数
      =Self-number
   -其他
      =px+qy命题
      =求n!位数的方法及推广
      =P^xTm!的应用
9.组合数学(还未学习)
10.计算几何(还未学习)
11.博弈论(还未学习)
12.概率论(还未学习)
13.高等数学与线性代数(正在学习)

二。练习题
NOIP:
   -USACO-C1~C4(我AC了)
   -大部分NOIP真题
省选:
   -所有NOIP真题(我差一点)
   -部分NOI真题(基本没有做)
   -USACO-C5~C6(我AC了)
   -SGU能做多少做多少(我还没做)
更高更妙:(完全非我所及,但你们会超过我的)
   -USACO上的各种比赛
   - www.topcoder.com/tc
   - www.codeforces.com
   说明:http://hi.baidu.com/buaa_babt/blog/item/522fb239ef912cdc7d1e71b5.html

三。推荐书目(我买了好多书放在二中)

四。资料(还未整理) 

posted on 2012-05-31 17:25 zyn.cpp 阅读(795) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年5月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜