第01篇 ACM/ICPC竞赛之基础篇

一、ACM/ICPC竞赛的特点

ACM/ICPC（国际大学生程序设计竞赛）是以算法设计为主的程序设计竞赛，并不涉及具体的应用技术。

ACM/ICPC竞赛以组队形式参赛，每个参赛队由三名队员组成，共同使用一台计算机解题。通常每场比赛的试题为6至10题，根据各队的完成题数和罚时进行排名。题目提交通过称为完成，从比赛开始到提交成功所用的时间为题目的基础罚时，另外，一道题目每提交失败一次，将增加20分钟罚时。也就是说，参赛队要尽可能用最快的速度、最少的失败次数，解决最多的题目。

二、输入和输出处理
试题一般采用标准输入和输出方式读取输入和产生输出，在题目中会详细描述输入和输出的格式和值域范围，所写的程序一定要严格遵守题目指定的输入输出格式。

在比赛试题的输入和输出处理上，针对一些常见的情形，有一些常用的方法。

1、多测试用例的输入和输出

有些试题在一次输入中只包含一个测试用例，也就是说，程序每运行一次，只算一道题。也有些试题在一次输入中包含多个测试用例，也就是说，程序每运行一次，要计算多道题。

对多用例输入，通常会先输入要计算的用例的个数，然后依次输入每个测试用例的输入数据，但程序并不需要等到所有的测试用例都计算完后再输出所有测试用例的计算结果，而是可以读入一个测试用例，输出一个结果，再读入一个测试用例，再输出一个结果。因此对多用例输入的试题，可以用这样的输入模式：

以C++为例：

int n;

cin >> n;

for (int i=0; i<n; i++)

{

    读入测试用例数据

    计算

    输出计算结果

}

2、单测试用例输入的结束判断
对单用例输入，最主要的问题是如何知道输入什么时候结束。

有些试题会指定某种特殊的输入值作为输入的结束标志，这种情况比较容易处理，只须在读入后，判断一下读入的内容是否为约定结束值即可。

有些试题并不指定特殊的输入值，而是以EOF（文件结束标志）作为结束标志。如果从文件流读入，当读到文件尾时，输入返回EOF。

如果从键盘读入时，在Windows的终端中，是以Ctrl+Z表示EOF；在Linux下是Ctrl + D 表示结束。对于这种情况，可以用这样的输入模式：

以C++为例：

int m, n; // 假设要连续输入一组整数对

while (cin>>m>>n)

{

    处理整数对(m, n)

}

以C语言为例：

int m, n;

while (scanf(“%d%d”, &m, &n)==2)

{

    处理整数对(m, n)

}

三、数据结构的设计
很多试题中已经给出了数据量的上限，因此可以很方便地以数组的方式定义数据结构。但也要注意到有些题目中没有明确指出数据上限时，切不可盲目定义数组大小。

例如在题hduoj 1070（多项式求和）中，并未说明输入多项式的项数，对这种情况就不宜用数组方式来表示多项式了——除非你的运气足够好，所开辟的数组大小能够经受所有的测试用例的考验。

除了使用一般的数组或链表结构外，对使用C++的选手来说，STL也是一大利器，充分运用可以有效提高编程的效率和正确性。

全排列函数next_permutation

STL 中专门用于排列的函数（可以处理存在重复数据集的排列问题）

 1 头文件：#include <algorithm>
 2 
 3 using namespace std;
 4 
 5 调用： next_permutation(start, end);
 6 
 7 注意：函数要求输入的是一个升序排列的序列的头指针和尾指针.
 8 
 9 用法：
10 
11 // 数组
12 
13 int a[N];
14 
15 sort(a, a+N);
16 
17 next_permutation(a, a+N);
18 
19 // 向量
20 
21 vector<int> ivec;
22 
23 sort(ivec.begin(), ivec.end());
24 
25 next_permutation(ivec.begin(), ivec.end());
26 
27 例子：
28 
29 vector<int> myVec;
30 
31 // 初始化代码
32 
33 sort(myVec.begin(),myVec.end());
34 
35 do{
36 
37 for (i = 0 ;i < size;i ++ ) cout << myVec[i] << " 	 " ;
38 
39 cout << endl;
40 
41 }while (next_permutation(myVec.begin(), myVec.end()));

四、测试用例的考虑
在试题中通常会给出测试用例的样例，这通常会被我们用来测试自己的程序，而且很多选手往往在正确计算出测试用例样例时，会认为自己的程序是正确的。

其实测试用例的样例只是测试用例的个例，实际用于测试的测试用例往往会涵盖各种极限情况和边界情况，而且有时测试用例的数量还会比较大，甚至会重复测试同 一个测试用例。因此我们的程序能够通过样例测试，未必能够通过所有的测试用例的测试，一方面要全面考虑所有可能的极限情况和边界情况，一方面程序要有足够 的效率。

未完待续，，，