项链(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
 IF k=m+l THEN 打印结果
          ELSE FOR i:=1 TO 字符串长度n DO
             IF (i<>e[l],e[2],e[k-1]) THEN
              BEGIN
               e[k]:=i;
               Work(k+l);
              END;
END;
让我们来分析产生重复的原因。考虑从字符串。'aab'中取2个字符的排列。当e[1]从l变到2时，字符串中的字符却没有变，都是'a'。这样我们只要在改变e[k]时，判断其对应的字符是否也改变。即在上面的过程的循环中加一句判断(设字符串为s):IF s<> s[e[k]] THEN …; 这当然只是一个粗略的想法，我们仅仅用上面的例子就能发现问题: 程序在对e[k]的每一次赋值之前都要进行一次判断，而不是我们预想的在改变e[k]时才进行判重。我们用一个布尔型的局部变量First来记录是否是对e[k]进行第一次赋值。修改后的程序如下:

PROCEDURE Work(k);
BEGIN
First:=True;
IF k=m+l THEN 打印结果
　
ELSE FOR i:=1 TO 字符串长度n DO
IF (i<>e[l],e[2],e[k-1]) THEN
BEGIN
First:=false;
e[k]:=i;
Work(k+l);
END;
END;
很多选手的程序到此就为止了，可是它还有一个致命的错误:我们在判重时假定这个字符串中的字符已经排好顺序，即相同的字符已经连在一起。事实上并不是这样，输入的字符串中的字符排列是任意的，需要我们在递归之前作一次排序的初始化才能保证程序运行得正确。可见虽然本题的难点是在递归过程中，但是那些简单的初始化却是程序最容易忽略，最容易出错的部分。

5·删除多余括号(IOI'94国家队选拔赛第一题)
键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。

例:输入表达式

a+(b+c)

(a*b)+c/d

a+b/(c-d)

应输出表达式

a+b+c

a*b+c/d

a+b/(c一d)

注意输入a+b时不能输出b+a。

表达式以字符串输入，长度不超过255。输入不要判错。

所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式化简。

同多项式加法一样，此题要求的也是一个我们平时很习惯但却没有注意的规则:去掉多余的括号。哪些括号是多余的呢?这要根据紧挨着括号前后的运算符号和括号中最后一个运算符号来决定。例如表达式a+(b*c+d)-e中，括号前的符号为"+"，括号后的符号为"-"，括号中最后一个运算符号为"+"，所以括号是多余的。总结括号中最后一个运算符号为"+"、"-"、"*"，"/"时，括号前、后为何运算符号时括号是多余的，我们很容易得出表1.1。

表1.1 多余的括号满足的条件

括号前的符号  括号中的符号  括号后的符号  
+  +  +、-  
+  -  +、-  
+、-、*  *  +、-、*、/  
+、-、*  /  +、-、*、/  

　

上表只是对一般情况的分析，显然是很不全面的。首先括号前，括号中和括号后都可能无运算符号，例如表达式((a))+b；其次变量前还可能带有负号，例如表达式(-a)+ (-b)中的括号一个是多余的，一个不是多余的。还有一些其它的情况如表达式只有括号无任何变量等需要考虑。此题留给大家自己去完成。注意多用一些特殊的数据来测试自己的程序。大家也可以试着用表达式树的方法来做此题。

6.合并表格(NOI'93第二题)
在两个文本文件中各存有一个西文制表符制成的未填入任何表项的表结构，分别称之为表1和表2，要求编程将表1和表2按下述规则合并成表3。

规则:表1在上表2在下，表1与表2在左边框对齐，将表1的最底行与表2的最顶行合并。

例如，3张表见图1.2。

　 　 　 　
　 　 　 　
 　 　 　
    
　 　 　 　
　 　 　
 
表1  表2  表3  

图1.2

编程要求:

(l)程序应能从给定的文本文件中读入两个源表并显示。

(2)若源表有错，应能指出其错(错误只出在表1的最底行和表2的第一行)。

(3)将表1和表2按规则合并成表3，并显示之。

(4)所有制表符的ASCII码应由选手自己从给出的示例文件中截取。

我们把此题的分析留给读者去独立完成。

"千里之堤，毁于蚁穴"。一些程序往往不是错在算法上，而是错在考虑得不全面上。希望通过以上几个例子，能使大家对此引起重视，在以后的编程中多加注意，避免不应有的遗憾。

　

本文摘自《1993-1996美国计算机程序竞赛试题与解析》

有兴趣一起研究的朋友门多来这里

OK