全国青少年信息学奥林匹克联赛培训习题与解答(中学高级本)

全国青少年信息学奥林匹克联赛培训习题与解答

（中学高级本）

习题篇与解析篇

第一章回溯法

1.1马拦过河卒

1.2出栈序列统计

1.3算24点

1.4冗余依赖

1.5走迷宫

1.6单向双轨道

1.7组合的输出

1.8售货员的难题

1.9驾车旅游

1.10关路灯

第二章递规与递推

2.1遍历问题

2.2产生数

2.3出栈序列统计

2.4计数器

2.5诸侯安置

2.6括号序列

2.7新汉诺塔

2.8排序集合

2.9青蛙过河

2.10电话号码

2.11编码

第三章贪心法

3.1排队接水

3.2智力大冲浪

3.3取火柴游戏

3.4加」二生产调度

3.5最大乘积

3.6种树

3.7WP

3.8马拉松接力赛

3.9线性存储问题

3.10扇区填数

第四章分治

4.1取余运算

4.2地毯填补问题

4.3平面上的最接近点对

4.4求方程的根

4.5小车问题

4.6黑白棋子的移动

4.7麦森数（NOIP20Q3）

4.8旅行家的预第（NOIP1999）

4.9飞行计划

第五章图

5.1医院设置

5.2工程规划

5.3服务器储存信息问题

5.4间谍网络（AGE）

5.5宫廷守卫

5.6K-联赛

5.7机器调度

5.8公路修建

5.9速度限制

第六章树

6.1排序二叉树

6.2树的重量

6.3信号放大器

6.4，叨问”术馆

6.5聚会的快乐

6.6重建道路

6.7有线电视网

第七章搜索

7.1最多因子数

7.2黑白棋游戏

7.3纵横填字游戏

7.4魔术数字游戏

7.5M

7.6一:维扫描

7.7拼字游戏

7.8公路修建

7.9单词游戏

第八章动态规划

8.1字串距离

8.2血缘关系

8.3尼克的任务

8.4书的复制

8.5多米诺骨

8.6平板涂色

8.7三角形牧场

8.8

第九章数学问题

9.1多项式展开系数

9.2两数之和

9.3盒子与球

9.4取数游戏

9.5磁盘碎片整理

9.6欧儿里德的游戏

9.7百事世界杯之旅

9.8幽

9.9班级聚会

第十章杂题

10.1排序

10.2木棍加工

10.3三角形

10.4多边形面积

10.5网线切割

10.6最接近的分数

10.7切孔机

10.8栓狗方案

10.9城市街道交通费系统

10.10魔鬼之城

10.11可见矩形

第一章回溯法

1.1马拦过河卒

源程序名knight.???(pas,c,cpp)

可执行文件名knight.exe

输入文件名knight.in

输出文件名knight.out

【问题描述】

棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘

上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦

过河卒

棋盘用坐标表示，A点(0.0)、B点(n,m)(n,m为不超过15的整数)，同样马的位置坐标是需要给出

的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一

步马走一步。

【输入】

一行四个数据，分别表示B点坐标和马的坐标。

【输出】

一个数据，表示所有的路径条数。

【样例】

knight.inknight.out

66336

【算法分析】

从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。

最后输出所有的路径数。这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，

但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推

公式更合适，详见后面的递推章节。

1.2出栈序列统计

源程序名stack1.???(pas,cpp)

可执行文件名stackl.exe

输入文件名stack1.in

输出文件名stackLout

【问题描述】

栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知

道栈的操作有两•种：push和pop,前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种

操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n,计算并输出由操作数序

列1,2,n,经过一系列操作可能得到的输出序列总数。

【输入】

一个整数n(K=n<=15)

【输出】

一个整数，即可能输出序列的总数目。

【样例】

stack1.instack1.out

35

【算法分析】

先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移

一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。

用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈

则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计

数次(这也是递归调用结束的条件)。

1.3算24点

源程序名point24.???(pas,c,cpp)

可执行文件名point24.exe

输入文件名point24.in

输出文件名point24.out

【问题描述】

几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲.在中国我们把这种游戏称为“算24点”。

您作为游戏者将得到4个卜9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运

算，要求运算结果等于24。

您可以使用的运算只有：+,*，/,您还可以使用（）来改变运算顺序。注意：所有的中间结果须

是整数，所以一些除法运算是不允许的（例如，（2*2）/4是合法的，2*（2/4）是不合法的）。下面我们给出一

个游戏的具体例子：

若给出的4个操作数是：1、2,3、7,则一种可能的解答是1+2+3*7=24。

【输入】

只有一行，四个1到9之间的自然数。

【输出】

如果有解的话，只要输出一个解，输出的是三行数据，分别表示运算的步骤。其中第一行是输入的两

个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；

第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。

如果没有解则输出“Noanswer!”

【样例】

point24.inpoint24.out

12372+1=3

7*3=21

21+3=24

【算法分析】

计算24点主要应用四种运算.开始状态有四个操作数，-个运算符对应两个操作数，所以一开始选

择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整

体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少（只有三层），所以可以用回溯

的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。

1.4冗余依赖

源程序名redund.???(pas,:,cpp)

可执行文件名redund.exe

输入文件名redund.in

输出文件名redund.out

【问题描述】

在设计关系数据库的表格时，术语“函数依赖"（FD）被用来表示不同域之间的关系。函数依赖是描

述一个集合中的域的值与另一个集合中的域的值之间的关系。记号X->Y被用来表示当集合X中的域被赋

值后，集合Y的域就可以确定相应的值。例如，一个数据表格包含“社会治安编号"（S）、姬"（N）、

“地址”（A）、姗”（P）的域，并且每个人都与某个特定的互不相同的S值相对应，根据域S就可以确

定域N、A、P的值。这就记作S->NAP。

写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得

到。例如，如果组里包括依赖A->B、B->C和A->C,那么第三个依赖是冗余的，因为域C可以用前两个

依赖得到（域A确定了域B的值，同样域B确定了域C的值）。在A->B、B->C、C-〉A、A->C、C->B

和B-〉A中，所有的依赖都是冗余的。

现在要求你编写一个程序，从给定的依赖关系中找出冗余的。

【输入】

输A的文件第一行是一个不超过100的整数n,它表示文件中函数依赖的个数。从第二行起每一行是

一个函数依赖且互不重复，每行包含用字符“-”和隔开的非空域列表。列表月包含大写的字母，函

数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如A->A）„虽然文件中没有对函数

依赖编号，但其顺序就是编号1到n。

【输出】

每一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的，先是一个FD,然后是依赖函数

号，接着是"isredundantusingFDs：”最后是说明的序列号。

如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。如果这些

函数依赖中不包含冗余依赖，则输出“NoredundantFDs”信息。

【样例1】【样例2】

redund.inredund.outredund.inredund.out

3FD3isredundantusingFDs:126FD3isredundantusingFDs:1

A->BD｛即C可以通过1、2得到｝P->RSTFD5isredundantusingFDs:462

BD->CVRT->SQP

A->CPS->T

Q->TR

QS->P

SR->V

【算法分析】

一个依赖冗余，就是说它可以由其他依赖推导出来。如何判断一个依赖能否被其他依赖推导出来呢？

假设判断的依赖为“a->b”，先找出所有形式为的依赖，再由*开始找相关依赖，直到出现“#-〉b”

为止（这里a、b、*、#都表示任意一个域名）。

如何实现这种查找呢？可以通过筒单的回溯来完成。只是找出冗余（如果有的话）还不说明工作就已结

束，要到找出所有的能够推导出b的依赖序列，选出其中长度最短的（最短的也可能并不惟一，因此本题

答案有可能并不惟一），最短的证明序列中一定不存在多余的依赖，如果不是最短的证明序列，那么该证

明序列中就有可能还有冗余依赖。

1.5走迷宫

源程序名maze.???(pas,cpp)

可执行文件名maze.exe

输入文件名maze.in

输出文件名maze.out

【问题描述】

有一个m*n格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表

示不可以走，文件读入这m*n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别

表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只

能是上下左右四个方向。如果•条路都不可行，则输出相应信息（用T表示无路）。

【输入】

第一行是两个数m,n（Km,n<15）,接下来是m行n列由1和0组成的数据，最后两行是起始点和

结束点。

【输出】

所有可行的路径，描述一个点时用（x,y）的形式，除开始点外，其他的都要用“表示方向。

如果没有一条可行的路则输出T。

【样例】

maze.in

56

100101

111111

001110

111110

111011

11

56

maze.out

(1,2)->(2,1)->(2,2)-〉(2,3)->(2⑷->(2,5)->(3,5)->(3⑷->(3,3)->(4,3)->(4⑷->(4,5)->(5,5)->(5,6)

(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(2,1)->(2,2)->(2,3)->(2,4)->(2,5)=〉(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3⑷->(3,3)->(4,3)->(4,4)-〉(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3⑷-〉(4,4)-〉(4,5)->(5,5)->(5,6)

(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)-〉(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)-〉(2,1)->(2⑵->(2,3)->(3,3)->(4,3)->(4⑷->(3⑷->(2/1)->(2,5)->(3,5)-〉(4,5)->(5,5)-〉(5,6)

(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4⑷->(4,5)->(5,5)->(5,6)

【算法分析】

用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来

描述，一个表示行号，另一个表示列号。对于某一个点（x,y）,四个可能走的方向的点描述如下表：

1

4x,y2

3

对应的位置为:(x-l,y),(x,y+l),(x+l,y),(x,y-1)。所以每个点都要试探四个方向，如果没有走过(数

组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，

到了终点则输出所走的路，否则继续走下去。

这个查找过程用search来描述如下：

proceduresearch(x,y,b,p)；｛x,y表示某一个点，b是已经过的点的情况，p是已走过的路｝

begin

fori:=1to4do｛分别对4个点进行试探｝

begin

先记住当前点的位置，已走过的情况和走过的路；

如果第i个点(xl,yl)uj以走，则走过去；

如果已达终点，则输出所走的路径并置有路可走的信息，

否则继续从新的点往下查找search(xl,yl,bl,pl)；

end；

end；

【思考与提高】

该程序通过引进新的变量和数组来继续新的查找，如果不引进新的变量和数组，那么每一次返回时要

将原来的值还原才行，如果那样，程序应如何修改?其实那样更加符合回溯的思想——换条路再试。这类

问题也可以归为搜索的问题，如果m和n的值相对比较大，则解可能很多，若题目只要找到一条路就结束

程序时，在程序的输出部分后面加上一个halt就行了。

有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于

这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层

的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜

索速度。

1.6单向双轨道

源程序名track.???(pas,cpp)

可执行文件名track.exe

输入文件名track.in

输出文件名track.out

【问题描述】

如图所示1,某火车站有B,C两个调度站，左边入口A处有n辆火车等待进站（从左到右以a、b、c、

d编号），右边是出口D,规定在这段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度

站不限定所能停放的车辆数。____________一

入□dl口

ABCD

从文件输入n及n个小写字母的一个排列，该排列表示火车在出口D处形成的从左到右的火车编号序

列。输出为一系列操作过程，每一行形如“hLR”的字母序列，其中h为火车编号，L为h车原先所在位

置（位置都以A、B、C、D表示），R为新位置。或者输出‘NO'表示不能完成这样的调度。

【输入】

一个数n（Kn<27）及由n个小写字母组成的字符串。

【输出】

可以调度则输出最短的调度序列，不可以调度时则输出‘NO'。

【样例】

rack.out

3cAB

cbabAC

aAD

bCD

cBD

【算法分析】

这是一道类似于栈的操作题目，只不过是有两个栈B和C可以操作，而对于A序列里的元素，既可

以进入B,也可以进入C,或直接到D。解决问题可以从D序列出发反过来看，当前要到D的字符在哪里，

如果在A,再看它前面有没有字符，如果有，先让它们进栈（B或C）,否则直接到D；如果在B,看是否

是栈顶元素，如果是，直接到D,否则将上面的字符进C；如果在C,看是否是栈顶元素，如果是，直接

到D,否则无法进行操作，因为只能向右不能向左，这时要回溯。如果所有的情况都检测过，某个字符不

能进行到D的操作，则输出无解信息。

由于A里的非直接进入D的字符可以进入B或C,可以跟二进制建立起对应关系，将所有情况列举

一遍，再找出其中步骤最少的输出。

1.7组合的输出

源程序名track.???(pas,cpp)

可执行文件名track.exe

输入文件名track.in

输出文件名track.out

【问题描述】

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且K=n),我们

可以简单地将n个元素理解为自然数1,2,…，n,从中任取r个数。

现要求你不用递归的方法输出所有组合。

例如n=5,r=3,所有组合为：

123124125134135145234235245345

【输入】

一行两个自然数n、r(Kn<21,K=r<=n)o

【输出】

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，

所有的组合也按字典顺序。

【样例】

compages.incompages.out

53123

124

125

134

135

145

234

235

245

345

【算法分析】

如果通过循环加递归来实现回溯比较简单，相应程序为：

constmax=20;

vara:array[0..max]ofinteger;

n,r:1..max;

procedurecompages(k:integer);｛选取第k个元素｝

vari,j:integer;

begin

｛当前所选元素最小为前个元素加1,最大为n-(r-k),因为后面还有(r-k)个元素要选取，至少为每次选取留•个｝

fori:=a[k-l]+lton-(r-k)dobegin

a[k]:=i;｛选取一个元素｝

ifk=rthenbegin

forj:=1tordowrite(a[j]:3);

writein;

end

elsecompages(k+1);

end;

end;

begin{main}

readln(n,r);

compages(1);｛从第一个元素开始选取给合数｝

end.

本题要求不用递归来实现回溯，关键要定好回溯的条件。如果选取第i个元素时选择了a[i],根据输

出条件应有a[i]-i<=n-r,如果不满足这个条件说明当前第i个元素已再无数可取，要进行回溯，将其值减

1,退到上一步将上一步原来的值再增加1,重复上述过程。当全部选取完时，i回到了0,a[0]的值增加1

后变为1,这是整个选取过程结束的条件。

L8售货员的难题

源程序名salesman.???(pas,c,cpp)

可执行文件名salesman.exe

输入文件名salesman.in

输出文件名salesman.out

【问题描述】

某乡有n个村庄（l<n<40）,有一个售货员，他要到各个村庄去售货，各村庄之间的路程s（0<s<1000）

是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，

然后返回商店所在的村，假设商店所在的村庄为1,他不知道选择什么样的路线才能使所走的路程最短。

请你帮他选择一条最短的路。

【输入】

村庄数n和各村之间的路程（均是整数）。

【输出】

最短的路程。

【样例】

salesman.insalesman,out

3｛村庄数｝3

021｛村庄1到各村的路程｝

102｛村庄2到各村的路程｝

210｛村庄3至恪村的路程｝

【算法分析】

题目给定的村庄数不多（W40）,所以可以用回溯的方法，从起点（第•个村庄）出发找出所有经过其他

所有村庄的回路，计算其中的最短路程。当村庄数n比较大时这种方法就不太适用了。

用一个过程road（step,line：byte）来描述走的状况，其中step是当前已到村庄数、line是当前所

在的村庄。如果step=n,下面只能回起点了，直接看第line个村庄到第一个村庄的路程加上已走的总路

程，如果比最小值还小则替换最小值（要保存路径的话也可保存，这是回溯算法的优点，考虑到达最小值

的路径可能不止一条，不便于测试，题目没要求输出路径）。如果step还小于n,那么将还没有到过的村

庄一个一个地试过去，再调用下一步road（step+1,新到的村庄号）。

1.9驾车旅游

源程序名tour.???(pas,c,cpp)

可执行文件名tour.exe

输入文件名tour.in

输出文件名tour.out

【问题描述】

如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游

时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的

加油站的列表，列表中包括了所有加油站的位置及其每升的油价（如3.25元/L）。驾车者一般都有以下的习

惯：

（1）除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半

的汽油时，驾驶员从不在加油站停下来；

（2）在第一个停下的加油站总是将油箱加满；

（3）在加油站加油的同时，买快餐等吃的东西花去20元。

（4）从起始城市出发时油箱总是满的。

（5）加油站付钱总是精确到0.1元（四舍五入）。

（6）驾车者都知道自己的汽车每升汽油能够行驶的里程数。

现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面

最少的费用。

【输入】

第一行是一个实数，是从出发地到目的地的距离（单位：km）。

第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量（单位：I。）；第二个实数是汽

车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用（单位元）；一个整数是1到50

间的数，表示从出发地到目的地线路上加油站的数目。

接下来n行都是两个实数，第一个数表示从出发地到某一个加油站的距离（单位：km）；第二个实数表

示该加油站汽油的价格（单位：元）。

数据项中的每个数据都是正确的，不需判错。一条线路上的加油站根据其到出发地的距离递增排列并

且都不会大于从出发地到目的地的距离。

【输出】

就一个数据，是精确到0.1元的最小的加油和吃饭费用

【样例】

tour,intour.out

600379.6

408.51283

2003.52

3503.45

500365

【算法分析】

驾车者从出发地出发后对于每个加油站都可能有两种操作，一是进去加油买食品，二是不进去继续前

行（如果当前汽车的余油可以的话），这样有n个加油站最多可能有2n种选择。由于加油站数目不太多，

可以采用回溯的算法来解决问题。从第一个加油站开始，依次选择所要停下的下一个加油站，从而找出总

费用最少的方案，加油站数目最多为50,这样回溯不会进行得很深。在选择下一个要停下的加油站时比较

麻烦，不能完全一个一个地试过去，这样时间太长。可以用这样的方法：先找出第一个要停下的加油站，

判断其后面的加油站是否可以到达，如果不可到达就必须在这里停下来加油；否则就找出可以到达但如果

只用一半汽油则无法到达的所有加油站，依次进行停靠。

1.10关路灯

源程序名powei*.???(pas,c,cpp)

可执行文件名powe匚exe

输入文件名power.in

输出文件名power.out

【问题描述】

某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有

少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。

为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是

老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向

左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关

掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能

会更省一些。

现在已知老张走的速度为lm/s,每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、

功率（W）,老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便

不再消耗电了）。

【输入】

文件第一行是两个数字n（0<n<50,表示路灯的总数）和c（l<=c<=n老张所处位置的路灯号）；

接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。

【输出】

一个数据，即最少的功耗（单位：J,U=lW-s）。

【样例】

power.inpower.out

53270｛此时关灯顺序为34215,不必输出这个关灯顺序｝

210

320

520

630

810

【算法分析】

设老张开始所在位置为c,以起始点c为分界点，算出左右两部分总的功率p」eft和p_right,再来分

别看向左与向右的情况。

向左走时，相应地可以减小左边应费的功，而增加右边应费的功，如果到一个点（一•盏路灯处）所要时

间为3减少的功为（p」eft+w[i]）*3增加的功为p_right*2t。

向右走时，相应地可以减小右边应费的功，而增加左边应费的功，如果到一个点（一盏路灯处）所要时

间为3减少的功为（p_righ+w[i]）*t,增加的功为p」eft*2t。

比较向左与向右的情况，找出比较好的一种确定方法。大部分情况能够解出最小值，但不能求出所有

情况下最佳的解。

对于每一个所处位置，都可以选择向左或向右，不管是向左还是向右，相应耗电的变化都跟上面所述

一样。所以可以选择回溯的算法来实现有限的搜索，对每一个点试探向左与向右的情况，在所有可能的情

况中找出最优解。

【思考与提高】

上面的程序运算的范围很有限，当n比较大时就会栈溢出，如n>30时速度就比较慢了。实际情况调

头的次数并不会多的，到底在什么时候掉头根据情况而定。我们可以从最后一步来思考：

最后一次关的可能是第一个灯也可能是最后一个灯，哪种情况所费的功小就选哪种；

最后一次关的是第一个灯的话，说明最后的方向是从最后到最前（右边到左边），最后倒数第二次的方

向为从左到右，起点可能是原始起点（此时是第一趟），也可能是原始起点左边的点（此时至少是第二趟），

一个个地试过去，先设拐一次弯，有可能拐的点都试过去，再试有两次拐弯换方向的情况，当再多的拐弯

超过已有的解时就不要再向下试了。采用这种回溯方法，效率更高。

如果n再大一些，如到300以上，上述方法也有它的局限性，此时最好从动态规划法或贪心法的角度

去思考。

第二章递规与递推

2.1遍历问题

源程序名travel.???(pas,c,Cpp)

可执行文件名travel.exe

输入文件名travel.in

输出文件名travel.out

【问题描述】

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的

前序和中序遍历，求它的后序遍历，相应的，已知•棵二叉树的后序遍历和中序遍历序列你也能求出它的

前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵

二叉树：

aaaa

//\\

bbbb

/\/\

cccc

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

【输入】

输A数据共两行，第一行表示该二叉树的前序遍历结果si,第二行表示该二叉树的后序遍历结果s2。

【输出】

输出可能的中序遍历序列的总数，结果不超过长整型数。

【样例】

rave1.out

abc4

bca

【算法分析】

根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一

个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉

树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结

点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的

中间结点，上面两种情况只是特殊的情况。

设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为

根结点，从第二个结点到最后一个结点分为n种情况：

根结点的左子树结点个数为n-1,右子树结点的个数为0；

根结点的左子树结点个数为n-2,右子树结点的个数为1；

根结点的左子树结点个数为n-i,右子树结点的个数为iT；{0<=i<=n-l);

根结点的左子树结点个数为0,右子树结点的个数为n-K

根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为n-i,右子树结点的

个数为iT((K=i<=nT),先序遍历的结果是从第二个结点(字符)开始取，而后序遍历的结果里是从第1

个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左

子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果

里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程,

不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数

目。

结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数：

Functioncount（先序结果first,后序结果last:string）:longint;

begin

Len:=遍历结果的长度；

如果len为0或1,则返回结果即count:=l

否则begin

t为当前统计后符合条件的数目，初值为0;

分类统计fori:=len-1downto0do

begin

在firet中取出长度为i的左子树结果LF；

在last中取出长度为i的左子树结果LL；

在firet中取出长度为len-1-i的左子树结果RF；

在last中取出长度为len-1-i的右子树结果RL；

如果LF、LL符合基本规则（LF的首字符跟LL的尾字符相同、LF中，所有的

字符在LL中也都有）

并且RF、RL也符合基本规则，那么

t:=t+count（LF,LL）*count（RF,RL）;

｛分步相乘、分步相加｝

｛这里count函数中递归调用了count｝

end;

返回值为t即count:=t;

end;

end;

其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现：

functioncheck（先序字符串F,后序字符串L）：boolean；

begin

Check:=true;

如果F的首字符不等于L的尾字符则check:=false;

从F的第二个字符取到最后一个字符，如果该字符不在L中，则check:=false;

end;

【思考与提高】

上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有可能解的个数，

如果输入的两个字符串没有解，上述算法同样能得到结果。

在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个

结点时.，如先序为ab、后序为ba,此时有可能有如下两种结构：

aa

/\

bb

这两种结构的中序遍历结果分别为：ba、ab,有两种。

根据分步相乘的原理，对比两个字符串，每出现•次如上的情况，可能有的结构数目（结构不同，中

序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目）就乘以2-次，最

终得到总的数目。这也可以理解为一种递推的方法。

从这里可以看到，在肯定有解的情况下，给定先序遍历的结果和后序遍历的结果，可能有2n种可能

的结构，也就是中序遍历可能得到20种不同的结果，其中n>=0。那么这里的n最大可能是多少呢？可以

证明n的最大值为字符串的长度加1整除2o

.推的程序如下：

Programtravel(intput,output);

Var

Total,I,m:longint;

Sl,s2:string;

Begin

Assign(input,,travel.in,);

Assign(output,,travel.out,);

Reset(input);rewrite(output);

Readln(sl);readln(s2);total:=l;

Fori:=ltolength(si)-1do

Begin

M:=pos(sl[i],s2);

Ifm>lthenifs[i+l]=s[m-l]thentotal:=total*2;

End;

Writein(total);close(iinput);close(output);

End.

2.2产生数

源程序名build.???(pas,:,叩p)

可执行文件名build.exe

输入文件名build.in

输出文件名build.out

【问题描述】

给出一个整数n(n<103")和m个变换规则(mW20)。

约定：一个数字可以变换成另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而

这里所说的一个数字就是指一个一位数。

现在给出一个整数n和m个规则，要你求出对n的每一位数字经过任意次的变换(0次或多次)，能产

生出多少个不同的整数。

【输入】

共m+2行，第一行是一个不超过30位的整数n,第2行是一个正整数m,接下来的m行是m个变换

规则，每一规则是两个数字x、y,中间用一个空格间隔，表示x可以变换成y。

【输出】

仅一行，表示可以产生的不同整数的个数。

【样例】

build.inbuild.out

1236

2

12

23

【算法分析】

如果本题用搜索，搜索的范围会很大(因为n可能有30位!)，显然无法在规定的时间内出解。而我们

注意到本题只需计数而不需要求出具体方案，所以我们稍加分析就会发现，可以用乘法原理直接进行计数。

设F[i]表示从数字i出发可以变换成的数字个数(这里的变换可以是直接变换，也可以是间接变换，比

如样例中的1可以变换成2,而2又可以变换成3,所以1也可以变换成3：另外自己本身不变换也是种

情况)。那么对于一个长度为m位的整数a,根据乘法原理，能产生的不同的整数的个数为：

F[a[l]]*F[a[2]]*F[a[3]]*-*F[a[m]]«

下面的问题是如何求F[i]呢？由于这些变换规则都是反映的数字与数字之间的关系，所以定义一个布

尔型的二维数组g[0..9,0..9]来表示每对数字之间是否可以变换，初始时都为False；根据输入的数据，如

果数字i能直接变换成数字j,那么g[i,j]置为True,这是通过一次变换就能得到的；接下来考虑那些间接

变换可得到的数字对，很明显：如果i可以变为k,k又可以变为j,那么i就可以变为j,即：

fork:=0to9do

fori:=0to9do

forj:=0to9do

g[i,j]=g[i-j]or(g[i,k]andg[k,jj)；

最后还要注意，当n很大时，解的个数很大，所以要用高精度运算。

2.3出栈序列统计

源程序名stack.???(pas,:,叩p)

可执行文件名stack.exe

输入文件名stack.in

输出文件名stack.out

【问题描述】

栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知

道栈的操作有两种：push和pop,前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操

作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定