北京大学暑期课：ACM/ICPC竞赛训练(ACM/ICPC Training)
课程介绍
北京大学的ACM国际大学生程序设计竞赛(ACM/ICPC)水平在国内处于领先地位，自2005年至2012年每年均参加总决赛，名次分别为11(铜牌)、13、14、13、20、14、13,13,13。北京大学ACM/ICPC竞赛队整体实力很强，在最近 九年的分区赛中，绝大部分队伍都获得金奖，只有少数参赛队获银奖以下。北京大学多次承担ACM/ICPC亚洲区预选赛命题，广获好评。近几年负责命题的赛区有：2008年北京赛区，2009年宁波赛区，2010年杭州赛区，2010年福州赛尘银含区,2011年北京赛区，2011年福州赛区，2012年金华赛区，2012年杭州赛区。均由此课程主讲教师郭炜负责命题。北京大学的Online Judge --- POJ 更是国内最有影响力的ACM/ICPC竞赛训练平台之一，在国际上也有较高知名度和较多用户。
北京大学ACM/ICPC竞赛队精英汇集，大多数队员都曾在全国中学生信息学奥赛上取得过优异成绩，或在ACM/ICPC亚洲区预选赛中获得过金奖。北京大学ACM/ICPC竞赛队通过多年的积累，已经形成了一套行之有效的系统训练方法。
本课程为准备参加ACM/ICPC的同学设置，不但对提高参训学校的竞赛成绩大有帮助，而且也是广交牛友的绝佳机会。
课程信息
课程编号： 30330500 学分: 2 一般来说，所修学分和成绩在选课者所在的大学也有效(具体情况请咨询贵校教务）。
学费：1000元。食宿自理。我校会开具学费收据，如果贵校同意为学生出学费，则可据此报销。
授课对象：本课程为ACM/ICPC 入门课程，对于已经获得过亚洲区预选赛前四十名的，不建议选修 。本课程以面向大学生为主。但如果您是教师或中学生，只要对ACM/ICPC感兴趣，我们也同样欢迎选修。
先修课程：C++,数据结构；基础算法；
授课时间：2013.7.8 - 2012.7.19，周一至周五 13:00 - 17:00
授课地点：北京大学
报名方式： 网上报名。报名链接：http://summer.pku.edu.cn/ss/index.jsp 报名时间：5月20－6月28日
北京大学教务部咨询电话：(010)62751435 62751430
授课内容：
课程内容涉及ACM/ICPC竞赛中用到的大量算法，包括：组合数学、数论、图论、计算几何、高级数据结构等。
授课方式：
包括：专题讲座、专题练习和竞赛实战。
课程内容6次由教师讲授，2次由北京大学优秀ACM队员讲授。
其中8天的内容为每天一个算法专题。
另外2天安排2场每场4小时的练习赛。
课程内容共八个专题，除理论知识外还包括精选例题讲解（先后次序可能调整，内容也可能微调）：
7.8 数据结构（一）: 线段树，树状数组，二维线段树
7.9 数学题：组合数学，数论等
7.10 数据结构（二）: 并查集, DFA, Trie树，Trie图等
7.11 若干图论问题：最小生成树 最短路 强连通分量、桥和割点 等
7.15 计算几何：线与线求交，线与面求交，求凸包，半平面求交等
7.16 搜索：深搜，广搜，剪枝，IDA*算法
7.17 动态规划：状态压缩，树形动归，平行四边形法则
7.18 网络流算法：基本的网络流算法，Dinic算法，带上下界的网络流，最小费用流
第一周的周五(7.12)：个人练习赛
第二周的周五(7.19)：组队比赛
成绩评定：
根据平时训练做题表现和竞赛名次评定成绩。
授课教师：
郭炜，曾经讲授过 *** 作系统, Java程序设计语言，多年来一直讲授《程序设计实习》课程，从2004年起担任ACM/ICPC北大队教练。EMail: gwpl@pku.edu.cn 欢迎咨询。 著有《新标准C++程派笑序设计》、《ACM国际大学生搏衫程序设计竞赛亚洲区预选赛真题题解》等书。
ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest – ACM-ICPC）由国际计算机学界著名的ACM学会（Association for Computer Machinery）主办，是世界上规模最大、水平最高的国际大学生程序竞赛。每年举办一次。ACM成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织。ACM国际性大学生程序设计竞赛自1970年开始，其宗旨是使大学生能通过计算机充分展示自己分析问题和解决问题的能力。参加本项比赛的选手至少需要掌握计算机科学的常用算法，基本的计算理论，（如：离散数学，具体数学，组合数学基础），数据结构基础，程序设计语言（规定是C/C++或者是Java）。在本项比赛中考察学生的不仅仅是能够完成指定任务的程序，更要求在完成程序的功能的基础之上提高程序的运行效率与空间占用率。我在浙江大学ACM在线测试组参加测试的最深体会就是你时时刻刻都应当去考虑如何去最大限度的优化，改善你的程序结构，已达到用最小的空间，最优的算法实现程序的功能。从数学角度考虑，题目主要的方向集中在工程数学，抽象数学很少涉及。一般题目都会给出要求和几组输入和输出作为程序设计的参考，也是检验程序正确性的标准之饥运一。
整个竞赛分为地区预赛(Regional Contest)和决赛（Final Contest）两个阶段进行。今年（2003）在中国大陆地区举行的ACM-ICPC区赛共有两个赛区，分别由北京清华大学和广州中山大学承办。我们学校的计型肢唤算机学院从去年卜凯起开始组织学生参加世界上最具权威性的大学生程序设计竞赛，取得了较好的成绩，我们学院在明年也要有组织的参加这项国际性的大赛，希望有志于此的同学加入我们的行列。我们会定期的举办相关的讲座以使同学们对ACM-ICPC比赛有更多地了解。鉴于我院学生对这项比赛了解的实际情况，下面我就从浙江大学的在线题库中选择了Volume I当中的第一个题目向大家展示一下这项比赛的特点。
Calculate a + b
Input
The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line.
Output
For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input.
Sample Input
1 5
Sample Output
6
Hint
Use + operator
如果选用的程序设计语言是 C++:
#include
int main()
{
int a,b
while(cin >>a >>b)
cout <<a+b <<endl
}
如果选用的程序设计语言是C:
#include
int main()
{
int a,b
while(scanf("%d %d",&a, &b) != EOF)
printf("%d\n",a+b)
}
如果选用的程序设计语言是PASCAL
program p1001(Input,Output)
var
a,b:Integer
begin
while not eof(Input) do
begin
Readln(a,b)
Writeln(a+b)
end
end.
程序的功能中文描述是这样的：在一行输入两个整型数，换行输出结果，循环执行，直到用户中止。
三个程序代码都摆出来了，虽然这个程序极其简单，但是可以说明很多语言的特点以及程序设计的思想，大家可以清楚地看到与一般的思路最大不同点就是没有使用循环语句for,而是选择while,结合程序设计语言自身的特点，从而大大的减少了代码量，而且不易出错。下面我把这个程序关键点的原理阐述一下：
针对题目的要求，要保证无数次输入下程序的健壮性，而while语句这点的优势就是及其突出的，此种情况下，我们通常采用在while循环结构的首部使用流读取运算符输入一系列值。当遇到文件结束符或者是非法输入时运算符返回0（false）这种结构非常适合事先并不知道有多少组输入时，那么下面我们在着重说一下cin在这里的用法.
上面的C++算法描述中，程序的跳出我们采用输入非法字符，一旦输入非法字符，则返回值为0（false）则，while循环结束，也就是输入输出流当中初学者不太常使用的流错误。
下面我们做一个简单的介绍：
对于输入输出流的状态，我们可以用类ios中的位测试流的状态。类ios是输入/输出类istream,ostream和iostream的基类。当遇到文件结束符时，输入流中自动设置eofbit.可以在程序中使用成员函数eof确定是否已经到达文件尾。如果cin遇到了文件的结束符，那么函数调用：
cin.eof()
返回true,否则返回false
当流中发生格式错误的时候，虽然会设置failbit,但是字符并未丢失。成员函数fail判断流 *** 作是否失败，这种错误通常可恢复。
当发生导致数据丢失的错误时，设置badbit.成员函数bad判断流 *** 作是否失败，这种严重错误通常不可恢复。
如果eofbit,failbit,badbit都没有设置，则设置goodbit
如果函数eo,fail,bad都没有设置，则成员函数good返回true.成员函数中应当只对合法流进行I/O *** 作。
下面是为说明问题专门写的一个测试代码，
#include
int main()
{
int a
cin <<a
cout >>cin.eof()
cout >>cin.fail()
cout >>cin.bad()
cout >>cin.good()
}
大家可以试一试，分别输入合法的整型数和非法的字符型数，比较结果就能够比较好的领会这部分内容了。另外两种语言的原理很容易看懂，就不傲述了，总之就想通过这个问题说明：问题看似简单，实则包含着很多内容，再简单的程序我们都要结合语言的自身特点，以一种最优化的结构去表达他， 不要忽视任何的小问题。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）