竞赛编程注意事项

C＋＋是一门庞大的语言，大多数语言特性和库函数在算 法竞赛中都是用不到（或者可以避开）的。而且算法竞赛有它自身的特点，即使对于资深C ＋＋程序员来说，如果缺乏算法竞赛的经验，也很难总结出一套适用于算法竞赛的知识点和 实践指南。

提示1-4：在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不 要等待用户按键，因为输入输出过程都是自动的，没有人工干预。 

在一般情况下，你的程序不能直接读取键盘和控制屏幕：不要在算法竞赛中使用 getch()、getche()、gotoxy()和clrscr()函数（早期的教材中可能会介绍这些函数）。 

提示1-5：在算法竞赛中不要使用头文件conio.h，包括getch()、clrscr()等函数。 

最后，最容易忽略的是输出的格式：在很多情况下，输出格式是非常严格的，多一个或 者少一个字符都是不可以的！

提示1-6：在算法竞赛中，每行输出均应以回车符结束，包括最后一行。

除非特别说 明，每行的行首不应有空格，但行末通常可以有多余空格。另外，输出的每两个数或者字符 串之间应以单个空格隔开。 总结一下，算法竞赛的程序应当只做3件事情：读入数据、计算结果、打印输出。不要 打印提示信息，不要在打印输出后“暂停程序”，更不要尝试画图、访问网络等与算法无关的 任务。

提示1-7：尽量用const关键字声明常数。

提示1-8：赋值是个动作，先计算右边的值，再赋给左边的变量，覆盖它原来的值。

提示1-9：printf的格式字符串中可以包含其他可打印符号，打印时原样输出。

提示1-10：算法竞赛的题目应当是严密的，各种情况下的输出均应有严格规定。如果 在比赛中发现题目有漏洞，应向相关人员询问，尽量不要自己随意假定。

提示1-11：赋值a=b之后，变量a原来的值被覆盖，而b的值不变。

提示1-12：可以通过手工模拟的方法理解程序的执行方式，重点在于记录每条语句执 行之后各个变量的值。

提示1-13：交换两个变量的三变量法适用范围广，推荐使用。

提示1-14：算法竞赛是在比谁能更好地解决问题，而不是在比谁写的程序看上去更高 级。

提示1-15：if语句的基本格式为：if（条件）语句1；else语句2。

提示1-16：if语句的条件是一个逻辑表达式，它的值可能为真，也可能为假。单个整数 值也可以表示真假，其中0为假，其他值为真。

提示1-17：C语言中的逻辑运算符都是短路运算符。一旦能够确定整个表达式的值，就 不再继续计算。

      如果a为真，则无论b的值如何，a||b均为真。换句话说，一旦 发现a为真，就不必计算b的值。C语言正是采取了这样的策略，称为短路（short-circuit）。

提示1-18：算法竞赛的目标是编程对任意输入均得到正确的结果，而不仅是样例数 据。

提示1-19：如果有多个并列、情况不交叉的条件需要一一处理，可以用else if语句。

提示1-20：适当在程序中编写注释不仅能让其他用户更快地搞懂你的程序，还能帮你 自己理清思路。

一是重视实验。哪怕不理解背后的道理，至少要清楚现象。例如，读者若亲自完成了本 章的探索性实验和上机练习，一定会对整数范围、浮点数范围和精度、特殊的浮点值、 scanf、空格、TAB和回车符的过滤、三角函数使用弧度而非角度等知识点有一定的了解。这 些内容都没有必要死记硬背，但一定要学会实验的方法。这样即使编程时忘记了一些细节， 手边又没有参考资料，也能轻松得出正确的结论。 二是学会模仿。本章始终没有介绍“#include＜stdio.h＞”语句的作用，但这丝毫不影响读 者编写简单的程序。这看似是在鼓励读者“不求甚解”，但实为考虑到学习规律而作出的决 策：初学者自学和理解能力不够，自信心也不够，不适合在动手之前被灌输大量的理论。如 果初学者在一开始就被告知“stdio是standard I/O的缩写，stdio.h是一个头文件，它在XXX位 置，包含了XXX、XXX、XXX等类型的函数，可以方便地完成XXX、XXX、XXX的任务； 但其实这个头文件只是包含了这些函数的声明，还有一些宏定义，而真正的函数定义是在库 中，编译时用不上，而在连接时……”多数读者会茫然不知所云，甚至自信心会受到打击， 对学习C语言失去兴趣。正确的处理方法是“抓住主要矛盾”——始终把学习、实验的焦点集 中在最有趣的部分。如果直观地解决方案行得通，就不必追究其背后的原理。如果对一个东 西不理解，就不要对其进行修改；如果非改不可，则应根据自己的直觉和猜测尝试各种改 法，而不必过多地思考“为什么要这样”。 当然，这样的策略并不一定持续很久。当学生有一定的自学、研究能力之后，本书会在 适当的时候解释一些重要的概念和原理，并引导学生寻找更多的资料进一步学习。要想把事 情做好，必须学得透彻，但没有必要操之过急。

提示2-1：for循环的格式为：for（初始化；条件；调整）循环体；

提示2-2：尽管for循环反复执行相同的语句，但这些语句每次的执行效果往往不同。

提示2-4：建议尽量缩短变量的定义范围。例如，在for循环的初始化部分定义循环变 量。

提示2-13：long long在Linux下的输入输出格式符为％lld，但Windows平台中有时 为％I64d。为保险起见，可以用后面介绍的C＋＋流，或者编写自定义输入输出函数。

提示2-16：要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在 每步计算之后对n取余，结果不变。

提示2-17：可以使用time.h和clock（）函数获得程序运行时间。常数 CLOCKS_PER_SEC和操作系统相关，请不要直接使用clock（）的返回值，而应总是除以 CLOCKS_PER_SEC。

   printf("Time used = %.2f\\n", (double)clock() / CLOCKS_PER_SEC);

输入“2 8 3 5 1 7 3 6”，按Enter键，但未显示结果。难道程序速度太慢？ 其实程序正在等待输入。还记得scanf的输入格式吗？空格、TAB和回车符都是无关紧要的， 所以按Enter键并不意味着输入的结束。那如何才能告诉程序输入结束了呢？ 提示

2-19：在Windows下，输入完毕后先按Enter键，再按Ctrl＋Z键，最后再按Enter 键，即可结束输入。在Linux下，输入完毕后按Ctrl＋D键即可结束输入。

提示2-21：请在比赛之前了解文件读写的相关规定：是标准输入输出（也称标准I/O， 即直接读键盘、写屏幕），还是文件输入输出？如果是文件输入输出，是否禁止用重定向方 式访问文件？ 

多年来，无数选手因文件相关问题丢掉了大量分数。一个普适的原则是：详细阅读比赛 规定，并严格遵守。

例如，输入输出文件名和程序名往往都有着严格规定，不要弄错大小 写，不要拼错文件名，不要使用绝对路径或相对路径。

 例如，如果题目规定程序名称为test，输入文件名为test.in，输出文件名为test.out，就不 要犯以下错误。 

错误1：程序存为t1.c（应该改成test.c）。 

错误2：从input.txt读取数据（应该从test.in读取）。 

错误3：从tset.in读取数据（拼写错误，应该从test.in读取）。 

错误4：数据写到test.ans（扩展名错误，应该是test.out）。 

错误5：数据写到c：\\\\contest\\\\test.out（不能加路径，哪怕是相对路径。文件名应该只有8 个字符：test.out）。

提示3-2：在算法竞赛中，常常难以精确计算出需要的数组大小，数组一般会声明得稍 大一些。在空间够用的前提下，浪费一点不会有太大影响。

提示3-4：比较大的数组应尽量声明在main函数外，否则程序可能无法运行。

提示4-3：如果在执行函数的过程中碰到了return语句，将直接退出这个函数，不去执 行后面的语句。相反，如果在执行过程中始终没有return语句，则会返回一个不确定的值。 幸好，-Wall可以捕捉到这一可疑情况并产生警告。

提示4-4：在算法竞赛中，请总是让main函数返回0。

提示4-13：C语言的变量都是放在内存中的，而内存中的每个字节都有一个称为地址 （address）的编号。每个变量都占有一定数目的字节（可用sizeof运算符获得），其中第一 个字节的地址称为变量的地址。

提示4-14：用int* a声明的变量a是指向int型变量的指针。

赋值a = &b的含义是把变量 b的地址存放在指针a中，表达式*a代表a指向的变量，既可以放在赋值符号的左边（左 值），也可以放在右边（右值）。 注意：*a是指“a指向的变量”，而不仅是“a指向的变量所拥有的值”。理解这一点相当重 要。例如，*a = *a + 1就是让a指向的变量自增1。甚至可以把它写成(*a)++。注意不要写 成*a++，因为“++”运算符的优先级高于“取内容”运算符“*”，实际上会被解释成*(a++)。

提示4-15：千万不要滥用指针，这不仅会把自己搞糊涂，还会让程序产生各种奇怪的 错误。

提示4-16：以数组为参数调用函数时，实际上只有数组首地址传递给了函数，需要另 加一个参数表示元素个数。除了把数组首地址本身作为实参外，还可以利用指针加减法把其 他元素的首地址传递给函数。

提示5-2：C＋＋能编译大多数C语言程序。虽然C语言中大多数头文件在C＋＋中仍然 可以使用，但推荐的方法是在C头文件之前加一个小写的c字母，然后去掉.h后缀。

还有一个新内容：using namespace std。这是什么意思呢？C＋＋中有一个“名称空 间”（namespace）的概念，用来缓解复杂程序的组织问题。例如张三写了一个函数叫 my_good_function（意思是“我的优秀函数”），李四也写了这样一个函数，但作用和张三的不 同。如果有一天需要把他们的程序合在一起用，就会出问题：函数不能重名。虽然后面会讲 到C＋＋支持函数重载，但如果这两个函数的参数类型也完全相同，则是不能重载的。一个 解决方案是分别把函数写在各自的名称空间里，然后就可以用zhang3：my_good_function() 和 li4：my_good_function( )这样的方式进行调用了。 基于这样的考虑，头文件iostream和algorithm里定义的内容放在std名称空间里。如果代 码和该名称空间里的内容不重名，就可以用using namespace std的方法把std里的名字导入默认 空间(3)。这样就可以用cin代替std：：cin，cout代替std：：cout，min代替std：：min了。不信 的话，你可以把这行语句注释掉，再编译一次试试。

提示5-3：C＋＋中可以使用流简化输入输出操作。标准输入输出流在头文件iostream 中定义，存在于名称空间std中。如果使用了using namespace std语句，则可以直接使用。 最后还有一个细节：声明数组时，数组大小可以使用const声明的常数（这在C99中是不 允许的）。在C＋＋中，这种写法更为推荐，因此本书后面的代码中一律采用这样的写法， 而不是用#define声明常数。

提示5-4：C＋＋中的引用就是变量的“别名”，它可以在一定程度上代替C中的指针。例 如，可以用“传引用”的方式让函数内直接修改实参。

C＋＋提供了一个新的string类型，用来替代C语言中的字符数组。用户仍然可以继续用 字符数组当字符串用，但是如果希望程序更加简单、自然，string类型往往是更好的选择。 例如，C＋＋的cin/cout可以直接读写string类型，却不能读写字符数组；string类型还可以像 整数那样“相加”，而在C语言里只能使用strcat函数。 提示5-5：C＋＋在string头文件里定义了string类型，直接支持流式读写。string有很多 方便的函数和运算符，但速度有些慢。

提示5-6：可以把string作为流进行读写，定义在sstream头文件中。 虽然string和sstream都很方便，但string很慢，sstream更慢，应谨慎使用(6)。

5.2.2 不定长数组：vector vector就是一个不定长数组。不仅如此，它把一些常用操作“封装”在了vector类型内部。 例如，若a是一个vector，可以用a.size( )读取它的大小，a.resize( )改变大小，a.push_back( )向 尾部添加元素，a.pop_back( )删除最后一个元素。 vector是一个模板类，所以需要用vectora或者vectorb这样的方式来声明一 个vector。Vector是一个类似于inta[]的整数数组，而vector就是一个类似于 stringa[ ]的字符串数组。vector看上去像是“一等公民”，因为它们可以直接赋值，还可以作为 函数的参数或者返回值，而无须像传递数组那样另外用一个变量指定元素个数。