新编实用算法分析与程序设计竞赛

Ⅰ 参加ACM竞赛需要用的参考书

ACM国际大学生程序设计竞赛：知识与入门.pdf

链接: https://pan..com/s/19OY2FJUkk4RhW5WTsPkwfQ

《ACM国际大学生程序设计竞赛:知识与入门》适用于参加ACM国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。

Ⅱ 程序设计，软件设计方面，比较有名的竞赛有哪些除了ACM，百度之星。。。。

除了网络之星、有道难题，还有Google的GoogleJam。
以上这些都是算法竞赛，需要长期的训练。

另外，国内还有一些类似“全国大学生信息安全竞赛”、“全国大学生电子设计竞赛”新增的“信息安全技术专题邀请赛”等竞赛，还有“数学建模竞赛”的省赛、全国赛、美赛等等。

以上都是只有证书，获得三等奖及以上的话，学校一般都会给奖金。

还有一些企业，会在一些学校举办一些比赛，例如“中兴杯校园程序设计大赛”（南京地区所有高校，奖金很高，获奖直接签中兴的三方）、“华为杯程序设计大赛”（校级比赛，奖金很高，前三等奖免初试的笔试面试）等等。

希望我的回答对你有帮助！

加油哈！

多多积累专业知识和本领，为班级、学校、国家，争取荣誉，祝你好运！

Ⅲ ACM 关于ACM程序设计竞赛，需要掌握哪些知识点，最好能详细一点，谢谢高手们了。

训练过ACM等程序设计竞赛的人在算法上有较大的优势，这就说明当你编程能力提高之后，主要时间是花在思考算法上，不是花在写程序与debug上。
下面给个计划你练练：

第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来。

1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成树(先写个prim,kruscal要用并查集，不好写)
3.大数（高精度）加减乘除
4.二分查找. (代码可在五行以内)
5.叉乘、判线段相交、然后写个凸包.
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.
8. 调用系统的qsort, 技巧很多，慢慢掌握.
9. 任意进制间的转换

第二阶段：练习复杂一点，但也较常用的算法。
如：
1. 二分图匹配（匈牙利），最小路径覆盖
2. 网络流，最小费用流。
3. 线段树.
4. 并查集。
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp
6.博弈类算法。博弈树，二进制法等。
7.最大团，最大独立集。
8.判断点在多边形内。
9. 差分约束系统.
10. 双向广度搜索、A*算法，最小耗散优先.

第三阶段：
前两个阶段是打基础，第三阶段是锻炼在比赛中可以快速建立模型、想新算法。这就要平时多做做综合的题型了。
1. 把oibh上的论文看看（大概几百篇的，我只看了一点点，呵呵）。
2. 平时扫扫zoj上的难题啦，别老做那些不用想的题.(中大acm的版主经常说我挑简单的来做:-P )
3. 多参加网上的比赛，感受一下比赛的气氛，评估自己的实力.
4. 一道题不要过了就算，问一下人，有更好的算法也打一下。
5. 做过的题要记好 :-)
下面转自：http://hi..com/wilworld/blog/item/88b1b844d37e4049500ffe6a.html
ACMer必备知识（任重而道远......）

图论

路径问题
0/1边权最短路径
BFS
非负边权最短路径（Dijkstra）
可以用Dijkstra解决问题的特征
负边权最短路径
Bellman-Ford
Bellman-Ford的Yen-氏优化
差分约束系统
Floyd
广义路径问题
传递闭包
极小极大距离 / 极大极小距离
Euler Path / Tour
圈套圈算法
混合图的 Euler Path / Tour
Hamilton Path / Tour
特殊图的Hamilton Path / Tour 构造

生成树问题
最小生成树
第k小生成树
最优比率生成树
0/1分数规划
度限制生成树

连通性问题
强大的DFS算法
无向图连通性
割点
割边
二连通分支
有向图连通性
强连通分支
2-SAT
最小点基

有向无环图
拓扑排序
有向无环图与动态规划的关系

二分图匹配问题
一般图问题与二分图问题的转换思路
最大匹配
有向图的最小路径覆盖
0 / 1矩阵的最小覆盖
完备匹配
最优匹配
稳定婚姻

网络流问题
网络流模型的简单特征和与线性规划的关系
最大流最小割定理
最大流问题
有上下界的最大流问题
循环流
最小费用最大流 / 最大费用最大流

弦图的性质和判定

组合数学

解决组合数学问题时常用的思想
逼近
递推 / 动态规划
概率问题
Polya定理

计算几何 / 解析几何

计算几何的核心：叉积 / 面积
解析几何的主力：复数

基本形
点
直线，线段
多边形

凸多边形 / 凸包
凸包算法的引进，卷包裹法

Graham扫描法
水平序的引进，共线凸包的补丁

完美凸包算法

相关判定
两直线相交
两线段相交
点在任意多边形内的判定
点在凸多边形内的判定

经典问题
最小外接圆
近似O(n)的最小外接圆算法
点集直径
旋转卡壳，对踵点
多边形的三角剖分

数学 / 数论

最大公约数
Euclid算法
扩展的Euclid算法
同余方程 / 二元一次不定方程
同余方程组

线性方程组
高斯消元法
解mod 2域上的线性方程组
整系数方程组的精确解法

矩阵
行列式的计算
利用矩阵乘法快速计算递推关系

分数
分数树
连分数逼近

数论计算
求N的约数个数
求phi(N)
求约数和
快速数论变换
……

素数问题
概率判素算法
概率因子分解

数据结构

组织结构
二叉堆
左偏树
二项树
胜者树
跳跃表
样式图标
斜堆
reap

统计结构
树状数组
虚二叉树
线段树
矩形面积并
圆形面积并

关系结构
Hash表
并查集
路径压缩思想的应用

STL中的数据结构
vector
deque
set / map

动态规划 / 记忆化搜索

动态规划和记忆化搜索在思考方式上的区别

最长子序列系列问题
最长不下降子序列
最长公共子序列
最长公共不下降子序列

一类NP问题的动态规划解法

树型动态规划

背包问题

动态规划的优化
四边形不等式
函数的凸凹性
状态设计
规划方向

线性规划

常用思想

二分
最小表示法

串

KMP
Trie结构
后缀树/后缀数组
LCA/RMQ
有限状态自动机理论

排序
选择/冒泡
快速排序
堆排序
归并排序
基数排序
拓扑排序
排序网络

Ⅳ 参加程序设计竞赛应该看哪些书

新编实用算法分析与程序设计(计算机程序设计竞赛权威指导书)

Ⅳ 小学生计算机程序设计竞赛活动

一、指导思想和目标
1、掌据计算机软件、硬件基本常识;
2、计算机信息存储的基本原理;
3、计算机程序设计相关数学知识及应用;
4、程序设计语言、程序设计三种基本结构;
5、分析和解决问题的基本思维方法;
6、排序、查找、归并算法的实现;
7、枚举、递推、归纳、模拟、贪心算法在程序设计中的应用。
二、竞赛的形式和内容范围
竞赛分初赛和决赛两轮进行，初赛全市统一试题、统一时间，由各镇区组织实施，目的是选出各镇区参加市决赛的选手;决赛由市教育局教研室组织实施。初赛和决赛为笔试，题型包括：一、选择题；二、填空题；三、写程序结果；四、完善程序。
三、初赛的知识范围
(一)、 计算机基本常识：(10%)
1、计算机硬件基础知识
计算机的组成、中央处理器、存储器、输入输出设备、计算机网络等方面常识。
2、计算机软件基本知识
常用软件的使用、分类，计算机网络的简单知识等。
3、相信编码有关知识ASCII码、位、字节的概念，二进制、十进制之间的转换等。
(二)、与程序设计相关的数学知识：(15%)
（1）、二进制、十进制之间的转换等；
（2）、逻辑判断问题；
（3）、加法原理、乘法原理的应用；
（4）、简单的排列、组合；
(三)、pascal程序设计：(75%)
1、基本数据类型。
整型、实型、字符型、字符串型、长整型、布尔型。
2、基本运算。
算术运算：加、减、乘、除、乘方、开平方、整除、求余；
关系运算：>、<、>=、<=、<>(不等于)；
逻辑运算：AND、OR、NOT。
3、常用语句的使用。
const var begin end read(readln) write(writeln) if...then case；
.. .for...do repeat...until while...do。
4、常用内部函数、过程的使用。
(1)、算术函数。
abs int odd ord pred succ random(random(n) ) round trunc sqrt
(2)、字符串函数。
length chr pos upcase
(3)、字符串处理过程的使用。
delete insert str val
5、一维、二维数组的定义和应用。
6、程序设计的基本方法：
（1）、最大公约数、最小公倍数的求法；
（2）、质数、分解质因数的方法；
(3）、数字的拆分方法；
(4)、简单的排序算法：如冒泡法、插入法；
(5)、数据的查找算法：顺序查找、二分查找；
(6)、数据的归并算法；
(7)、枚举算法；
(8)、归纳、递推算法；
(9)、字符串处理有关问题；
(10)、高精度加、减运算算法；
(11)、简单的贪心算法。
注：Basic程序设计初赛的知识范围与往年要求一样。

Ⅵ 第三届全国大学生算法设计与编程挑战赛的难度大不大

如果你有天赋又肯努力的话，不难。
全国大学生算法设计与编程挑战赛，是由中国未来研究会大数据与数学模型专业委员会举办的面向全国高校大学生的学科竞赛。
大赛旨在激发学生学习计算机领域专业知识与技能的兴趣，鼓励学生主动灵活地运用计算机知识和技能解决实际问题，有效提升算法设计、逻辑推理、数学建模、编程实现和计算机系统能力，培养团队合作意识、挑战精神和创新能力。

Ⅶ 算法设计比赛做什么算法好

应该是ACM吧
就是给你8-10道算法题目，5个小时，做出来多的题目数越多，排名越靠前，如果题目数一样多的看用的时间。
时间的计算方法如下：
例如你A题用了20分钟AC，然后B题有用了30分钟AC（此时是比赛开始50分钟），又用了30分钟AC了C题，那么你的时间（penalty ）是
20 + 50 + 80 = 150分钟

比赛中常用的算法有
1。动态规划
2。搜索
3。贪心
4。图论
5。组合数学
6。计算几何
7。数论
等

推荐到
http://acm.pku.e.cn
http://acm.zju.e.cn
http://acm.h.e.cn
http://acm.timus.ru
这几个OJ上练习

比较好的题目分类（POJ上的）
1。这个是我最喜欢的
初期:
一.基本算法:
(1)枚举. (poj1753,poj2965)(2008-10-27Done 位运算+宽搜)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(2008-08-29Done)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)(2008-09-01Done)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)(2008-09-02Done)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)(2008-10-23Done 并查集、欧拉)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)(2008-08-29Done)
中级:
一.基本算法:
(1)C++的标准模版库的应用. (poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
(1)差分约束系统的建立和求解. (poj1201,poj2983)(2008-09-05Done)
(2)最小费用最大流(poj2516,poj2516,poj2195)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点.(poj2186)
(5)图的割边和割点(poj3352)
(6)最小割模型、网络流规约(poj3308, )
三.数据结构.
(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)静态二叉检索树. (poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高级应用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)(2008-09-16Done)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化 (poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)

五.动态规划
(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
(1)组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.

(2)数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)随机化算法(poj3318,poj2454)
(5)杂题.
(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
(1)坐标离散化.
(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多边形的内核(半平面交)(poj3130,poj3335)
(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高级:
一.基本算法要求:
(1)代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保证正确性和高效性. poj3434
二.图算法:
(1)度限制最小生成树和第K最短路. (poj1639)
(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最优比率生成树. (poj2728)
(4)最小树形图(poj3164)
(5)次小生成树.
(6)无向图、有向图的最小环
三.数据结构.
(1)trie图的建立和应用. (poj2778)(2008-10-26Done 矩阵A^n)
(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
(RMQ+dfs)).(poj1330)
(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
目的). (poj2823)
(4)左偏树(可合并堆).
(5)后缀树(非常有用的数据结构,也是赛区考题的热点).
(poj3415,poj3294)
四.搜索
(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
(1)需要用数据结构优化的动态规划.
(poj2754,poj3378,poj3017)
(2)四边形不等式理论.
(3)较难的状态DP(poj3133)
六.数学
(1)组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
(2)博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
(1)半平面求交(poj3384,poj2540)
(2)可视图的建立(poj2966)
(3)点集最小圆覆盖.
(4)对踵点(poj2079)
八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

2。这个每个分类的题目比较多，适合作为第一个分类的扩展
说明：递推算动归， 离散化算数据结构， 并查集算数据结构， 博弈算动归， 麻烦题一般都是不错的综合题， 最短路算图论，数据的有序化算排序
麻烦题：1697, 1712, 1713, 1720, 1729, 1765, 1772, 1858, 1872, 1960, 1963, 2050, 2122, 2162, 2219, 2237,
简单题目：1000, 1003, 1004, 1005, 1007, 1046, 1207, 1226, 1401, 1504, 1552, 1607, 1657, 1658, 1674, 1799, 1862, 1906, 1922, 1929, 1931, 1969, 1976, 2000, 2005, 2017, 2027, 2070, 2101, 2105, 2109, 2116, 2136, 2160, 2190, 2232, 2234, 2275, 2301, 2350, 2363, 2389, 2393, 2413, 2419, 推荐：1063, 1064, 1131, 1140, 1715, 2163,
杂题：1014, 1218, 1316, 1455, 1517, 1547, 1580, 1604, 1663, 1678, 1749, 1804, 2013, 2014, 2056, 2059, 2100, 2188, 2189, 2218, 2229, 2249, 2290, 2302, 2304, 2309, 2313, 2316, 2323, 2326, 2368, 2369, 2371, 2402, 2405, 2407, 推荐：1146, 1147, 1148, 1171, 1389, 1433, 1468, 1519, 1631, 1646, 1672, 1681, 1700, 1701, 1705, 1728, 1735, 1736, 1752, 1754, 1755, 1769, 1781, 1787, 1796, 1797, 1833, 1844, 1882, 1933, 1941, 1978, 2128, 2166, 2328, 2383, 2420,
高精度：1001, 1220, 1405, 1503,
排序：1002, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 2388, 2418, 推荐：1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,
搜索容易：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349, 推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,
数据结构容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395, 不易：1145, 1177, 1195, 1227, 1661, 1834, 推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119, 2274,
动态规划容易：1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926, 1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, 2033, 2063, 2081, 2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424, 不易：1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733, 1737, 1837, 1850, 1920, 1934, 1937, 1964, 2039, 2138, 2151, 2161, 2178, 推荐：1015, 1635, 1636, 1671, 1682, 1692, 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411,
字符串：1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896, 1951, 2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408,
贪心：1042, 1065, 1230, 1323, 1477, 1716, 1784,
图论容易：1161, 1164, 1258, 1175, 1308, 1364, 1776, 1789, 1861, 1939, 1940, 1943, 2075, 2139, 2387, 2394, 2421, 不易：1041, 1062, 1158, 1172, 1201, 1275, 1718, 1734, 1751, 1904, 1932, 2173, 2175, 2296, 网络流：1087, 1273, 1698, 1815, 2195, 匹配：1274, 1422, 1469, 1719, 2060, 2239, Euler：1237, 1637, 1394, 2230, 推荐：2049, 2186,
计算几何容易：1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318, 不易：1685, 1687, 1696, 1873, 1901, 2172, 2333, 凸包：1113, 1228, 1794, 2007, 2187,
模拟容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791, 1835, 1970, 2317, 2325, 2390, 不易：1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,
数学容易：1061, 1091, 1142, 1289, 1305, 1306, 1320, 1565, 1665, 1666, 1730, 1894, 1914, 2006, 2042, 2142, 2158, 2174, 2262, 2305, 2321, 2348, 不易：1067, 1183, 1430, 1759, 1868, 1942, 2167, 2171, 2327, 推荐：1423, 1450, 1640, 1702, 1710, 1721, 1761, 1830, 1930, 2140,

Ⅷ acm必备知识都有哪些

备战ACM资料
一：知识点
数据结构：
1，单，双链表及循环链表
2，树的表示与存储，二叉树（概念，遍历）二叉树的
应用（二叉排序树，判定树，博弈树，解答树等）
3，文件操作（从文本文件中读入数据并输出到文本文
件中）
4，图（基本概念，存储结构，图的运算）
数学知识
1，离散数学知识的应用（如排列组合、简单的图论，数
理逻辑）
2，数论知识
3，线性代数
4，组合代数
5，计算几何
二 算法
1，排序算法（冒抛法，插入排序，合并排序，快速排
序，堆排序）
2，查找（顺序查找，二分发）
3，回溯算法
4，递归算法
5，分治算法
6，模拟法
7，贪心法
8，简单搜索算法（深度优先，广度优先），搜索中的
剪枝，A*算法
9，动态规划的思想及基本算法
10，高精度运算
三、ACM竞赛的题型分析
竞赛的程序设计一般只有16种类型，它们分别是：
Dynamic Programming （动态规划）
Greedy （贪心算法）
Complete Search （穷举搜索）
Flood Fill （不知该如何翻译）
Shortest Path （最短路径）
Recursive Search Techniques （回溯搜索技术）
Minimum Spanning Tree （最小生成树）
Knapsack （背包问题）
Computational Geometry (计算几何学)
Network Flow （网络流）
Eulerian Path （欧拉回路）
Two-Dimensional Convex Hull （不知如何翻译）
BigNums （大数问题）
Heuristic Search （启发式搜索）
Approximate Search （近似搜索）
Ad Hoc Problems （杂题）
四 ACM竞赛参考书
《实用算法的分析与程序设计》 （吴文虎，王建德着，电子工业出版社，竞赛类的黑宝书）
《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法
和程序设计》（吴文虎，王建德着，清华大学出版社，参加竞赛组合数学必学）
《计算机算法设计与分析》 （王晓东编着，最好的数据结构教材）
《数据结构与算法》 （傅清祥，王晓东编着，我所见过的最好的算法教材）
《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德着，清华大学出版社）
《计算机程序设计技巧》 D.E.Kruth着，算法书中最着名的《葵花宝典》，大师的作品，难度大）
《计算几何》周陪德着
《ACM国际大学生程序设计竞赛试题与解析（一）》 （吴文虎着，清华大学出版社）
《数学建模竞赛培训教材》 共三本 叶其孝主编
《数学模型》 第二版 姜启源
《随机规划》
《模糊数学》
《数学建模入门》 徐全智
《计算机算法设计与分析》 国防科大
五 常见的几个网上题库
常用网站：
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）第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/problemset
（11）ACM-ICPC：http://icpc.baylor.e/icpc/
（12）北京大学：http://acm.pku.e.cn/JudgeOnline/index.acm
（13）浙江大学：http://acm.zju.e.cn/
（14）IOI：http://olympiads.win.tue.nl/ioi/
（15）2003年江苏省信息学奥林匹克竞赛夏令营：http://jsoi.czyz.com.cn
（16）http://acm.zju.e.cn
（17）http://acm.zsu.e.cn
（18）www.shumo.com
（19）http://www.bepark.com/downldmanag/index.asp
（20）http://www.yh01.com colin_fox/colin_fox
五 如何备战ACM/ICPC
1，个人准备（算法书，习题集，网上做题和讨论）
2，1000题=亚洲冠军=世界决赛
3，做好资料收集和整理工作

Ⅸ acm初学者要准备什么 看什么书啊

刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。
一、语言是最重要的基本功

无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。

接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。

而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。

C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。

通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的掌握并不要求十分全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方，下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍，都有可能酿成错误：

在去年清华的赛区上，有一个队在做F题的时候使用了cout和printf的混合输出，由于一个带缓冲一个不带，所以输出一长就混乱了。只是因为当时judge team中负责F题的人眼睛尖，看出答案没错只是顺序不对（答案有一页多，是所有题目中最长的一个输出），又看了看程序发现只是输出问题就给了个Presentation error（格式错）。如果审题的人不是这样而是直接给一个 Wrong Answer，相信这个队是很难查到自己错在什么地方的。

现在我们转入第二个方面的讨论，基础学科知识的积累。

二、以数学为主的基础知识十分重要

虽然被定性为程序设计竞赛，但是参赛选手所遇到的问题更多的是没有解决问题的思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。今年World Final的总冠军是波兰华沙大学，其成员出自于数学系而非计算机系，这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学，此外对于物理、电路等等也可能有一定应用，但是不多。因此，大一的同学也不必为自己还没学数据结构而感到不知从何入手提高，把数学捡起来吧！下面我来谈谈在竞赛中应用的数学的主要分支。

1、离散数学——作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。

图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大，但是往往也是竞赛中的难题所在，如果有初学者对于这部分的某些具体内容暂时感到力不从心，也不必着急，可以慢慢积累。

竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于图论要简单一些，很多知识对于小学上过奥校的同学来说已经十分熟悉，但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为难题。

2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定大概的过程之后，核心算法往往要涉及数论的内容。

3、计算几何——计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。

4、线性代数——对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。

5、概率论——竞赛是以黑箱来判卷的，这就是说你几乎不能动使用概率算法的念头，但这也并不是说概率就没有用。关于这一点，只有通过一定的练习才能体会。

6、初等数学与解析几何——这主要就是中学的知识了，用的不多，但是至少比高等数学多，我觉得熟悉一下数学手册上的相关内容，至少要知道在哪儿能查到，还是必要的。

7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道，但是一些题目的叙述背景往往需要和这部分有一定联系，掌握得牢固一些总归没有坏处。

以上就是竞赛所涉及的数学领域，可以说范围是相当广的。我认识的许多人去搞信息学的竞赛就是为了逼着自己多学一点数学，因为数学是一切一切的基础。

三、数据结构与算法是真正的核心

虽然数学十分十分重要，但是如果让三个只会数学的人参加比赛，我相信多数情况下会比三个只会数据结构与算法的人得到更为悲惨的结局。

先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的，至于树，我个人觉得需要建树的问题有但是并不多。（但是树往往是很重要的分析工具）除此之外，排序和查找并不需要对所有方式都能很熟练的掌握，但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度，就又该说说哈希表了，竞赛时对时间的限制远远多于对空间的限制，这要求大家尽快掌握“以空间换时间”的原则策略，能用哈希表来存储的数据一定不要到时候再去查找，如果实在不能建哈希表，再看看能否建二叉查找树等等——这都是争取时间的策略，掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。

接着说说算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。

常用算法中的另一类是以“相似或相同子问题”为核心的，包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划，如何抽象出重复的子问题是很多题目的难点所在，笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法（比如Floyd-Warshall算法），并且多阅读一些定理的证明，这虽然不能有什么直接的帮助，但是长期坚持就会对思维很有帮助。

四、团队配合

通过以上的介绍大家也可以看出，信息学竞赛对于知识面覆盖的非常广，想凭一己之力全部消化这些东西实在是相当困难的，这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间，具体的情况因成员的组成不同而不同，这里我就不再多说了。

五、练习、练习、再练习

知识的积累固然重要，但是信息学终究不是看出来的，而是练出来的，这是多少前人最深的一点体会，只有通过具体题目的分析和实践，才能真正掌握数学的使用和算法的应用，并在不断的练习中增加编程经验和技巧，提高对时间复杂度的感性认识，优化时间的分配，加强团队的配合。总之，在这里光有纸上谈兵是绝对不行的，必须要通过实战来锻炼自己。

大家一定要问，我们去哪里找题做，又如何检验程序是否正确呢？这大可不必担心，现在已经有了很多网上做题的站点，这些站点提供了大量的题库并支持在线判卷，你只需要把程序源码提交上去，马上就可以知道自己的程序是否正确，运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点，笔者不建议大家在所有这些站点上做题，选择一个就可以了，因为每个站点的题都有一定的难易比例，系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。

1、Ural：

Ural是中国学生对俄罗斯的Ural州立大学的简称 ，那里设立了一个Ural Online Problem Set，并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强，得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计，Ural的题目类型大概呈如下的分布：

题型
搜索
动态规划
贪心
构造
图论
计算几何
纯数学问题
数据结构
其它

所占比例
约10%
约15%
约5%
约5%
约10%
约5%
约20%
约5%
约25%

这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。

2、UVA：

UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ，并且支持ONLINE JUDGE，形式和Ural大学的题库类似。不过和Ural不同的是，UVA题目多的多，而且比较杂，而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从，要么难以找到合适的题目，要么Wrong Answer了很多次以后仍然不知道错在那里。 如果说做Ural题目主要是为了训练算法，那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛，因此那里强人无数，不过你先要使自己具有听懂他们在说什么的素质：）

3、ZOJ：

ZOJ是浙江大学建立的ONLINE JUDGE，是中国大学建立的第一个同类站点，也是最好和人气最高的一个，笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站，但是这里的中国学生比较多，因此让人觉得很亲切。这里目前有500多道题目，难易分配适中，且涵盖了各大洲的题目类型并配有索引，除此之外，ZOJ的JUDGE系统是几个网站中表现得比较好的一个，很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛，只要是注册的用户都可以参加。

说起中国的ONLINE JUDGE，去年才开始参加ACM竞赛的北京大学现在也建立了自己的提交系统；而我们学校也是去年开始参加比赛，现在也有可能推出自己的提交系统，如果能够做成，到时候大家就可以去上面做题了。同类网站的飞速发展标志着有越来越多的同学有兴趣进入信息学的领域探索，这是一件好事，同时也意味着更激烈的竞争。

看看这篇文章对你有什么帮助！我也是ACM初学者！

Ⅹ 信息学如何备战省赛

一：知识点
数据结构：
1，单，双链表及循环链表
2，树的表示与存储，二叉树（概念，遍历）二叉树的
应用（二叉排序树，判定树，博弈树，解答树等）
3，文件操作（从文本文件中读入数据并输出到文本文
件中）
4，图（基本概念，存储结构，图的运算）
数学知识
1，离散数学知识的应用（如排列组合、简单的图论，数
理逻辑）
2，数论知识
3，线性代数
4，组合代数
5，计算几何
二 算法
1，排序算法（冒抛法，插入排序，合并排序，快速排
序，堆排序）
2，查找（顺序查找，二分发）
3，回溯算法
4，递归算法
5，分治算法
6，模拟法
7，贪心法
8，简单搜索算法（深度优先，广度优先），搜索中的
剪枝，A*算法
9，动态规划的思想及基本算法
10，高精度运算
三、ACM竞赛的题型分析
竞赛的程序设计一般只有16种类型，它们分别是：
Dynamic Programming （动态规划）
Greedy （贪心算法）
Complete Search （穷举搜索）
Flood Fill （不知该如何翻译）
Shortest Path （最短路径）
Recursive Search Techniques （回溯搜索技术）
Minimum Spanning Tree （最小生成树）
Knapsack （背包问题）
Computational Geometry (计算几何学)
Network Flow （网络流）
Eulerian Path （欧拉回路）
Two-Dimensional Convex Hull （不知如何翻译）
BigNums （大数问题）
Heuristic Search （启发式搜索）
Approximate Search （近似搜索）
Ad Hoc Problems （杂题）
四 ACM竞赛参考书
《实用算法的分析与程序设计》 （吴文虎，王建德着，电子工业出版社，竞赛类的黑宝书）
《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法
和程序设计》 （吴文虎，王建德着，清华大学出版社，参加竞赛组合数学必学）
《计算机算法设计与分析》 （王晓东编着，最好的数据结构教材）
《数据结构与算法》 （傅清祥，王晓东编着，我所见过的最好的算法教材）
《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德着，清华大学出版社，
内容极佳）
《计算机程序设计技巧》 D.E.Kruth着，算法书中最着名的《葵花宝典》，大师的作品，难度大）
《计算几何》 （周陪德着，全面介绍了计算几何）
《ACM国际大学生程序设计竞赛试题与解析（一）》 （吴文虎着，清华大学出版社）
数学建模竞赛培训教材 共三本 叶其孝主编
数学模型 第二版 姜启源
随机规划
模糊数学
数据结构
数学建模入门 徐全智
计算机算法设计与分析 国防科大
五 常见的几个网上题库
常用网站：
1）信息学初学者之家：
（2）大榕树编程世界：~drs/program/default.asp
（3）中国教育曙光网：
（4）福建信息学奥林匹克：
（5）第20届全国青少年信息学奥林匹克竞赛：
（6）第15届国际青少年信息学奥林匹克竞赛：
（7）全美计算机奥林匹克竞赛：
（8）美国信息学奥林匹克竞赛官方网站：
（9）俄罗斯Ural州立大学：
（10）西班牙Valladolid大学：
（11）ACM-ICPC：
（12）北京大学：
（13）浙江大学：
（14）IOI：
（15）2003年江苏省信息学奥林匹克竞赛夏令营：
（16）
（17）
（18）
（19）
（20） colin_fox/colin_fox