C++ACM模板9资源-CSDN文库

4星 · 超过85%的资源需积分: 9 90 浏览量 2011-01-24 13:27:05 上传评论收藏 997KB DOC 举报

资源推荐

资源详情

资源评论

的组成
免费模板~~~
　　　　　　　　　　　　　　　　目　录
第一篇  入门篇..................................................................................................................................2
第  章  新手入门
1  ACM
国际大学生程序设计竞赛简介
...................................................................................3
2  ACM
竞赛需要的知识
...........................................................................................................4
3  
团队配合
................................................................................................................................6
4  
练习、练习、再练习
............................................................................................................6
5  
对新手的一些建议
................................................................................................................7
第  章  语言介绍
1  C++
简介
................................................................................................................................9
2  
变量
........................................................................................................................................9
3  C++
数据类型
......................................................................................................................10
4  C++
操作符
..........................................................................................................................11
5  
数组
......................................................................................................................................14
6  
字符数组
..............................................................................................................................15
7  
字串操作函数
......................................................................................................................16
8  
过程控制
..............................................................................................................................18
9  C++
中的函数
......................................................................................................................22
10  
函数规则
............................................................................................................................23
第  章   简介
1  
泛型程序设计
......................................................................................................................25
2  STL 
的组成
...........................................................................................................................29
第二篇  算法篇................................................................................................................................48
第  章  基本算法
1  
算法初步
..............................................................................................................................49
2  
分治算法
..............................................................................................................................55
3  
搜索算法
..............................................................................................................................59
4  
贪婪算法
..............................................................................................................................65
第  章  进阶算法
1  
数论基础
..............................................................................................................................75
2  
图论算法
..............................................................................................................................81
3  
计算几何基础
......................................................................................................................98
第三篇  实践篇..............................................................................................................................112
第  章  《多边形》
第  章  《灌溉问题》
第  章  《》
第  章  《》解题报告
第  章  《》解题报告
第  章  《包裹运送》


的组成

第1章新手入门

1 ACM 国际大学生程序设计竞赛简介

1.1 背景与历史

1970 年在美国 TexasA&M 大学举办了首次区域竞赛，从而拉开了国际大学生程序

设计竞赛的序幕。1977 年，该项竞赛被分为两个级别，即区域赛和总决赛，这便是现代

ACM 竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。 1995 至 1996

年，来自世界各地的一千多支高校的代表队参加了 ACM 区域竞赛。ACM 大学生程序设

计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其

解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大

学生程序设计竞赛。

1.2 竞赛组织

竞赛在由各高等院校派出的  人一组的队伍间进行，分两个级别。参赛队应首先参

加每年  月至  月在世界各地举行的“区域竞赛 !"# $%$&”。各区域竞赛得分最高

的队伍自动进入第二年  月在美国举行的“决赛' !"# $%$&”，其它的高分队伍也有可

能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(!)*"$+#!,-%.&，他负责

选手的资格认定并指定或自己担任该队的教练 )!)/&。每支队伍最多由三名选手

) $%$! $&组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一

名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。

1.3 竞赛形式与评分办法

竞赛进行  个小时，一般有 0 道试题，由同队的三名选手使用同一台计算机协作

完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程

序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。

程序运行不正确是指出现以下  种情况之一：

&运行出错.* 1$2#...&；

&运行超时$21"2$#3),,&；

&运行结果错误4. #! %4.&；



 竞赛培训资料

&运行结果输出格式错误5.% $!$ #...&。

竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用

时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时

间是竞赛开始到提交被接受的时间加上该问题的罚时（每次提交通不过，罚时  分钟）。

没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料（包括试

题）将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语

言包括 6，，及 !-!，也可以使用其它语言。具体的操作系统及语言版本各

年有所不同。

1.4 竞赛奖励情况

总决赛前十名的队伍将得到高额奖学金：第一名奖金为  美元，第二名奖金为

 美元，第三名奖金为  美元，第四名至第十名将各得到 " 美元。除此之外还

将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。

2 ACM 竞赛需要的知识

2.1 编程语言是最重要的基本功

无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，编程语言都是大

家要过的第一道关。亚洲赛区的比赛支持的语言包括 7与 !-!。首先说说 !-!，众

所周知，作为面向对象的王牌语言，!-! 在大型工程的组织与安全性方面有着自己独特

的优势，但是对于信息学比赛的具体场合，!-! 则显得不那么合适，它对于输入输出流

的操作相比于 要繁杂很多，更为重要的是 !-! 程序的运行速度要比 慢  倍以上，

而竞赛中对于 !-! 程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提

出了更高的要求，是相当不利的。其实，并不主张大家在这种场合过多地运用面向对象

的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降

低程序的执行效率。

接着说  和 。在赛场上使用纯  的选手还是大有人在的，它们主要是看重了纯

 在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只

要提高了自己在算法设计上的造诣，纯  一样能发挥巨大的威力。

而 相对于 ，在输入输出流上的封装大大方便了编程操作，同时降低了出错的

可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同

学比较在意这点，可以尝试  和 的混编，毕竟仅仅学习 的流操作还是不花什么

时间的。

的另一个支持来源于标准模版库&，库中提供的对于基本数据结构的统一接

口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，

与此相对的，使用  要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必

须放弃 ，这意味着我们不能存在“有了  就可以不去管基本算法的实现”的想法；



的组成

另外，熟练和恰当地使用  必须经过一定时间的积累，准确地了解各种操作的时间复

杂度，切忌对  中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。

通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的掌握并不要求十分

全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方

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

虽然被定性为程序设计竞赛，但是参赛选手所遇到的问题更多的是没有解决问题的

思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。有一年 8.",

' !" 的总冠军是波兰华沙大学，其成员出自于数学系而非计算机系，这就是一个鲜活的

例子。竞赛中对于基础学科的涉及主要集中于数学，此外对于物理、电路、生物、化学、

医学等也可能有一定应用，但是不多。因此，大一的同学也不必为自己还没学数据结构

而感到不知从何入手提高，把数学捡起来吧！下面我来谈谈在竞赛中应用的数学的主要

分支。

离散数学

离散数学作为计算机学科的基础是竞赛中涉及最多的数学分支，重中之重又在于图

论和组合数学，尤其是图论。图论之所以运用最多是因为它的变化最多，而且可以轻易

地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、9' 和

'，关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等

等。虽然这部分的比重很大，但是往往也是竞赛中的难题所在，如果有初学者对于这部

分的某些具体内容暂时感到力不从心，也不必着急，可以慢慢积累。

组合数学

竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于

图论要简单一些，很多知识对于小学上过奥校的同学来说已经十分熟悉，但是也有一些

部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难

题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为难题。

数论

数论以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这

部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想上一阵

时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识

确定大概的过程之后，核心算法往往要涉及数论的内容。

计算几何

计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多

的结合，较常用到的部分包括线段相交的判断、多边形面积的计算、内点外点的判断、

凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。

线性代数

对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于

矩阵来找到更好的算法。



剩余63页未读，继续阅读

评论收藏

内容反馈

uc6814580

2013-06-15

我觉得这个叫做ACM讲义更加合适一点。
haotian23571113

2012-11-30

很不错，挺全的，谢谢楼主了。

promotercx

粉丝: 4
资源: 8

C++ ACM模板9

最新资源

C++ ACM模板9

ACM大数模板(c/c++)

ACM C++ stl 模板

ACM&C++实用技巧与模板库

ACM模板

ACM模板和一些题目的代码实现c++源码.zip

ACM模板byXYM

ACM模板库.docx

ACM几何题模板

ACM模板-清华大学.zip

ACM数论模板

ACM常用模板 ACM常用模板

ACM模板——清华大学

ACM模板-f_zyj v

ACM比赛模板

ACM之字符串模板

基于C++的ACM模板

ACM模板(数据结构)

基于C++实现的ACM-ACM竞赛常用模板

ACM模板1

基于C++的ACM-ICPC模板

ACM模板ACM 模板

最好最全的ACM模板

浙江大学---ACM模板

吉林大学ACM模板

ACM 模板 函数

杭州电子科技大学ACM模板库

上海交大ACM模板_上海交大ACM模板_ACM模板_

浙大上交吉大上大acm模板.zip

上海交大ACM模板.zip

acm模板_acm模板

最新资源

ACM 模板函数