acm程序设计竞赛例题

《acm程序设计竞赛例题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、备战ACM资料一：知识点数据结构：1，单，双链表及循环链表2，树的表示与存储，二叉树（概念，遍历）二叉树的应用（二叉排序树，判定树，博弈树，解答树等）3，文件操作（从文本文件中读入数据并输出到文本文件中）4，图（基本概念，存储结构，图的运算）数学知识1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑）2，数论知识3，线性代数4，组合代数5，计算几何二算法1，排序算法（冒抛法，插入排序，合并排序，快速排序，堆排序）2，查找（顺序查找，二分发）3，回溯算法4，递归算法5，分治算法6，模拟法7，贪心法8，

2、简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法9，动态规划的思想及基本算法10，高精度运算三、ACM竞赛的题型分析竞赛的程序设计一般只有16种类型，它们分别是：DynamicProgramming（动态规划）Greedy（贪心算法）CompleteSearch（穷举搜索）FloodFill（不知该如何翻译）ShortestPath（最短路径）RecursiveSearchTechniques（回溯搜索技术）MinimumSpanningTree（最小生成树）Knapsack（背包问题）Comp

3、utationalGeometry(计算几何学)NetworkFlow（网络流）EulerianPath（欧拉回路）Two-DimensionalConvexHull（不知如何翻译）BigNums（大数问题）HeuristicSearch（启发式搜索）ApproximateSearch（近似搜索）AdHocProblems（杂题）四ACM竞赛参考书《实用算法的分析与程序设计》（吴文虎，王建德著，电子工业出版社，竞赛类的黑宝书）《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法和程序设计

4、》（吴文虎，王建德著，清华大学出版社，参加竞赛组合数学必学）《计算机算法设计与分析》（王晓东编著，最好的数据结构教材）《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材）《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德著，清华大学出版社）《计算机程序设计技巧》D.E.Kruth著，算法书中最著名的《葵花宝典》，大师的作品，难度大）《计算几何》周陪德著《ACM国际大学生程序设计竞赛试题与解析（一）》（吴文虎著，清华大学出版社）《数学建模竞赛培训教材》共三本叶其孝主编

5、《数学模型》第二版姜启源《随机规划》《模糊数学》《数学建模入门》徐全智《计算机算法设计与分析》国防科大五常见的几个网上题库常用网站：1）信息学初学者之家：http://oibh.ioiforum.org/（2）大榕树编程世界：http://www.fjsdfz.org/~drs/program/default.asp（3）中国教育曙光网：http://www.chinaschool.org/aosai/（4）福建信息学奥林匹克：http://www.cfcs.com.cn/fjas/index.htm（5

6、）第20届全国青少年信息学奥林匹克竞赛：http://www.noi2003.org/（6）第15届国际青少年信息学奥林匹克竞赛：http://www.ioi2003.org/（7）全美计算机奥林匹克竞赛：http://ace.delos.com/usacogate（8）美国信息学奥林匹克竞赛官方网站：http://www.usaco.org/（9）俄罗斯Ural州立大学：http://acm.timus.ru/（10）西班牙Valladolid大学：http://acm.uva.es/problemse

7、t（11）ACM-ICPC：http://icpc.baylor.edu/icpc/（12）北京大学：http://acm.pku.edu.cn/JudgeOnline/index.acm（13）浙江大学：http://acm.zju.edu.cn/（14）IOI：http://olympiads.win.tue.nl/ioi/（15）2003年江苏省信息学奥林匹克竞赛夏令营：http://jsoi.czyz.com.cn（16）http://acm.zju.edu.cn（17）http://acm.zs

8、u.edu.cn（18）www.shumo.com（19）http://www.bepark.com/downldmanag/index.asp（20）http://www.yh01.comcolin_fox/colin_fox五如何备战ACM/ICPC1，个人准备（算法书，习题集，网上做题和讨论）2，1000题=亚洲冠军=世界决赛3，做好资料收集和整理工作实验一：递归与分治1.二分查找2.合并排序3.快速排序实验二：回溯1.