《信息学竞赛讲义.ppt》由会员分享，可在线阅读，更多相关《信息学竞赛讲义.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息学竞赛讲义信息学竞赛活动介绍 国内比赛以及活动nNOIPnNOIn 冬令营nCTSCn以及各省丰富多彩的培训活动信息学竞赛活动介绍 国际比赛以及活动nIOInCEOInBOInPOInIPSCn常用竞赛网站介绍nNOI官方网站 :nOIBH论坛 :www.oibh.orgn大榕树论坛 :www.mydrs.orgnFLYMouse的空间: :n交流平台 :QQ！常用竞赛题库介绍nUSACO :http:/ :http:/ :http:/ :http:/acm.timus.ru/nPku :http:/ :http:/ :http:/www.spoj.pl/nMIPT:http:/acm.m
2、ipt.ru/经典书籍介绍n信息学奥林匹克提高篇 吕品 北京大学出版社n全国青少年信息学奥林匹克联赛 南京大学出版社 n数据结构 严蔚敏 清华大学出版社n算法与数据结构 电子工业出版社 经典书籍介绍n信息学奥林匹克竞赛指导系列丛书 吴文虎 清华大学出版社n算法艺术与信息学竞赛 刘汝佳 清华大学出版社n算法艺术与信息学竞赛学习指导 清华大学出版社 （未出版-_-!）经典书籍介绍n金牌之路 王建德 陕西师范大学出版社n实用算法的分析与程序设计n算法导论信息学竞赛知识结构n语言：Pascal 或 C+n基本算法n数据结构n搜索n动态规划n数学n图论n计算几何信息学竞赛知识结构 语言n学会分析时间空间
3、复杂度n编成风格规范，速度快n编译开关n文件操作n位操作n静态差错能力n节省时间空间的小技巧信息学竞赛知识结构 数据结构n堆栈(LIFO)n数组实现n指针实现n掌握其特点及简单的应用：如辅助搜索，双堆栈进行四则运算等信息学竞赛知识结构 数据结构n队列(FIFO)n数组实现n指针实现（包括双向队列和循环队列）n了解其特点和应用：如其扩展“块状链表”，BFS的节点扩展，拓扑排序实现时的应用，以及动态规划中的队列优化等。信息学竞赛知识结构 数据结构nHash表n了解Hash表的实现n重点掌握解决冲突的两种方法：开散列，闭散列。通过Hash的开散列实现，熟悉对指针的掌握nHash函数的设计nHash的
4、应用：各种各样的判重，以及kmp变形算法的应用信息学竞赛知识结构 数据结构n字符串n熟练掌握Pascal语言中关于字符串的所有函数和相应的操作n掌握匹配算法：模式匹配、KMPn掌握一些特殊的变形：Tire树、Tire图、KMP扩展算法、最小表示法、单词前缀树，单词后缀树，后缀数组。信息学竞赛知识结构 数据结构n树(Tree)n树的定义、结构、特点。笔试考查点n树的实现：父亲数组（如堆）儿子链表实现 左儿子右兄弟表示法nLCA问题 ：朴素算法，Tarjan算法nRMQ问题：ST算法 信息学竞赛知识结构 数据结构n二叉树(BST)n掌握二叉树的普通实现n平衡二叉树的各种实现：AVL、红黑树、Spl
5、ay、Treap以及skiplist。n了解排序二叉树的应用信息学竞赛知识结构 数据结构n并查集n掌握其父亲表示法的实现n两种优化：rank值启发合并以及路径压缩n了解其时间复杂度n熟练其应用：比如Kruskal算法的实现以及一些特殊的应用信息学竞赛知识结构 数据结构n优先队列n二叉堆及其数组实现n可并优先队列：左偏树的应用n二项堆（了解）信息学竞赛知识结构 数据结构n线段树n树状数组n块状链表n信息学竞赛知识结构 数据结构n排序算法n快速排序：一定要熟练掌握，当n小于等于20时用普通排序较快。n选择排序、冒泡排序、插入排序n桶排序、基数排序信息学竞赛知识结构 基本算法n枚举n贪心n递归和分治
6、n回溯n二分答案n随机化贪心、随机化调整信息学竞赛知识结构 搜索n深度优先搜索(DFS)n了解其与堆栈的关系n剪枝优化n搜索顺序n跌代加深搜索，如：埃及分数n注意其拓展：博弈问题信息学竞赛知识结构 搜索n广度优先搜索(BFS)n判重：1985年国内一名研究生证明了针对BFS的判重只需与上三层进行。n双向搜索n估价函数信息学竞赛知识结构 数学n数论n素数相关：素数的判定，筛选法，Miller-Rabbin测试n整除和约数：欧几里德辗转相除法及其扩展，因数分解。n带余除法的四则运算信息学竞赛知识结构 数学n进位制：快速幂取模，求ab mod cn费马小定理n欧拉函数n求一个数的约数个数及约数和n高
7、斯消元求解方程n求解线性同余方程 ax=b(mod n)信息学竞赛知识结构 数学n组合数学n基本的排列组合n容斥原理n棋盘多项式(了解)n置换群(了解)n常见递推关系和组合数：Fibonacci、Catalan、第一类Stirling数、第二类Stirling数n置换群信息学竞赛知识结构 图论n基本概念和定理n连通性：点连通性，边连通性n割顶、桥等信息学竞赛知识结构 图论n最短路径n掌握其不同的实现方式：dijkstra、bellman-ford、SPFA(SSSP)，Floyd-warshall(APSP)n熟悉各种不同算法的时空复杂度和使用范围n了解一些经典例题和其变形信息学竞赛知识结构 图论n最小生成树n掌握两种实现：Prim，Kruskaln掌握其变形：K小生成树，最小度限制生成树n掌握其经典应用：参见吴景岳的论文信息学竞赛知识结构 图论n网络流n掌握其两种实现n最小切割最大流定理n最小费用最大流n有上下界的最大最小流n多联系建模思想，掌握其广泛的应用，例如混合图的欧拉回路信息学竞赛知识结构 图论n可行性遍历问题n哈密尔顿回路n欧拉回路n中国邮递员问题n信息学竞赛知识结构 图论n求割顶和块n求极大强连通子图n拓扑排序和关键路径