ACM入门指南

本文转载于CSDN  , 网络有多种版本 ,现收藏CSDN版本进行普及教育,拟在普及ACM详细知识予以广大网友。

前言:
这篇指南不对ACM/ICPC国际大学生程序设计竞赛进行介绍,计算机学子如果不了解的可以在百度上进行搜索查询,这里介绍的只是一个计算机学生想要在ACM/ICPC里进行发展的初学者。内容比较简单通俗,完全是给新接触的人看的,已经接触过的请飘过,该干嘛的干嘛去。

语言关:

要进行程序设计,也就必然要熟悉编程语言,只要掌握了一门语言,就可以进行ACM训练了。一般通用语言如C、C++、JAVA都可以,这三种语言都有自己的优势和缺点,C在效率方面比较好;但C++封装了输入输出流,方便了我们的操作也减少出错的可能性,而且C++提供了非常强大的标准模版库(STL),使得很多在C上实现起来比较麻烦的代码,在C++上却非常方便;JAVA在大型工程和安全方面都有比较独特的优势,但在ACM里面却不是一种优秀的语言,因为JAVA的执行效率要比C、C++慢很多,如果题目限时比较紧的话,就不适合用JAVA,当然JAVA为我们提供了很方便的高精度运算(大整数运算),所以个人认为,刚学完C的可以用纯C来写训练,在训练过程中可以学学C++,有时间的把STL也好好学学,这样可以减少很多不必要的劳动。

初次接触ACM训练的同学经常会遇到问题,就是输入和输出问题,所以如果对语言的输入输出问题不是很熟悉的话,要抽几天时间重点看看,特别有些初学者在输出时总会输出冗余信息,可能认为有交互性吧,但这是ACM不允许的,它不需要任何交互性。不严格按照题目要求进行输入输出的程序是无法通过系统测试的。

熟悉在线评测系统

在线评测系统,英文叫Online Judge,(简称OJ)里面提供了很多题目给我们平时训练之用。这里以浙江大学的在线评测系统为例,网址是http://acm.zju.edu.cn 先在上面进行注册,注册完后就可以进行题目的训练了,点击主页上的“Problems”,就可以看到里面的题库,可以选任何一个题来做,里面的题目不是由易到难进行排列,而初学者要选择比较简单的题目来做。一般来讲,每道题目都有他做对的正确率和提交的总次数,那些正确率比较高并且提交次数比较多的就会比较简单。一旦确定了做某道题,在读懂题意以后,就可以进行构思和编码了,编码完成后再进行程序的调试。一般写完了的程序不一定就正确,这时可以用题目下方提供的一些数据进行测试,如果不能通过,还得要对代码进行修改,直到能通过所有的测试数据。这里要注意的是,很多新手会问这样的问题,我的程序通过了它的数据呀,为什么提交的时候不正确呢,这是因为OJ系统关于这题的测试数据远远不止这些,它还有许多你无法知道的数据,你的程序必须要能通过它所有的数据,才算是正确。下面我们挑出里面最简单的一个题(1001)进行讲解:

A + B Problem

Time limit: 1 Seconds   Memory limit: 32768K

Total Submit: 52075   Accepted Submit: 22355

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

我们发现这是一个求两数和的题目,输入a b 程序输出a+b的结果,于是我们可以编写如下代码(注意:”//”是C++的注释):[code]

//C

#include <stdio.h>

int main()

{

int a,b;

while(scanf(“%d %d”,&a, &b) != EOF) //直到没有数据输入退出,

//ms-dos窗口方式下, ctrl + z结束.

printf(“%dn”,a+b);

}

//或者C++

#include <iostream>

using namespace std;

int main()

{

int a,b;

while(cin >> a >> b)

cout << a+b << endl;

return 0;

}

[/code]在题目的下面,有一个“Submit”选项,点击出现提交界面,我们可以把我们的代码复制上去,输入自己的帐号和密码就可以进行提交,如下图:

点击“submit”,出现如下界面

我们就可以点击“status”,系统通过对我们的代码进行测评,然后会给我们返回一个提示信息,如下图,这个程序的返回结果是Accepted,表示正确.

并不是所有提交上去的代码都是返回Accepted,只有仔正确的情况下才会返回Accepted,一般而言,系统返回的信息有以下几种情况:

Accepted(AC):恭喜你,你的程序是正确的。

Presentation Error(PE):虽然你的程序输出了正确结果,但是二哥结果的格式有点问题,这时要检查程序的输出是否多了或少了空格(’ ‘)、制表符(’t’)或者换行符(’n’)。

Wrong Answer(WA):程序的输出结果不正确,可能是算法有问题,也可能是其他问题。

Runtime Error(RE):运行时错误,例如访问非法内存,像指针,数组下标越界会造成,程序出现除数为0,栈溢出等等。

Time Limit Exceeded(TLE):程序运行的时间超过题目的时间限制。

Memory Limit Exceeded(MLE):程序运行的内存超过题目的内存限制。

Output Limit Exceeded(OLE):程序输出的内容太多,超过题目的输出限制。

…………

除了Accepted信息外,其他信息都说明你程序有问题,还要进行修改然后提交,直到正确。对系统的介绍大概到此,如果有问题或者还有不明白的,可以提问进行补充。

程序的输入和输出问题

OJ一般只支持标准输入输出,提交的程序不允许操作文件,你的程序不能输出任何多余信息,包括提示信息,如对上面1001题的程序,可能会有些人这样写:[code]

#include <stdio.h>

int main()

{

int a,b;

while(1)

{

printf(“请输入a和b:”); //此行是多余输出,不允许

if(scanf(“%d %d”,&a, &b) == EOF)

return 0;

printf(“%dn”,a+b);

}

}

[/code]每个题目的测试数据测试完毕后,就会以一个标记结束输入,向1001是文件结束,有些程序是特定的数据作为输入的结束,选手要认清楚这点。

几个网上测评系统

对于初学者,在http://acm.hdu.edu.cn  http://acm.hdu.edu.cn上面有比较多的适合初学者的题目,联系题目链接在http://acm.hdu.edu.cn/listproblem.php?vol=1

http://acm.hdu.edu.cn/listproblem.php?vol=1 上。

浙大上面也有不少比较简单的题目,地址是 http://acm.zju.edu.cn]http://acm.zju.edu.cn如果不能判断哪些题目比较简单的话,可以查看这里的链接:http://acm.zju.edu.cn/forum/viewtopic.php?t=1060

每个OJ系统的操作大同小异,应该不成什么问题,有问题群里问问。

当然还有不少比较出名的OJ,但作为初学者,这两个OJ已经是非常不错了,多做题,多看书,不浮躁,不气馁,不懂要问,水平提高会很快的。

 

新手要掌握的知识和一些入门题

刚学完一门语言,对算法和数据结构还不懂的同学,可以做做一些简单的题目,如浙大的:

1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241 1242

1251 1292 1331 1334 1337 1338 1350 1365 1382 1383 1394 1402 1405 1414

1494 1514 1622 1715 1730 1755 1760 1763 1796 1813 1879 1889 1904 1915

1949 2001 2022 2099 2104 2108 2172 2176 2201 2208 2321 2345 2351 2376 2388

2405 2417 2433 2781 2782 2807 2812 2857 2851 2878 2883 2886 2892

上面题目都不怎么需要算法基础,都是新手可以做出来的,多做可以比较快入门,没学过算法和数据结构的,自己要自学一些算法和数据结构,在了解了一些重要的数据结构的术语如线性表,栈,队列,字串,树,图等等的前提下,可以掌握以下相关算法:

二分查找,数制转换,表达式求值,KMP字符串匹配算法,二叉树遍历,哈夫曼编码,深度优先搜索,广度优先搜索,最短路径,拓扑排序,二叉排序树,哈希,排序(插入排序、冒泡排序、快速排序、归并排序、堆排序,虽然ACM不怎么直接考排序,但掌握了有好处),高精度(大整数)加减乘除,欧几里德算法,扩展的欧几里德算法,以上的相关算法都是比较基础的,要重点掌握,可以自己买一本数据结构,或者图书馆借,遇到有上面算法的要重点研究,也可以上网搜索这些知识(这个很重要),看完某一算法,可以做做相关的题目,这样就对算法的了解有一个升华.

相关知识的题目,包括一些数学方面的题目(不保证全部正确):

北大ACM-题型分类