一个好的取胜之道是制定在竞赛中指导你行动的策略。无论是在好的情况下还是在坏的情况下,它将帮助你决定你的行动。用这种方法你可以在竞赛中将时间花费在解决编程问题上而不是试图决定下一步该干什么…这有点像预先计算好你面对各种情况的反应。
心理上的准备也很重要。
竞赛中的策略
首先通读所有的题目;草拟出算法,复杂度,数量,数据结构,微妙的细节,…
- 集体讨论所有可能的算法 —— 然后选择最“笨”但却可行的算法。(注:请注意这一点,对参赛选手来说获奖就是唯一目的)
- 进行计算!(空间和时间复杂度,并且加上实际期望和最坏情况下的数量)
- 试图证明该算法错误——使用特殊的(退化的)测试数据。
- 将问题排序:根据你所需付出的努力,将能够最快解决的问题排在前面。(答题的次序为:以前做过的,容易的,不熟悉的,难的)
编写程序解决一个问题 —— 对每一道题而言,一次一道题
- 确定算法
- 构造特殊情况的测试数据
- 写出数据结构
- 编写并测试输入子程序(编写额外的子程序来显示数据输入的正确性)
- 编写并测试输出子程序
- 逐步细化:通过写注释来刻划程序的逻辑轮廓
- 一个部分一个部分地填充并调试代码
- 完成代码使其正常运转,并验证代码的正确性(使用一般情况的测试数据)
- 试图证明代码错误——使用特殊情况的测试数据来验证代码正确性
- 逐渐优化——但足够了即可,并且保存所有的版本(使用最坏情况的(即运行时间长的)测试数据来计算出实际运行时间)
时间安排策略和“故障控制”方案
制定一个计划决定在各种(可预测的)故障发生时的行动;想象你可能遇到的问题并计算出你所希望做出的反应。核心问题是:“你何时花费更多的时间在调试程序上,你何时放弃并继续做下一题?”。考虑以下问题:
- 你已经花费了多长时间来调试它?
- 你可能有什么样的BUG?
- 你的算法有错吗?
- 你的数据结构需要改变吗?
- 你是否对什么地方可能会出错有一些头绪?
- 花费较短的时间(20分钟)在调试上比切换去做其他别的事要好;但是你或许能够在45分钟内解决另一个问题(A short amount (20 mins) of debugging is better than switching to anything else; but you might be able to solve another from scratch in 45 mins.)
- 你何时返回到一个你先前放弃的问题?
- 你何时花费较多的时间优化一个程序,你何时放弃当前优化工作而切换去作其他事?
- 从这点考虑出去(Consider from here out)——忘记先前的努力,着眼于将来:你如何才能就你目前所有的抓住下一个小时。
在你上交你的答案之前列出一个校验表:
- 在竞赛结束前五分钟结束编写代码(Code freeze five minutes before end of contest)。
- 将所有的声明关闭。
- 将调试输出关闭。
- 确认输入输出文件名正确。
- 确认输入输出格式正确。
- 重新编译并再测试一次。
- 将文件以正确的文件名复制到正确的位置(软盘)。
提示和技巧
- 如果可以就用暴力法(即穷举法)解决 (注:居然将这条作为技巧,可见竞赛的目的就是获奖,为此要“不择手段”。)
- KISS(=Keep
全面地考虑问题
在编程序时常常会遇到这样的问题:一道很简单的题目,编出的程序却错了很多测试点。这其中的主要原因是由于考虑问题不全面,只想到了一些普通的情况,而遗漏了很多特殊的地方。
下面通过几个例子来进行讨论。
1.项链(IOI’93第一题)
由n(n≤100)个珠子组成一个项链,珠子有红、蓝、白三种颜色,各种颜色的珠子的安排顺序由输入文件任意给定。
图1.1可看作由字符b(代表蓝色珠子)和字符r(代表红色珠子)所组成的字符串。假定从项链的某处将其剪断,把它摆成一直线,从一端收集同种颜色珠子(直到遇到另一种颜色的珠子时停止)。然后再从另一端重复上述过程(请注意,这一端珠子的颜色不一定和另一端珠子的颜色相同)。
brbrrrbbbrrrrbrrbbrbbbbrrrrb
图 1.1
请选择项链被剪断的位置,目标是使两端各自颜色相同的珠子数目之和最大。例如,对于上图(只有红蓝两种颜色),最大值M是8,断点位置在珠子9和珠子10之间,或珠子24和珠子25之间。
项链中可以有三种颜色用b(蓝)、r(红)和w(白)表示。白色既可看成是红色,又可看成蓝色。
(1)一个ASCII文件NECKLACE.DAT中的内容:该文件中每一行代表某个项链中各种颜色珠子的配置。把输出内容写入ASCII输出文件NECKLACE.SOL中。
作为举例,输入文件的内容可以是:
brbrrrrbbbbrrrrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrb
(2)对于给定的每个项链的配置,求出收集到的珠子数的最大值M及相应的断点位置(注意可能存在多个位置)。
(3)在输出文件NECKLACE.SOL中写入收集到的珠子数的最大值M及断点位置。
例如:
brbrrrbbbrrrrrbbrbbbbrrrrb
8 between 9 and 10
bbwbrrrwbrbrrrrrb
10 between 16 and 17
作为竞赛的第一题,这道题目显然是比较简单的题目。它只包含两个步骤:剪断项链和收集同颜色的珠子。例如下面的一条项链(a)从N=3处断开变为项链(b)。这个操作只需要将前N个珠子移到后边即可。
brb | rrwb ------> rrwbbrb (a) (b)
现在只剩下收集同颜色的珠子这一步,根据上面的例子我们很容易写出下面的程序。
用变量c来记录最左边珠子的颜色;
Left:=0;
FOR i:=1 TO 项链长度 DO
IF 左数第i个珠子的颜色与c相同
THEN Inc(Left)
ELSE Break;
这样变量Left中存放的就是从左边收集到的珠子的数目,同理可求得从右边收集到的珠子的数目Right,则所求的值为Lett+Right。这个程序显然能通过上面的例子,由于这是一道简单的题目,谁也不想在它上面多费时间,往往做到此为止。可是如果仔细想想, 再举几个例子,就会发现错误。上面的那条项链断开后左有两个珠子为红色和蓝色,在题目中这两种颜色的珠子都比较”普通”,只有白色的珠子比较”特殊”。所以应举一个断开后左右两端有白色珠子的例子。还是上面那条项链入N=6处断开。
brbrrw| b——->bbrbrrw
正确答案应是收集到5个珠子:左边2个,有边3个。而上面的程序得到的结果却是3个:左边2个,右边1个。错误就在于没有考虑到左右两端有白色珠子的情况。一种较容易的解决方案是先将左有两端的白色珠子均取下,记其数目为Other,再用上面的程序来求,结果为Left十Right十Other。我们解决了左右两端出现白色珠子的情况,还有没有别的特殊情况呢?一个真正”特殊”的项链不应包含所有颜色的珠子,最好只包含一种颜色。 如下面的项链是由l0个红色的珠子组成。
rrrrrrrrrr
用我们的程序得出的结果是20个,显然是不对的。因为题目中要求是收集珠子而不是数珠子,所以最后得到的总数不应超过珠子的总数。这虽然只是一个字眼的问题,却使当年中国队的选手失了不少分。一个简单的改正措施是判断最后的结果是否大于珠子总数,如果是则输出珠子的总数即可。
虽然项链这道题比较简单,却很难”简单”地得到满分,最容易出的错误就是考虑的不全面。
2.多项式加法
由文件输入两个多项式的各项系数和指数,编程求出它们的和,并以手写的习惯输出此多项式。
要求:
(1)多项式的每一项axb用axb的格式输出。
(2)两个多项式在文件中各占一行,每行有2m个数,依次为第一项的系数,第一项的指数,第二项的系数,第二项的指数……
例如输入文件为:
l 2 3 0
-l 1
输出:
x2-x+3
此题是一道大学生竞赛的题目,很多人只用了很短的时间就编出程序。但最后测试的结果却令他们很惊讶:通过的数据还不到一半!他们犯的错误归根结底就是考虑得不够全面。
此题对于多项式相加的过程很简单,只要找出幂次相同的项相加即可。关键在于题目中要求用符合手写的习惯输出结果。何为手写的习惯呢?例如多项式3x2-x中就有很多手写的习惯。我们不会将其写成3x2一lx1+O。因为首先当某项系数为1时,我们习惯于不写系数;其次对于一次项我们也要省略指数;还有我们从来不写出系数为0的项。一个简单的多项式就有这么多的手写习惯,我们已经感觉到了要把这题全面地做出很不容易。虽然我们平时总在写多项式,但是谁也不会留心我们写多项式时的习惯。我们写多项式的习惯究竟有哪些呢?
(1)首先我们考虑对于多项式中的任一项axb它有多少手写习惯:
- 当a=0时,此项省去不写;
- 当a=l时,省去a;
- 当a=-1时,系数只写一个负号’-‘;
- 当b=0时,省去x和b;
- 当b=l时,省去b;
- 当a<一1时,省去此项前面的加号(首项除外)。
我们一口气写了这么多条规则,每一条看起来都很正确,但合在一起是否还正确呢?当a=l或-1时要省去其中的数字1,这是针对一般情况而言。如果b=0,则数字1就不应当省去。所以我们不仅要单独考虑a和b,而且要将其和起来考虑。
(2)其次对于整个多项式有哪些规则呢?
- 多项式的首项系数前不应有加号’+’;
- 如果一个多项式为零多项式,则应写出数字’0’。
现在看起来这道题并不是一道很容易的题目。它需要一个人在很短的时间内能全面地总结出上述那么多规则。这对一个人的全面考虑问题的能力是一个很好的检验。
3.求最长的公共子串(NOI’93第一题)
求N个字符串的最长公共子串,N<20,字符串长度不超过255。例如N=3,由键盘 依次输入3个字符串为
What is local bus ?
Name some local buses.
local bus is a high speed I/O bus close to the processor.
则最长公共子串为”local bus”。
此题也是作为第一题出现,同样有很多入在此题上失分。我们都做过求n个数最大公 约数的问题,在那道题中求3个数的最大公约数时,可以先求两个数的最大公约数,再将此数与第三个数求一次最大公约数。有人从那道题中得到”启发”,设s(p,q)为字符串p 和q的最长公共子串,则p、q、r的最长公共子串为s(s(p,q),r)。这样只需编写一个求两个字符串的最长公共子串的过程即可。但这种方法对不对呢?看看下面的例子。
三个字符串分别为’abc’、’cab’、’c’,则s(p,q)=’ab’,s(s(p,q).r)=”。事实上这三个字符串有公共子串’c’。显然上面的算法是错误的,原因在于没有考虑到本题与求最大公约数那道题在性质上的不同之处。最大公约数可以由局部解得到全局解,而本题却不能。正确的做法是列举出其中一个字符串的所有子串,找出其中最长的而且是公共的子串。
FOR i:=l TO 第一个字符串的长度 DO
FOR j:=i TO 第一个字符串的长度 DO
IF (第i个字符到第j个字符的子串为公共子串)AND(j-i+1>当前找到的最长公共子串的长度max)
THEN
BEGIN
max:=j-i+l;
最长公共子串:=此子串;
END;
为了提高效率,我们可以将最短的字符串作为第一个字符串。此题需要考虑的并不像多项式加法那道题那么多,但是它提醒我们在不清楚题目的性质之前,不能滥用以前的方法。
4.可重复排列(NOI’94第一题)
键盘输入一个仅由小写字母组成的字符串,输出以该串中任取M个字母的所有排列及排列总数(输入数据均不需判错)。
此题是由全排列问题转变而来,不同之处在于:一个字符串中可能有相同的字符,导致可能出现重复的排列。例如从字符串’aab’中取2个字符的排列只有三种:’aa’、’ab’、’ba’。如何去掉那些可能重复的排列呢?一种想法就是每产生一种不同的排列就记录下来,以便让以后产生的排列进行比较判重。这种想法显然没有考虑到随着字符串长度的增加,排列将会多得无法记录,而且这种判重方法在效率上也会很低。最好有一种方法能在产生排列的过程中就能将重复的去掉。先看一看全排列的递归过程
- PROCEDURE Work(k);
- BEGIN
高性能计算机 (2001年国家集训队冬令营试题)
问题描述
现在有一项时间紧迫的工程计算任务要交给你–国家高性能并行计算机的主管工程师–来完成。为了尽可能充分发挥并行计算机的优势,我们的计算任务应当划分成若干个小的子任务。
这项大型计算任务包括A和B两个互不相关的较小的计算任务。为了充分发挥并行计算机的运算能力,这些任务需要进行分解。研究发现,A和B都可以各自划分成很多较小的子任务,所有的A类子任务的工作量都是一样的,所有的B类子任务也是如此(A和B类的子任务的工作量不一定相同)。A和B两个计算任务之间,以及各子任务之间都没有执行顺序上的要求。
这台超级计算机拥有p个计算节点,每个节点都包括一个串行处理器、本地主存和高速cache。然而由于常年使用和不连贯的升级,各个计算节点的计算能力并不对称。一个节点的计算能力包括如下几个方面:
- 就本任务来说,每个节点都有三种工作状态:待机、A类和B类。其中,A类状态下执行A类任务;B类状态下执行B类任务;待机状态下不执行计算。所有的处理器在开始工作之前都处于待机状态,而从其它的状态转入A或B的工作状态(包括A和B之间相互转换),都要花费一定的启动时间。对于不同的处理节点,这个时间不一定相同。用两个正整数 和分别表示节点i转入工作状态A和工作状态B的启动时间(单位:ns)。
- 一个节点在连续处理同一类任务的时候,执行时间–不含状态转换的时间–随任务量(这一类子任务的数目)的平方增长,即:
若节点i连续处理x个A类子任务,则对应的执行时间为: ;
类似的,若节点i连续处理x个B类子任务,对应的执行时间为: 。
其中, 和 是系数,单位是ns。 。
任务分配必须在所有计算开始之前完成,所谓任务分配,即给每个计算节点设置一个任务队列,队列由一串A类和B类子任务组成。两类子任务可以交错排列。
计算开始后,各计算节点分别从各自的子任务队列中顺序读取计算任务并执行,队列中连续的同类子任务将由该计算节点一次性读出,队列中一串连续的同类子任务不能被分成两部分执行。
编程任务
现在需要你编写程序,给这p个节点安排计算任务,使得这个工程计算任务能够尽早完成。假定任务安排好后不再变动,而且所有的节点都同时开始运行,任务安排的目标是使最后结束计算的节点的完成时间尽可能早。
输入输出
输入文件名是hpc.in。
文件的第一行是对计算任务的描述,包括两个正整数 和 ,分别是A类和B类子任务的数目,两个整数之间由一个空格隔开。
文件的后面部分是对此计算机的描述:
文件第二行是一个整数p,即计算节点的数目。
随后连续的p行按顺序分别描述各个节点的信息,第i个节点由第i+2行描述,该行包括下述四个正整数(相邻两个整数之间有一个空格):
输出文件名是hpc.out。其中只有一行,包含有一个正整数,即从各节点开始计算到任务完成所用的时间。
样例
设输入文件hpc.in为
对应的输出文件hpc.out为
93