一、
ACM/ICPC
简介
ACM
国际大学生程序设计竞赛（
ACM/ICPC
：
ACM International Collegiate Programming Contest
）是由国际计算机界历史悠久、颇具权威性的组织
ACM(
美国计算机协会）学会（
Association for Computer Machineary
）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。该项竞赛从
1970
年举办至今已历
25
届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的
“
希望之星
”
，而受到国际各知名大学的重视，并受到全世界各著名计算机公司如
Microsoft(
微软公司
)
、
IBM
等的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事，
ACM
所颁发的获奖证书也为世界各著名计算机公司、各知名大学所认可。
该项竞赛是年度性竞赛，分区域预赛和国际决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的
3~4
月举行，而区域预赛安排在上一年的
9
月
~12
月在各大洲举行。从
1998
年开始，
IBM
公司连续
5
年独家赞助该项赛事的世界决赛和区域预赛。这项比赛是以大学为单位组队（每支队由教练、
3
名正式队员，一名后备队员组成）参赛，要求在
5
个小时内，解决
5~8
到题目。
ACM/ICPC
的区域预赛是规模很大，范围很广的赛事，近几年，全世界有
1000
多所大学，
2000
多支参赛队在六大洲的
28~30
个赛站中争夺世界决赛的
60~66
个名额，去年我校举办的区域预赛，就有来自
50
多所高校的
100
多支队伍参加，其激烈程度可想而知。
与其他编程竞赛相比，
ACM/ICPC
题 目难度更大，更强调算法的高效性，不仅要解决一个指定的命题，而且必需要以最佳的方式解决指定的命题；它涉及知识面广，与大学计算机系本科以及研究生如程 序设计、离散数学、数据结构、人工智能、算法分析与设计等相关课程直接关联，对数学要求更高，由于采用英文命题，对英语要求高，
ACM/ICPC
采用
3
人合作、共用一台电脑，所以它更强调团队协作精神；由于许多题目并无现成的算法，需要具备创新的精神，
ACM/ICPC
不仅强调学科的基础，更强调全面素质和能力的培养。
ACM/ICPC
是一种全封闭式的竞赛，能对学生能力进行实时的全面的考察，其成绩的真实性更强，所以目前已成为内地高校的一个热点，是培养全面发展优秀人材的一项重要的活动。概括来说就是：强调算法的高效性、知识面要广、对数学和英语要求较高、团队协作和创新精神。
注：此文摘自中山大学新闻中心
二、程序设计竞赛考核的方面
程序设计竞赛与软件工具的使用不同，它要求编程者以某种高级语言为媒介，通过构造算法去解决由现实生活中抽象出来的问题，这些问题非一般工具软件能解决。程序设计对人的能力要求是多方面的。编程者不仅要熟悉计算机语言的语法，而且还要具备：
1
、
扎实的数学基础和算法知识，能够对问题或者客观存在的事务及其所要解决的问题产生正确认识和理解，包括弄清楚事物属性、行为及其彼此之间的关系。
2
、
娴熟的编程技术，能够把对问题及其方法的认识描述出来，最终产生一个计算机能够理解和执行的系统实现。
3
、
相应的实践能力和创造能力，能够独立思考、提出质疑，拓延思路、洞悉规律，创造性地运用知识于不同的问题情景。
4
、
如果真正参加竞赛，那么对心理素质的要求非常高。落后时不急不躁，领先时不盲目乐观，方能立于不败之地。同时，大学生的
ACM
竞赛是三人团队共用一台机器，这对培养集体合作精神很有好处。
综上所述，程序设计竞赛主要考的是数据结构、算法和数学模型
(
基本不包括
windows
程序，这是和
programming
不一样的地方
—
转载者注
)
， 而这些知识恰恰就是本科阶段主要的专业基础课程，所以程序设计竞赛一定程度上可以反映出一个学校的教学水平，这也是为什么程序设计竞赛为什么规模越来越大 的一个原因。正因为程序设计能比较客观地反映人的综合素质，因此，国际、国内的各种大学生和中学生信息学方面的竞赛都把程序设计作为考核内容。
注：此文是复旦大学首
席
教授
博士生导师施伯乐 给一本关于程序设计竞赛的书所写的序
三、常用算法简介（个人理解，仅供参考）
1.
搜索
DFS(
深度
)
，
BFS(
广度
)
，用的很多，基本思想，做题时优先考虑的算法。
BFS
：把前面的信息存储，把所有的信息计算并保存，这样前面的信息不用重复计算。
BFS
是一层一层来搜索，搜索完一层，再去搜索下一层（常用来从前向后推））；
DFS
是一直向下搜，直到到底才返回（常用第归来实现）。
2.
递推公式，组合数学上讲得比较多。关系递推，欧拉公式，母函数等都会有所涉及，尤其是从现有的已知条件中如何获取递推公式，找到层与层之间的关系是解题的关键。这需要对这种题的原型有较多的研究，对这部分的概念有较深的理解。
3.
排列组合、数论及数字游戏等，对数学的知识要求比较高，不过纯粹数学的题近年来不常考。
NOI,IOI
（高中生的竞赛）中经常涉及。
4.
动态规划
=
分析
+
前面的结果，和递推有点类似。
a)
递推公式的一般形式：
f(n) = f(n-1) + f(n-2);
b)
动态规划的一般形式：
F[n][k] = max{ F[n-i][k-1] + F[i][1] }
其中
1<=i<=n-k+1.
c)
此部分考得较多，题目类型变化也多，比较灵活，但是只要想对了，编程很是容易。
5.
图论，数据结构和离散数学上都有涉及，竞赛中涉及到的有最短路（纪录路径），最小生成树、
Euler
图、二分图（实际模型很多，比较难看出来，用得较多）
6.
模拟题，考的是基本功。要求学生：编程速度快、基本功扎实、读题时要认真仔细、肯花时间，这样就没有什么问题了。
7.
高精度，属基础部分。