ACM/ICPC
1.什么是ACM/ICPC
ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞赛)是由国际计算机界历史悠久、颇具权威性的组织ACM(Association for Computing Machinery,国际计算机协会)主办的,世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。
ACM-ICPC的历史及其影响
ACM/ICPC从1970年开始,已经举办了30多届,其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该竞赛一直受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注。可以说,ACM国际大学生程序设计竞赛已成为世界各国大学生最具影响力的国际级计算机类的赛事。
2.ACM-ICPC的比赛形式和内容
ACM/ICPC采用组队参赛的形式,由三名队员组成一支队伍参赛。比赛时三名队员只使用一台电脑,整个比赛时间为5个小时。
比赛题目为6~10道不等,全英文。
标准的程序数据输入和输出解答要求。选手们必须根据题目内容设计算法,并完成相应的功能要求。该队程序如果能在规定时间内得出正确的答案视为通过。
队伍通过的题目数量多的在比赛中排名越高,题目数相同的则用时越少的排名越高。
3.竞赛内容
竞赛涵盖的范围很广,大致划分如下:Direct(简单题),Computational Geometry(计算几何),Number Theory(数论),Combinatorics(组合数学),Search Techniques(搜索技术),Dynamic Programming(动态规划),Graph Theory(图论),Other(其他)
4.ACM-ICPC在世界
该项竞赛分区域预赛和国际决赛两个阶段进行。各预赛区前几名自动获得参加世界决赛的资格,世界决赛安排在每年的3~4月举行,而区域预赛安排在上一年的9~12月在各大洲举行。(咱们吉林省的省赛一般是在4-5份)。
区域预赛现在又分网上预赛和赛区决赛。
ACM/ICPC的区域预赛是规模很大、范围很广的赛事。仅在2003年参加区域预赛的队伍就有来自75个国家(地区),1411所大学的3150支代表队,他们分别在127个赛场中进行比赛,以争夺全球总决赛的73个名额。
2005年第30届ACM/ICPC亚洲赛区预赛共设了北京、成都、汉城、东京等11个赛站,来自亚洲各国知名高校的各个代表队进行了激烈的角逐。
5.ACM-ICPC在中国
中国内地于1996年在上海大学举办了国内首届ACM/ICPC亚洲区预赛,至今已九届。
前六届赛区都由上海大学主办;
2002年分设北京和西安赛区,分别由清华大学和西安交通大学主办;
2003年设北京和广州赛区,分别由清华大学和中山大学主办。
2004年设北京和上海赛区,分别由北京大学和上海交通大学举办。
2005年第30届ACM国际大学生程序设计竞赛亚洲区预选赛,中国设有北京赛区、杭州赛区和成都赛区,分别由北京大学、浙江大学和四川大学承办。
2006年赛事重新回到上海大学举办,纪念ACM/ICPC在国内连续举办十周年。
2007年(缺)
刚刚结束的2008年第33届ACM国际大学生程序设计竞赛亚洲区预选赛,中国设有哈尔滨赛区、北京赛区、合肥赛区、杭州赛区和成都赛区,分别由哈尔滨工程大学、北京交通大学、中国科技大学、杭州电子科技大学和西南民族大学承办。
国内的许多著名大学,一直非常重视该项赛事的参与。清华大学、浙江大学、复旦大学、上海交通大学、中山大学、同济大学一直是国内ACM/ICPC的领先者。
我们吉林农业科技学院起步晚,但我们的同学绝对有能力和他们一比高下!
我们电子科技大学的ACMilan战队在第32届闯进了在加大拿举行的世界总决赛
6.怎样才能成为一个ACM选手
门槛低,学会C/C++,就可以入手。
今后我们学校将大力开展相关的竞赛培训活动
需要同学们投入精力,主动进行相关的练习和学习。
耽误你打游戏、看电影的时间,却换来更多的“财富”
7.ACM-ICPC能给你带来什么
去外地参赛、甚至出境去新加坡、韩国、日本参赛的机会
获奖,更够为你带来非常多的荣誉(奖励学分、奖学金),简历上增添光彩的一笔,更接近国外名校。
但参加这个竞赛,不是为了去外地比赛玩的,也不是单单为了拿个奖
8.参加ACM-ICPC的意义
竞赛中,高级语言程序设计、高等数学、数据结构、算法分析、数学建模、离散数学、数论、图论、概率论、计算机几何学、组合数学等课程的知识都有所涉及,通过竞赛培训,强化、拓展相关学科知识的深度和广度。
听身边比赛的朋友说的最多的一句话就是:“比赛的前后,我是绝对不一样的!”
我想当你参加了比赛之后,你也一定会发自内心地说一句的。
9.相关连接:
http://acm.timus.ru/ (外国)
http://acm.hdu.edu.cn/ 杭州电子科技大学
http://acm.pku.edu.cn/JudgeOnline/ 北京大学
http://acm.pku.edu.cn/ PKU 北京大学
http://acm.nenu.edu.cn/ 或者 http://acm.hrbeu.edu.cn/ 哈工程
http://acm.jlu.edu.cn/joj 吉林大学
http://acm.tongji.edu.cn/ 同济大学在线题库,唯一的中文题库
http://acm.tju.edu.cn/ 天津大学
http://acm.sgu.ru/ 俄罗斯圣萨拉托夫州大学在线题库
http://acm.mipt.ru/judge/bin/problems.pl?lang=en 俄罗斯莫斯科物理技术学院
https://spoj.sphere.pl/ 波兰格但斯克理工大学
http://acm.uva.es/ 西班牙的Universidad de Valladolid在线题
下面我就从浙江大学的在线题库中选择了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
",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();
}
大家可以试一试,分别输入合法的整型数和非法的字符型数,比较结果就能够比较好的领会这部分内容了。另外两种语言的原理很容易看懂,就不傲述了,总之就想通过这个问题说明:问题看似简单,实则包含着很多内容,再简单的程序我们都要结合语言的自身特点,以一种最优化的结构去表达他, 不要忽视任何的小问题。