ACM比赛介绍

ACM-ICPC比赛介绍及相关参考

    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区赛共有两个赛区，分别由北京清华大学和广州中山大学承办。下面从浙江大学的在线题库中选择了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();
}

    大家可以试一试，分别输入合法的整型数和非法的字符型数，比较结果就能够比较好的领会这部分内容了。另外两种语言的原理很容易看懂，就不傲述了，总之就想通过这个问题说明：问题看似简单，实则包含着很多内容，再简单的程序我们都要结合语言的自身特点，以一种最优化的结构去表达他，不要忽视任何的小问题。下面给大家介绍一些ACM-ICPC的网站供大家学习
acm西北欧赛区（德国达姆斯塔特）网站
-darmstadt.de/
acm西南欧赛区（葡萄牙波尔多）网站

acm中欧赛区（波兰华沙）网站

acm东北欧赛区（俄罗斯圣彼得堡）网站

acm东南欧赛区（罗马尼亚布加勒斯特）网站

acm达卡赛区网站

acm函馆赛区网站

acm坎普尔赛区网站

acm新加坡赛区网站

acm德黑兰赛区网站
~acmicpc/
acm大田赛区网站
~acmicpc/
acm台北赛区网站

acm上海赛区网站

ACM-ICPC最重要的资源就是在线题库集锦，下面也为大家提供这方面的网站网址：
简称: uva
全称: Valladolid Programming Contest Site
所在国：西班牙提交方式：web方式和email方式说明：可能是世界上名气最大，最古老的在线题库了。收集了N卷的题目，许多国家队的高手都是从这里练出来的。题目包括历届ACM/ICPC分区赛试题、总决赛试题以及很多其他网友自己出的题目。题目类型比较全面，难度较平均，但是测试数据非常刁钻，而且经常更新旧的数据，在别的地方能通过的程序到了uva就可能无法通过。定期有比赛，并且可以利用它的系统主办自己的比赛。唯一的缺点是系统太烂，比赛的时候经常系统崩溃（不过这和参加的人太多也有关）。网址：
简称: zju/zoj
全称: ZJU Online Judge Contests
所在国：中国提交方式：web方式说明：目前国内唯一一个在线题库。目前有6卷题目了，题目大多数是以前的ACM/ICPC分区赛试题和一些浙大ACM队员自己出的题目。定期有比赛（Monthly Contest）。网址：
简称: ural
全称: Ural State University Problem Set Archive with Online Judge System
所在国：俄罗斯提交方式：web方式和email方式说明：这也是一个著名的题库，因为是俄罗斯人办的，题目的数学味道比较浓。定期有比赛。这里的题目风格和ACM/ICPC不太相同，题目数学趣味浓，有一定难度，很多题目都是那种需要一些小技巧的，一旦想出来了程序可能只有几十行。中国的很多搞OI的中学生在这里做题，这里的题目比较适合中学的OIer。网址：
简称: sgu
全称: Saratov State University :: Online Contester
所在国：俄罗斯提交方式：web方式说明：一个比较新的题库，同样因为是俄罗斯人办的，题目的数学味道很浓。定期有比赛。