9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

信息学奥赛



全国青少年信息学奥林匹克联赛培训习题与解答 (中学高级本) 目录 习题篇 与 解析篇 第一章 回溯法 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.7 餐巾 3.8 马拉松接力赛 3.9 线性存储问题 3.10 扇区填数 第四章 分治 4.1 取余运算 4.2 地毯填补问题 4.3 平面上的最接近点对 4.4 求方程的根

4.5 小车问题 4.6 黑白棋子的移动 4.7 麦森数(NOIP2003) 4.8 旅行家的预算(NOIP1999) 4.9 飞行计划 第五章 图 5.1 医院设置 5.2 工程规划 5.3 服务器储存信息问题 5.4 间谍网络(AGE) 5.5 宫廷守卫 5.6 K-联赛 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.5 魔板 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.in knight.out 6633 6 【算法分析】 从起点开始往下走(只有两个方向可以走),如果某个方向可以走再继续下一步,直到终

点,此时计数。最后输出所有的路径数。这种方法可以找出所有可能走法,如果要输出这些 走法的话这种方法最合适了,但是本题只要求输出总的路径的条数,当棋盘比较大时,本程 序执行会超时,此时最好能找出相应的递推公式更合适,详见后面的递推章节。

1.2 出栈序列统计 源程序名 stack1.???(pas, c, cpp) 可执行文件名 stack1.exe 输入文件名 stack1.in 输出文件名 stack1.out 【问题描述】 栈是常用的一种数据结构, 有 n 令元素在栈顶端一侧等待进栈, 栈顶端另一侧是出栈序 列。你已经知道栈的操作有两?种:push 和 pop,前者是将一个元素进栈,后者是将栈顶元 素弹出。现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求 出对于给定的 n,计算并输出由操作数序列 1,2,?,n,经过一系列操作可能得到的输出 序列总数。 【输入】 一个整数 n(1<=n<=15) 【输出】 一个整数,即可能输出序列的总数目。 【样例】 stack1.in stack1.out 3 5 【算法分析】 先了解栈的两种基本操作,进栈 push 就是将元素放入栈顶,栈顶指针上移一位,等待 进栈队列也上移一位,出栈 pop 是将栈顶元素弹出,同时栈顶指针下移一位。 用一个过程采模拟进出栈的过程,可以通过循环加递归来实现回溯:重复这样的过程, 如果可以进栈则进一个元素,如果可以出栈则出一个元素。就这样一个一个地试探下去,当 出栈元素个数达到 n 时就计数一次(这也是递归调用结束的条件)。

1.3 算 24 点 源程序名 point24.???(pas, c, cpp) 可执行文件名 point24.exe 输入文件名 point24.in 输出文件名 point24.out 【问题描述】 几十年前全世界就流行一种数字游戏, 至今仍有人乐此不疲. 在中国我们把这种游戏称 为“算 24 点” 。您作为游戏者将得到 4 个 1~9 之间的自然数作为操作数,而您的任务是对这 4 个操作数进行适当的算术运算,要求运算结果等于 24。 您可以使用的运算只有:+,-,*,/,您还可以使用()来改变运算顺序。注意:所有 的中间结果须是整数,所以一些除法运算是不允许的(例如,(2*2)/4 是合法的,2*(2/4)是 不合法的) 。下面我们给出一个游戏的具体例子: 若给出的 4 个操作数是:1、2、3、7,则一种可能的解答是 1+2+3*7=24。

【输入】 只有一行,四个 1 到 9 之间的自然数。 【输出】 如果有解的话,只要输出一个解,输出的是三行数据,分别表示运算的步骤。其中第一 行是输入的两个数和一个运算符和运算后的结果,第二行是第一行的结果和一个输入的数 据、运算符、运算后的结果;第三行是第二行的结果和输入的一个数、运算符和“ =24” 。 如果两个操作数有大小的话则先输出大的。 如果没有解则输出“No answer!” 【样例】 point24.in point24.out 1237 2+1=3 7*3=21 21+3=24 【算法分析】 计算 24 点主要应用四种运算.开始状态有四个操作数,一个运算符对应两个操作数, 所以一开始选择两个操作数分别对四个操作符进行循环检测,每一次运算后产生了新的数, 两个数运算变成一个数,整体是少了一个操作数,所以四个数最终是三次运算。由于操作的 层数比较少(只有三层),所以可以用回溯的算法来进行检测,当找到一个解时便结束查找。 如果所有的情况都找过后仍然没有,则输出无解的信息。

1.4 冗余依赖 源程序名 redund.???(pas, c, 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,然 后是依赖函数号,接着是"is redundant using FDs: ”最后是说明的序列号。 如果许多函数依赖的序列都能被用来说明一个依赖是冗余的, 则输出其中最短的证明序 列。如果这些函数依赖中不包含冗余依赖,则输出“No redundant FDs”信息。 【样例 1】 【样例 2】 redund.in redund.out redund.in redund.out 3 FD 3 is redundant using FDs: 1 2 6 FD 3 is redundant using FDs: 1 A->BD {即 C 可以通过 1、2 得到} P->RST FD 5 is redundant using FDs: 4 6 2 BD->C VRT->SQP A->C PS->T Q->TR QS->P SR->V 【算法分析】 一个依赖冗余, 就是说它可以由其他依赖推导出来。 如何判断一个依赖能否被其他依赖 推导出来呢?假设判断的依赖为“a->b” ,先找出所有形式为“a->*”的依赖,再由*开始找 相关依赖,直到出现“#->b”为止(这里 a、b、*、#都表示任意一个域名)。 如何实现这种查找呢?可以通过筒单的回溯来完成。只是找出冗余(如果有的话)还不说 明工作就已结束,要到找出所有的能够推导出 b 的依赖序列,选出其中长度最短的(最短的 也可能并不惟一,因此本题答案有可能并不惟一),最短的证明序列中一定不存在多余的依 赖,如果不是最短的证明序列,那么该证明序列中就有可能还有冗余依赖。 1.5 走迷宫 源程序名 maze.???(pas, c, cpp) 可执行文件名 maze.exe 输入文件名 maze.in 输出文件名 maze.out 【问题描述】 有一个 m*n 格的迷宫(表示有 m 行、n 列),其中有可走的也有不可走的,如果用 1 表示 可以走,0 表示不可以走,文件读入这 m*n 个数据和起始点、结束点(起始点和结束点都是 用两个数据来描述的,分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路, 要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输 出相应信息(用-l 表示无路)。 【输入】 第一行是两个数 m,n(1<m,n<15),接下来是 m 行 n 列由 1 和 0 组成的数据,最后两 行是起始点和结束点。 【输出】 所有可行的路径,描述一个点时用(x,y)的形式,除开始点外,其他的都要用“一>” 表示方向。 如果没有一条可行的路则输出-1。

【样例】 maze.in 56 100101 111111 001110 111110 111011 11 56 maze.out (1,2)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6) (1,1)->(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,4)->(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)->(4,5)->(5,5)->(5,6) (1,1)->(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)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(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)->(4,5)->(5,5)->(5,6) 【算法分析】 用一个 a 数组来存放迷宫可走的情况, 另外用一个数组 b 来存放哪些点走过了。 每个点 用两个数字来描述,一个表示行号,另一个表示列号。对于某一个点(x,y),四个可能走的 方向的点描述如下表: 1 4 x,y 2 3 对应的位置为:(x-1, y),(x, y+1),(x+1, y),(x, y-1)。所以每个点都要试探四个方向,如果 没有走过(数组 b 相应的点的值为 0)且可以走(数组 a 相应点的值为 1)同时不越界, 就走过去, 再看有没有到达终点,到了终点则输出所走的路,否则继续走下去。 这个查找过程用 search 来描述如下: procedure search(x, y, b, p);{x,y 表示某一个点,b 是已经过的点的情况,p 是已走过的路} begin for i:=1 to 4 do{分别对 4 个点进行试探} begin 先记住当前点的位置,已走过的情况和走过的路; 如果第 i 个点(xl,y1)可以走,则走过去; 如果已达终点,则输出所走的路径并置有路可走的信息, 否则继续从新的点往下查找 search(xl,y1,b1,p1); end; end;

【思考与提高】 该程序通过引进新的变量和数组来继续新的查找, 如果不引进新的变量和数组, 那么每 一次返回时要将原来的值还原才行,如果那样,程序应如何修改?其实那样更加符合回溯的 思想——换条路再试。这类问题也可以归为搜索的问题,如果 m 和 n 的值相对比较大,则 解可能很多,若题目只要找到一条路就结束程序时,在程序的输出部分后面加上一个 halt 就行了。 有些情况很明显是无解的, 如从起点到终点的矩形中有一行或一列都是为 0 的, 明显道 路不通,对于这种情况要很快地“剪掉”多余分枝得出结论,这就是搜索里所说的“剪枝” 。 从起点开始往下的一层层的结点,看起来如同树枝一样,对于其中的“枯枝”——明显无用 的节点可以先行“剪掉” ,从而提高搜索速度。 1.6 单向双轨道 源程序名 track.???(pas, c, cpp) 可执行文件名 track.exe 输入文件名 track.in 输出文件名 track.out 【问题描述】 如图所示 l,某火车站有 B,C 两个调度站,左边入口 A 处有 n 辆火车等待进站(从左到 右以 a、b、c、d 编号),右边是出口 D,规定在这一段,火车从 A 进入经过 B、C 只能从左 向右单向开,并且 B、C 调度站不限定所能停放的车辆数。

从文件输入 n 及 n 个小写字母的一个排列,该排列表示火车在出口 D 处形成的从左到 右的火车编号序列。输出为一系列操作过程,每一行形如“h L R”的字母序列,其中 h 为 火车编号, L 为 h 车原先所在位置(位置都以 A、 B、 C、 D 表示), R 为新位置。 或者输出 ‘NO’ 表示不能完成这样的调度。 【输入】 一个数 n(1<n<27)及由 n 个小写字母组成的字符串。 【输出】 可以调度则输出最短的调度序列,不可以调度时则输出‘NO’ 。 【样例】 track.in track.out 3 cAB cba bAC 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, c, cpp) 可执行文件名 track.exe 输入文件名 track.in 输出文件名 track.out 【问题描述】 排列与组合是常用的数学方法,其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r<=n),我们可以简单地将 n 个元素理解为自然数 1,2,?,n,从中任取 r 个数。 现要求你不用递归的方法输出所有组合。 例如 n=5,r=3,所有组合为: l23 l24 125 l34 l35 145 234 235 245 345 【输入】 一行两个自然数 n、r(1<n<21,1<=r<=n)。 【输出】 所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占三个 字符的位置,所有的组合也按字典顺序。 【样例】 compages.in compages.out 53 123 124 125 134 135 145 234 235 245 345 【算法分析】 如果通过循环加递归来实现回溯比较简单,相应程序为: const max=20; var a:array[0..max]of integer; n,r:1..max; procedure compages(k:integer);{选取第 k 个元素} var i,j:integer; begin {当前所选元素最小为前一个元素加 1,最大为 n-(r-k),因为后面还有(r-k)个元素要选取,至

少为每次选取留一个} for i:=a[k-1]+1 to n-(r-k) do begin a[k]:=i; {选取一个元素} if k=r then begin for j:=1 to r do write(a[j]:3); writeln; end else compages(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,这是整个选取过程结束的条件。

1.8 售货员的难题 源程序名 salesman.???(pas, c, cpp) 可执行文件名 salesman.exe 输入文件名 salesman.in 输出文件名 salesman.out 【问题描述】 某乡有 n 个村庄(1<n<40),有一个售货员,他要到各个村庄去售货,各村庄之间的路程 s(0<s<1000)是已知的,且 A 村到 B 村与 B 村到 A 村的路大多不同。为了提高效率,他从商 店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为 1,他不知道选择 什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。 【输入】 村庄数 n 和各村之间的路程(均是整数)。 【输出】 最短的路程。 【样例】 salesman.in salesman.out 3 {村庄数} 3 02l {村庄 1 到各村的路程} 102 {村庄 2 到各村的路程} 210 {村庄 3 到各村的路程} 【算法分析】 题目给定的村庄数不多(?40),所以可以用回溯的方法,从起点(第一个村庄)出发找出 所有经过其他所有村庄的回路, 计算其中的最短路程。 当村庄数 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.in tour.out 600 379.6 40 8.5 128 3 200 3.52 350 3.45

500 365 【算法分析】 驾车者从出发地出发后对于每个加油站都可能有两种操作, 一是进去加油买食品, 二是 不进去继续前行(如果当前汽车的余油可以的话),这样有 n 个加油站最多可能有 2n 种选择。 由于加油站数目不太多,可以采用回溯的算法来解决问题。从第一个加油站开始,依次选择 所要停下的下一个加油站,从而找出总费用最少的方案,加油站数目最多为 50,这样回溯 不会进行得很深。在选择下一个要停下的加油站时比较麻烦,不能完全一个一个地试过去, 这样时间太长。可以用这样的方法:先找出第一个要停下的加油站,判断其后面的加油站是 否可以到达, 如果不可到达就必须在这里停下来加油; 否则就找出可以到达但如果只用一半 汽油则无法到达的所有加油站,依次进行停靠。 1.10 关路灯 源程序名 power.???(pas, c, cpp) 可执行文件名 power.exe 输入文件名 power.in 输出文件名 power.out 【问题描述】 某一村庄在一条路线上安装了 n 盏路灯, 每盏灯的功率有大有小 (即同一段时间内消耗 的电量有多有少) 。老张就住在这条路中间某一路灯旁,他有一项工作就是每天早上天亮时 一盏一盏地关掉这些路灯。 为了给村里节省电费, 老张记录下了每盏路灯的位置和功率, 他每次关灯时也都是尽快 地去关, 但是老张不知道怎样去关灯才能够最节省电。 他每天都是在天亮时首先关掉自己所 处位置的路灯, 然后可以向左也可以向右去关灯。 开始他以为先算一下左边路灯的总功率再 算一下右边路灯的总功率,然后选择先关掉功率大的一边,再回过头来关掉另一边的路灯, 而事实并非如此,因为在关的过程中适当地调头有可能会更省一些。 现在已知老张走的速度为 1m/s,每个路灯的位置(是一个整数,即距路线起点的距离, 单位:m) 、功率(W) ,老张关灯所用的时间很短而可以忽略不计。 请你为老张编一程序来安排关灯的顺序, 使从老张开始关灯时刻算起所有灯消耗电最少 (灯关掉后便不再消耗电了) 。 【输入】 文件第一行是两个数字 n(0<n<50, 表示路灯的总数)和 c(1<=c<=n 老张所处位置的路灯 号); 接下来 n 行,每行两个数据,表示第 1 盏到第 n 盏路灯的位置和功率。 【输出】 一个数据,即最少的功耗(单位:J,1J=1W?s)。 【样例】 power.in power.out 53 270 {此时关灯顺序为 3 4 2 1 5,不必输出这个关灯顺序} 2 10 3 20 5 20 6 30 8 10 【算法分析】

设老张开始所在位置为 c,以起始点 c 为分界点,算出左右两部分总的功率 p_left 和 p_right,再来分别看向左与向右的情况。 向左走时,相应地可以减小左边应费的功,而增加右边应费的功,如果到一个点(一盏 路灯处)所要时间为 t,减少的功为(p_left+w[i])*t,增加的功为 p_right*2t。 向右走时,相应地可以减小右边应费的功,而增加左边应费的功,如果到一个点(一盏 路灯处)所要时间为 t,减少的功为(p_righ+w[i])*t,增加的功为 p_left*2t。 比较向左与向右的情况,找出比较好的一种确定方法。大部分情况能够解出最小值,但 不能求出所有情况下最佳的解。 对于每一个所处位置,都可以选择向左或向右,不管是向左还是向右,相应耗电的变化 都跟上面所述一样。 所以可以选择回溯的算法来实现有限的搜索, 对每一个点试探向左与向 右的情况,在所有可能的情况中找出最优解。 【思考与提高】 上面的程序运算的范围很有限, 当 n 比较大时就会栈溢出, 如 n>30 时速度就比较慢了。 实际情况调头的次数并不会多的, 到底在什么时候掉头根据情况而定。 我们可以从最后一步 来思考: 最后一次关的可能是第一个灯也可能是最后一个灯,哪种情况所费的功小就选哪种; 最后一次关的是第一个灯的话,说明最后的方向是从最后到最前(右边到左边),最后倒 数第二次的方向为从左到右,起点可能是原始起点(此时是第一趟),也可能是原始起点左边 的点(此时至少是第二趟),一个个地试过去,先设拐一次弯,有可能拐的点都试过去,再试 有两次拐弯换方向的情况, 当再多的拐弯超过已有的解时就不要再向下试了。 采用这种回溯 方法,效率更高。 如果 n 再大一些,如到 300 以上,上述方法也有它的局限性,此时最好从动态规划法或 贪心法的角度去思考。

第二章 递规与递推 2.1 遍历问题 源程序名 travel.???(pas, c, cpp) 可执行文件名 travel.exe 输入文件名 travel.in 输出文件名 travel.out 【问题描述】 我们都很熟悉二叉树的前序、中序、后序遍历,在数据结构中常提出这样的问题:已知 一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序遍历和中 序遍历序列你也能求出它的前序遍历。 然而给定一棵二叉树的前序和后序遍历, 你却不能确 定其中序遍历序列,考虑如下图中的几棵二叉树: a a a a / / \ \ b b b b / \ / \ c c c c 所有这些二叉树都有着相同的前序遍历和后序遍历,但中序遍历却不相同。 【输入】 输 A 数据共两行,第一行表示该二叉树的前序遍历结果 s1,第二行表示该二叉树的后

序遍历结果 s2。 【输出】 输出可能的中序遍历序列的总数,结果不超过长整型数。 【样例】 trave1.in trave1.out abc 4 bca 【算法分析】 根据二叉树先序遍历和后序遍历的特点, 可以知道, 先序遍历的第一个结点是后序 遍历的最后一个结点, 对于中序遍历来说却是中间的一个结点, 这里所说的中间也只是相对 而言的中间。 如果一棵二叉树的根结点没有左子树, 那么先序遍历的第一个结点也是中序遍 历的第一个结点, 如果一棵二叉树的根结点没有右子树, 那么先序遍历的第一个结点是中序 遍历的最后一个结点。 我们这里还认为就是中序遍历的中间结点, 上面两种情况只是特殊的 情况。 设二叉树的结点总数为 n(对于输入的字符串来说是它的长度),对于先序遍历的结果, 第一个结点为根结点,从第二个结点到最后一个结点分为 n 种情况: 根结点的左子树结点个数为 n-1,右子树结点的个数为 0; 根结点的左子树结点个数为 n-2,右子树结点的个数为 1; …… 根结点的左子树结点个数为 n-i,右子树结点的个数为 i-1;{0<=i<=n-1); ?? 根结点的左子树结点个数为 0,右子树结点的个数为 n-1。 根据这 n 种情况,分别将二叉树拆分为左子树和右子树,左子树结点个数为 n-i,右子 树结点的个数为 i-l(0<=i<=n-1),先序遍历的结果是从第二个结点(字符)开始取,而后序遍 历的结果里是从第 1 个结点字符开始取。也就是说对于每一种情况,分两步处理:第一步在 先序遍历和后序遍历的结果里取左子树, 看是否符合规则, 统计这部分可能有的中序遍历的 结果数目;第二步在先序遍历和后序遍历的结果里取右子树,看是否符合规则,统计这部分 可能有的中序遍历的结果数目。 这两步都递归调用了统计过程, 不再递归调用的条件就是当 统计的是空树或只有一个结点的树,这时返回的值是可能有的中序遍历结果数目。 结合“分类相加原理”和“分步相乘原理” ,可以得到下面的递归函数: Function count (先序结果 first,后序结果 last : string) : longint; begin Len:=遍历结果的长度; 如果 len 为 0 或 1,则返回结果即 count:=l 否则 begin t 为当前统计后符合条件的数目,初值为 0; 分类统计 for i:=len-1 downto 0 do begin 在 first 中取出长度为 i 的左子树结果 LF; 在 last 中取出长度为 i 的左子树结果 LL; 在 first 中取出长度为 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; 其中,检查先序结果和后序结果两个字符串是否符合基本规则,可以再通过一个函数来实 现: function check(先序字符串 F,后序字符串 L):boolean; begin Check:=true; 如果 F 的首字符不等于 L 的尾字符则 check:=false; 从 F 的第二个字符取到最后一个字符,如果该字符不在 L 中,则 check:=false; end; 【思考与提高】 上面的算法通过递归,结合统计的基本原理“分步相乘,分类相加” ,从而统计出所有可能 解的个数,如果输入的两个字符串没有解,上述算法同样能得到结果。 在肯定有解的情况下,上述算法最终可以递归调用到 0、1 个结点,如果有多组解,那么调 用到两个结点时,如先序为 ab、后序为 ba,此时有可能有如下两种结构: a a / \ b b 这两种结构的中序遍历结果分别为:ba、ab,有两种。 根据分步相乘的原理, 对比两个字符串, 每出现一次如上的情况, 可能有的结构数目(结 构不同, 中序遍历结果也不同, 因此可能有的二叉树结构的数目就是可能有的中序遍历结果 数目)就乘以 2 一次,最终得到总的数目。这也可以理解为一种递推的方法。 从这里可以看到,在肯定有解的情况下,给定先序遍历的结果和后序遍历的结果,可能 有 2n 种可能的结构,也就是中序遍历可能得到 2n 种不同的结果,其中 n>=0。那么这里的 n 最大可能是多少呢?可以证明 n 的最大值为字符串的长度加 1 整除 2。 递推的程序如下: Program travel(intput,output); Var Total,I,m:longint; S1,s2:string; Begin Assign(input,’travel.in’); Assign(output,’travel.out’); Reset(input); rewrite(output); Readln(s1); readln(s2); total:=1; For i:=1 to length(s1)-1 do Begin

M:=pos(s1[i],s2); If m>1 then if s[i+1]=s[m-1] then total:=total*2; End; Writeln(total); close(iinput); close(output); End.

2.2 产生数 源程序名 build.???(pas, c, cpp) 可执行文件名 build.exe 输入文件名 build.in 输出文件名 build.out 【问题描述】 给出一个整数 n(n<1030)和 m 个变换规则(m?20)。 约定:一个数字可以变换成另一个数字,规则的右部不能为零,即零不能由另一个数字 变换而成。而这里所说的一个数字就是指一个一位数。 现在给出一个整数 n 和 m 个规则,要你求出对 n 的每一位数字经过任意次的变换(0 次 或多次),能产生出多少个不同的整数。 【输入】 共 m+2 行,第一行是一个不超过 30 位的整数 n,第 2 行是一个正整数 m,接下来的 m 行是 m 个变换规则,每一规则是两个数字 x、y,中间用一个空格间隔,表示 x 可以变换成 y。 【输出】 仅一行,表示可以产生的不同整数的个数。 【样例】 build.in build.out 123 6 2 12 23 【算法分析】 如果本题用搜索,搜索的范围会很大(因为 n 可能有 30 位!),显然无法在规定的时间内 出解。而我们注意到本题只需计数而不需要求出具体方案,所以我们稍加分析就会发现,可 以用乘法原理直接进行计数。 设 F[i]表示从数字 i 出发可以变换成的数字个数(这里的变换可以是直接变换, 也可以是 间接变换,比如样例中的 1 可以变换成 2,而 2 又可以变换成 3,所以 1 也可以变换成 3; 另外自己本身不变换也是一种情况)。那么对于一个长度为 m 位的整数 a,根据乘法原理, 能产生的不同的整数的个数为:F[a[1]]*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,即: for k:=0 to 9 do

for i:=0 to 9 do for j:=0 to 9 do g[i,j]=g[i,j]or(g[i,k] and g[k,j]); 最后还要注意,当 n 很大时,解的个数很大,所以要用高精度运算。

2.3 出栈序列统计 源程序名 stack.???(pas, c, cpp) 可执行文件名 stack.exe 输入文件名 stack.in 输出文件名 stack.out 【问题描述】 栈是常用的一种数据结构, 有 n 个元素在栈顶端一侧等待进栈, 栈顶端另一侧是出栈序 列。你已经知道栈的操作有两种:push 和 pop,前者是将一个元素进栈,后者是将栈顶元素 弹出。现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出 对于给定的 n,计算并输出由操作数序列 1,2,?,n,经过一系列操作可能得到的输出序 列总数。 【输入】 【输出】 就一个数 n(1?n?1000)。 一个数, 即可能输出序列的 总数目。 【样例】 stack.in stack.out 3 5 【算法分析】 在第一章练习里, 我们通过回溯的方法计算并输出不同的出栈序列, 这里只要求输出不 同的出栈序列总数目,所以我们希望能找出相应的递推公式进行处理。 从排列组合的数学知识可以对此类问题加以解决。 我们先对 n 个元素在出栈前可能的位置进行分析, 它们有 n 个等待进栈的位置, 全部进 栈后在栈里也占 n 个位置,也就是说 n 个元素在出栈前最多可能分布在 2*n 位置上。 出栈序列其实是从这 2n 个位置上选择 n 个位置进行组合, 根据组合的原理, 从 2n 个位 置选 n 个,有 C(2n,n)个。但是这里不同的是有许多情况是重复的,每次始终有 n 个连续的 空位置,n 个连续的空位置在 2n 个位置里有 n+1 种,所以重复了 n+1 次。所以出栈序列的 种类数目为: C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)?*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*?*(n+2)/n!。 考虑到这个数据可能比较大,所以用高精度运算来计算这个结果。 本题实际是一个经典的 Catalan 数模型。有关 Catalan 数的详细解释请参考《组合数学》 等书。 【思考与提高】 我们知道,在某个状态下,所能做的操作(移动方法)无非有两种: (1)将右方的等待进栈的第一个元素进栈; (2)将栈顶的元素出栈,进入左边的 出栈序列。 设此时右方、栈、左方的元素个数分别为 a,b,c。我们就能用(a,b,c)表示出当前的状 态。显然 n=a+b+c,则 c=n-a-b。即已知 a 和 b,c 就被确定,所以我们可以用(a,b)来作为状 态的表示方法。则起始状态为(n,0),目标状态为(0,0)。

又由上面的两种移动方法,我们可类似的得到两种状态转移方式: 再设 f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态 规划的状态转移方程,我们可写出以下递归式: 边界值:f(0,0)=1。 有了这个递归公式后,再写程序就比较简单了,请读者自己写出递归程序。 2.4 计数器 源程序名 count.???(pas, c, cpp) 可执行文件名 count.exe 输入文件名 count.in 输出文件名 count.out 【问题描述】 一本书的页数为 N, 页码从 1 开始编起, 请你求出全部页码中, 用了多少个 0, 1, 2, ?, 9。其中—个页码不含多余的 0,如 N=1234 时第 5 页不是 0005,只是 5。 【输入】 一个正整数 N(N?109),表示总的页码。 【输出】 共十行:第 k 行为数字 k-1 的个数。 【样例】 count.in count.out 11 1 4 1 1 1 1 1 1 1 1 【算法分析】 本题可以用一个循环从 1 到 n,将其拆为一位一位的数字,并加到相应的变量里,如拆 下来是 1,则 count[1]增加 1。这种方法最简单,但当 n 比较大时,程序运行的时间比较长。 这种方法的基本程序段如下: for i:=1 to n do begin j:=i; while j>0 do begin count[j mod 10]:=count[j mod 10]+1; j:=j div 10; end; end; 当 n 是整型数据时,程序执行的时间不会太长。而 n 是长整型范围,就以 n 是一个 9

位数为例,当 i 执行到 8 位数时,每拆分一次内循环要执行 8 次,执行完 8 位数累计内循环 执行的次数为: 9*1+90*2+900*3+9000*4+90000*5+900000*6+9000000*7+90000000*8 时间上让人不能忍受。 可以从连续数字本身的规律出发来进行统计, 这样速度比较快, 先不考虑多余的 0 的情 况,假设从 0000~9999,这一万个连续的数,0 到 9 用到的次数都是相同的,一万个四位数, 0 到 9 这十个数字共用了 40000 次,每个数字使用了 4000 次。 进一步推广,考虑所有的 n 位数情况,从 n 个 0 到 n 个 9,共 10n 个 n 位数,0 到 9 十 个数字平均使用,每个数字共用了 n*10n-1 次。 有了这样的规律后,可以从高位向低位进行统计,最后再减去多余的 0 的个数。 以 n=3657 为例:(用 count 数组来存放 0 到 9 各个数字的使用次数) 最高位(千位)为 3,从 0 千、1 千到 2 千,000~999 重复了 3 次,每一次从 000 到 999, 每个基本数字都使用了 3*102=300 次,重复 3 次,所以 count[0]~count[9]各增加 3*300; 另外最高位的 0 到 2 作为千位又重复了 1000 次,count[0]~count[2]各增加 1000,3 作 为千位用了 657 次(=n mod 100),因此 count[3]增加 657; 接下来对百位 6 再进行类似的处理,0 到 9 在个位和十位平均重复使用 6*20 次,所以 count[0]~count[9]先各增加 6*20, 0 到 5 作为百位重复使用了 100 次, 所以 count[0]~count[5] 再各增加 100,6 作为百位在这里重复用了 57 次(=n mod 100);因此 count[6]增加 57; 对十位和个位也进行相同的处理,得出 count[0]~count[9]的值; 最后再减去多算的 0 的个数。 那么 0 到底多算了多少次呢? 当没有十位及以更高位时,个位的 0,只多算了 1 次; 当没有百位及以更高位时,十位的 0,多算了 10 次; 当没有千位及以更高位时,百位的 0,多算了 100 次; …… 因此在统计 m 位数时,0 多算了(11??1)这样一个全是 1 的 m 位数。 基本算法描述如下: 输入 n; 计算 n 的位数 Len; 将 n 每一位上的数字存放到数组 c 里; 计算 10 的 0 次方到 len-1 次方并存放到数组 b 里; i 控制位数,for i:=len downto 1 do begin 0 到 9 的使用次数增加平均使用的次数 b[i-1]*(i-1)*c[i]; 0 到 c[i-1]的使用次数增加作为当前位使用的次数 b[i-1]; c[i]的使用次数增加 n mod b[i-1] end 最后减去多计算的 0 的个数; 输出结果。

2.5 诸侯安置 源程序名

empire.???(pas, c, cpp)

可执行文件名 empire.exe 输入文件名 empire.in 输出文件名 empire.out 【问题描述】 很久以前,有一个强大的帝国,它的国土成正方形状,如图 2—2 所示。

这个国家有若干诸侯。 由于这些诸侯都曾立下赫赫战功, 国王准备给他们每人一块 封地(正方形中的一格)。但是,这些诸侯又非常好战,当两个诸侯位于同一行或同一列时, 他们就会开战。如下图 2—3 为 n=3 时的国土,阴影部分表示诸侯所处的位置。前两幅图中 的诸侯可以互相攻击,第三幅则不可以。

国王自然不愿意看到他的诸侯们互相开战,致使国家动荡不安。 因此,他希望通过合 理的安排诸侯所处的位置,使他们两两之间都不能攻击。 现在,给出正方形的边长 n,以及需要封地的诸侯数量 k,要求你求出所有可能的安置 方案数。(n?l00,k?2n2-2n+1) 由于方案数可能很多,你只需要输出方案数除以 504 的余数即可。 【输入】 仅一行,两个整数 n 和 k,中间用一空格隔开。 【输出】 一个整数,表示方案数除以 504 的余数。 【样例】 empire.in empire.out 22 4 【样例说明】 四种安置方案如图 2-4 所示。注意:镜面和旋转的情况属于不同的方案。

【算法分析】 重新描述一下问题,其实就是在一个边长为 2n-1 的正菱形(如上图 2-2 为 n=3 的情形) 上摆放 k 个棋子, 使得任意两个棋子都不在同一行、 同一列。 试问: 这样的摆法共有多少种? 看到这道题目,我们就会立即想起一道经典的老题目:n 皇后问题。这道题目与 n 皇后 问题非常相似。但有两个不同点:一是 n 皇后问题可以斜着攻击对方棋子,而本题不能;二 是 n 皇后问题是在 n, n 的正方形棋盘上面放置 k 个皇后, 而本题却是在一个正菱形上摆放。

我们试着先将 n 皇后变为不可斜攻的,再作思考,如果不能够斜着攻击,n 皇后的公式是: (C(k,n))2*k!。但是本题不是一个正方形,所以这个公式对本题好像没有任何帮助。看来只 能够从另外一个角度思考问题了。

首先想到在 2n-1 列中任意取出 k 列进行具体分析,这样一来问题就转化成:有一个长 为 k 的数列(无重复元素),每一个数在一个不定的区间[a,b]当中,第 i 个数一定在区间[ai,bi] 之间,求这样的数列有多少种?如果就是这个问题,那么比较难解决,但若把这个数列放在 本题中,就比较简单。 因为题目中任意两个区间都是一种包含关系。可以先把区间按照长 度排一下序,就可以看出来,再用乘法原理进行求解即可。但是,n 最多可到 100,k 最多 可到 50,穷举要进行 C(50,100)种方案! 显然无法在规定的时间内出解!那么怎么办呢?再继 续分析一下问题发现,里面有重叠子问题。如果一个列作为最后一列,且这一列以及前面所 有列共放置 p 个诸侯,设有 q 种情况,那么这一列后面的所有列共放置 p+1 个棋子的方案 数都要用到 q,从而引用乘法原理。而且在穷举过程中,这一个工作做了许多遍,所以干脆 用递推。递推前,先把图形转化为类似图 2-5 的形式(即列排序)。 设 f[i,j]表示以第 i 列为最后一列,放置 j 个棋子的总方案数,得出公式: 不过还要注意,当 k?2n-1 时,问题无解。

2.6 括号序列 源程序名 bracket.???(pas, c, cpp) 可执行文件名 bracket.exe 输入文件名 bracket.in 输出文件名 bracket.out 【问题描述】 定义如下规则序列(字符串): 1.空序列是规则序列; 2.如果 S 是规则序列,那么(S)和[S]也是规则序列; 3.如果 A 和 B 都是规则序列,那么 AB 也是规则序列。 例如,下面的字符串都是规则序列: (),[],(()),([]),()[],()[()] 而以下几个则不是: (,[,],)(,()),([() 现在,给你一些由‘(’ , ‘)’ , ‘[’ , ‘]’构成的序列,你要做的,是找出一个最短规则 序列,使得给你的那个序列是你给出的规则序列的子列。(对于序列 a1,a2,?, 和序列 bl,b2,?, ,如果存在一组下标 1?i1<i2<?< ?m,使得 aj= 对一切 1?j?n 成立,那 么 a1,a2?, 就叫做 b1,b2,?, 的子列。 【输入】 输入文件仅一行,全部由‘(’ , ‘)’ , ‘]’ , ‘]’组成,没有其他字符,长度不超过 100。

【输出】 输出文件也仅有一行,全部由‘(’ , ‘)’ , ‘]’ , ‘]’组成,没有其他字符,把你找到的 规则序列输出即可。 因为规则序列可能不止一个, 因此要求输出的规则序列中嵌套的层数尽 可能地少。 【样例】 bracket.in bracket.out ([() ()[]() { 最多的嵌套层数为 1,如层数为 2 时的一种为 ()[()]} 【算法分析】 对于输入的括号序列字符串,从左向右进行查找,用一个数组来记录查找配对的情况, 如果一个括号有相应的括号跟它对应,则将它标记为 0,如果没有相应的括号跟它对应,则 保存原子始代码的编号, “[]”分别为-1 和 1, “()”分别为-2 和 2。 因此对于读入的字符串, 首先将其转换为相应的代码存放到数组里, 为后面查找匹配做 准备。 查找匹配时,可用这样的方法: 如果当前的字符是右括号,则跟前面的一个没有匹配的左括号对照,看是否匹配,如果 匹配,则将两个字符标记为 0,查找并定位到左边的第一个没有匹配的左括号(如果有的话)。 如果当前的字符是左括号, 则记住这个不匹配的左括号的位置, 为后面找到右括号时匹配做 准备。 从第一个字符开始到最后一个字符重复上面的过程,检查处理完毕。 输出时考虑到不增加嵌套的层数,以就近的原则,将出现不匹配的一个括号时,输出两 个匹配的括号。

2.7 新汉诺塔 源程序名 hanoi.???(pas, c, cpp) 可执行文件名 hanoi.exe 输入文件名 hanoi.in 输出文件名 hanoi.out 【问题描述】 设有 n 个大小不等的中空圆盘, 按从小到大的顺序从 1 到 n 编号。 将这 n 个圆盘任意的 迭套在三根立柱上,立柱的编号分别为 A、B、C,这个状态称为初始状态。 现在要求找到一种步数最少的移动方案,使得从初始状态转变为目标状态。 移动时有如下要求: ?一次只能移一个盘; ?不允许把大盘移到小盘上面。 【输入】 文件第一行是状态中圆盘总数; 第二到第四行分别是初始状态中 A、 B、 C 柱上圆盘的个数和从上到下每个圆盘的编号; 第五到第七行分别是目标状态中 A、 B、 C 柱上圆盘的个数和从上到下每个圆盘的编号。 【输出】 每行一步移动方案,格式为:move I from P to Q 最后一行输出最少的步数。 【样例】

Hanoi.in 5 3321 254 0 12 3543 11

Hanoi.out move 1 from A to B move 2 from A to C move 1 from B to C move 3 from A to B move 1 from C to B move 2 from C to A move 1 from B to C 7

【算法分析】 要从初始状态到目标状态.就是要把每个圆盘分别移到自己的目标状态。 怎样才能保证总的移动步数最少呢?关键是首先考虑把编号最大的圆盘移到它的目标状 态, 因为编号最大的圆盘移到目标位置后就不再移动了, 而在编号最大的圆盘没有移到目标 之前,编号小的圆盘可能还要移动,即使它已在目标状态。所以编号最大的圆盘一旦固定, 对以后的移动不会造成影响。 最大的移动好后, 再考虑剩余的没有到达目标状态的最大号圆 盘??直到最小的编号为 1 的圆盘到目标状态为止。 设计一个移动过程:move(k,w),表示把编号 k 的圆盘移到 w 柱。

2.8 排序集合 源程序名 sort.???(pas, c, cpp) 可执行文件名 sort.exe 输入文件名 sort.in 输出文件名 sort.out 【问题描述】 对于集合 N={1,2,?,n}的子集,定义一个称之为“小于”的关系: 设 S1={X1,X2,?,Xi}, (X1<X2<?<Xi) ,S2={Y1, Y2, ?,Yj}, (Y1<Y2<?<Yj) ,如果 存在一个 k, (0?k?min(i,j)) ,使得 X1=Y1,?,Xk=Yk,且 k=i 或 X(k+1)<Y(k+1),则称 S1“小于”S2。 你的任务是,对于任意的 n(n?31)及 k(k<2n),求出第 k 小的子集。 【输入】 输入文件仅一行,包含两个用空格隔开的自然数,n 和 k。 【输出】 输出文件仅一行,使该子集的元素,由小到大排列。空集输出 0。 【样例】 sort.in sort.out 34 123 【算法分析】 我们知道,n 个元素构成的集合有 2n 种情况。本题的意思是:把这些集合按照某种规 则排序,然后输入 k,输出第 k 个集合。所以排序的规则是本题的关键,其实很简单,当 n =3 时,8 个集合排序如下:{}<{1}<{l,2}<{l,2,3}<{1,3}<{2}<{2,3}<{3},你发现规律了吗? 具体算法为:先推出第 k 小的一个子集的第一个数宇是多少,第一个数字确定了之后,再推 出第二个数字, 从第一个数字加 1 一直计算累加集合个数, 直到得到不超过 k 的最大的那个 数字,就是第二位数字,这样一直递推,推到最后一个。要注意:终止条件是有了 n 个数字

或者第 i 个数字为空,这时递推终止,输出最后的结果。

2.9 青蛙过河 源程序名 frog.???(pas, c, cpp) 可执行文件名 frog.exe 输入文件名 frog.in 输出文件名 frog.out 【问题描述】 有一条河,左边一个石墩(A 区)上有编号为 1,2,3,4,?,n 的 n 只青蛙,河中有 k 个荷叶(C 区),还有 h 个石墩(D 区),右边有一个石墩(B 区),如下图 2—5 所示。n 只青蛙 要过河(从左岸石墩 A 到右岸石墩 B),规则为:

(1)石墩上可以承受任意多只青蛙,荷叶只能承受一只青蛙(不论大小); (2)青蛙可以:A→B(表示可以从 A 跳到 B,下同),A→C,A→D,C→B,D→B,D→ C,C→D; (3)当一个石墩上有多只青蛙时,则上面的青蛙只能跳到比它大 1 号的青蛙上面。 你的任务是对于给出的 h,k,计算并输出最多能有多少只青蛙可以根据以上规则顺利 过河? 【样例】 frog.in frog.out 2 3 {河中间有 2 个石礅,3 个荷叶} 16 {最多有 16 只青蛙可以按照规则过 河} 【算法分析】 结论为:f(h,k)=2h(k+1) 从具体到一般,推导过程如下: f(0,0)=1 f(0,k)=k+1; (如 k=3 时,有 4 只青蛙可以过河) f(1,k)=2(k+1); (递推思想) …… 依此类推:f(2,k)=(2*(k+1))*2=22(k+1); ……

2.10 电话号码 源程序名 phone.???(pas, c, cpp) 可执行文件名 phone.exe 输入文件名 phone.in 输出文件名 phone.out 【问题描述】 电话机上每一个数字下面都写了若干个英文字母。分布如下: 1~abc 2~def 3~ghi 4~ikl 5~mn 6~opq 7~rst 8~uvw 9~xyz 现在给定一个单词表和一串数字密码,请你用单词表中的单词翻译这个密码。 【输入】 第一行为一个正整数 N 表示单词表中单词的个数(N?100); 第二行为一个长度不超过 100 的数字串,表示密码; 接下来的 N 行,每行一个长度不超过 20 的单词,表示单词表。 【输出】 仅一行,表示翻译后的原文,如果密码无法翻译,则输出“No Solutions!” ,如果密码 有多种翻译方式,则输出任意一种即可。 【样例】 phone.in phone.out 8 thi shs b boo k 73373711664 thi shs this is b a boo k 【算法分析】 本题可以用递归搜索求解。首先,我们注意到一个数字串对应的单词是不惟一的,而反 之,一个单词所对应的数字串却是惟一的!所以,我们一开始就读入一大串的数字密码和一 些可以出现的单词,我们把每一个单词所表示的密码(是惟一的)存在数组中。然后从密码的 开头开始扫描,得出密码的第一个单词有可能的情况,选择其中一种,得出第一个单词,得 到除第一个单词以外的后面的子密码。然后用递归实现子密码的破译。若子密码无解,就可 以换一种第一个单词的取法,再次试验。如果全是无解,那整个密码也是无解的。另外,首 先要判断整个密码串是否是一个单词,避免无限递归。

2.11 编码 源程序名 encode.???(pas, c, cpp) 可执行文件名 encode.exe 输入文件名 encode.in 输出文件名 encode.out 【问题描述】 编码工作常被运用于密文或压缩传输。 这里我们用一种最简单的编码方式进行编码: 把 一些有规律的单词编成数宇。 字母表中共有 26 个字母{a,b,?,z},这些特殊的单词长度不超过 6 且字母按升序排 列。把所有这样的单词放在一起,按字典顺序排列,一个单词的编码就对应着它在字典中的 位置。 例如: a→1 b→2 z→26 ab→27 ac→28 你的任务就是对于所给的单词,求出它的编码。 【输入】 仅一行,被编码的单词。 【输出】 仅一行,对应的编码。如果单词不在字母表中,输出 0。 【样例】 encode.in encode.out ab 27 【算法分析】 对于输入的字符串, 首先检查是否符合编码的条件: 全是由小写字母组成并且前面的字 母不会比后面的字母大。如果符合条件则进行编码,否则输出 0。 编码时如果不找规律,可以根据顺序,从第一个符合条件的单词 a 开始往后构造,每构 造一个,相应的编码增加 1,直到构造到输入的字符串。 一个单词的后序单词类似于数字的进位,如十进制中 8 后面是 9,9 后面是 10——进位 的情况,再如 99 后面是 100,199 后面是 200。而这里单词的规则是一串中后面的字符不比 前面的大,所以 z 后是 ab,az 后是 bc,??两个字符的单词最大的为 yz,三个字符最小的 为 abc,最大的为 xyz,??六个字符的单词最小的为 abcdef,最大的为 uvwxyz。 根据上面的进位规则进行构造,构造到输入的字符串时则输出相应的序号。 由此可以写出程序。 另外可以从数学上寻找递推的规则: 一个字符的单词有 26 个; 两个字符的单词有:25+24+23+?+1 个; {其中 ab~az 共 25 个,bc~bz 共 24 个,cd~cz 共 23 个?,yz 共 1 个} 三个字符的单词有: (24+23+22+?+1)+(23+22+21+?+1)+?+(2+1)+(1)个 abc~ayz bcd~byz wxy~wyz xyz 四个字符的单词有: ((23+22+21+…+1)+(22+21+20+…+1)+…+(2+1)+(1))+ abcd~axyz ((22+21+20+?+1)+(21+20+?+1)+?+(2+1)+(1))+?+?+((1))个

bcde~bxyz 以此类推,得到相应的数学公式。

wxyz

第三章 贪心法 3.1 排队接水 源程序名 water.???(pas, c, cpp) 可执行文件名 water.exe 输入文件名 water.in 输出文件名 water.out 【问题描述】 有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为 Ti,请编程找出这 n 个 人排队的一种顺序,使得 n 个人的平均等待时间最小。 【输入】 输入文件共两行,第一行为 n;第二行分别表示第 1 个人到第 n 个人每人的接水时间 T1,T2,?,Tn,每个数据之间有 1 个空格。 【输出】 输出文件有两行,第一行为一种排队顺序,即 1 到 n 的一种排列;第二行为这种排列方 案下的平均等待时间(输出结果精确到小数点后两位)。 【样例】 water.in water.out 10 3 2 7 8 1 4 9 6 10 5 56 12 1 99 1000 234 33 55 99 812 291.90 【算法分析】 平均等待时间是每个人的等待时间之和再除以 n,因为 n 是一个常数,所以等待时间之 和最小,也就是平均等待时间最小。假设是按照 1~n 的自然顺序排列的,则这个问题就是求 以下公式的最小值: 如果用穷举的方法求解, 就需要我们产生 n 个人的所有不同排列, 然后计算每种排列所 需要等待的时间之和,再“打擂台”得到最小值,但这种方法需要进行 n!次求和以及判断, 时间复杂度很差! 其实,我们认真研究一下上面的公式,发现可以改写成如下形式: 这个公式何时取最小值呢?对于任意一种排列 k1, k2, k3, ?, kn, 当 ? ? ??? 时, total 取到最小值。如何证明呢?方法如下: 因为 假设 i<j,而 < ,这是的和为 total1,而把 ki 和 kj 互换位置,设新的和为 total2,则: 我们发现上述△total 恒大于 0,所以也说明了任何次序的改变,都会导致等待时间的增 加。从而证明了我们的设想。 既然如此,我们就得到了一种最有贪心策略:把接水时间少的人尽可能排在前面。这样 一样,问题的本质就变成:把 n 个等待时间按非递减顺序排列,输出这种排列,并求出这种 排列下的平均等待时间。

3.2 智力大冲浪 源程序名 riddle.???(pas, c, cpp) 可执行文件名 riddle.exe 输入文件名 riddle.in 输出文件名 riddle.out 【问题描述】 小伟报名参加中央电视台的智力大冲浪节目。 本次挑战赛吸引了众多参赛者, 主持 人为了表彰大家的勇气,先奖励每个参赛者 m 元。先不要太高兴!因为这些钱还不一定都 是你的?!接下来主持人宣布了比赛规则: 首先,比赛时间分为 n 个时段(n?500),它又给出了很多小游戏,每个小游戏都必须在 规定期限 ti 前完成(1?ti?n)。如果一个游戏没能在规定期限前完成,则要从奖励费 m 元中 扣去一部分钱 wi,wi 为自然数,不同的游戏扣去的钱是不一样的。当然,每个游戏本身都 很简单,保证每个参赛者都能在一个时段内完成,而且都必须从整时段开始。主持人只是想 考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者,小伟很想赢得冠军,当然更 想赢取最多的钱!注意:比赛绝对不会让参赛者赔钱! 【输入】 输入文件 riddle.in,共 4 行。 第 1 行为 m,表示一开始奖励给每位参赛者的钱; 第 2 行为 n,表示有 n 个小游戏; 第 3 行有 n 个数,分别表示游戏 1 到 n 的规定完成期限; 第 4 行有 n 个数,分别表示游戏 1 到 n 不能在规定期限前完成的扣款数。 【输出】 输出文件 riddle.out,仅 1 行。表示小伟能赢取最多的钱。 【样例】 riddle.in riddle.out 10000 9950 7 4243146 70 60 50 40 30 20 10 【算法分析】 因为不同的小游戏不能准时完成时具有不同的扣款权数, 而且是最优解问题, 所以本题 很容易就想到了贪心法。 贪心的主要思想是要让扣款数值大的尽量准时完成。 这样我们就先 把这些任务按照扣款的数目进行排序,把大的排在前面,先进行放置。假如罚款最多的一个 任务的完成期限是 k,我们应该把它安排在哪个时段完成呢?应该放在第 k 个时段,因为放 在 1~k 任意一个位置,效果都是一样的。一旦出现一个不可能在规定时限前完成的任务, 则把其扔到最大的一个空时间段,这样必然是最优的,因为不能完成的任务,在任意一个时 间段中罚款数目都是一样的,具体实现请看下面的参考程序 1。 本题也可以有另外一种贪心算法, 即先把所有的数据按照结束时间的先后排序, 然后从 前向后扫描。 当扫描到第 n 个时段,发现里面所分配的任务的结束时间等于 n-1,那么就 说明在前面这些任务中必须舍弃一个,于是再扫描第 1~n 这 n 个时段,挑出一个最小的去 掉并累加扣款值,然后再去调整排列顺序,让后面的元素填补前面的空缺,具体实现请看下 面的参考程序 2。

3.3 取火柴游戏 源程序名 match.???(pas, c, cpp) 可执行文件名 match.exe 输入文件名 match.in 输出文件名 match.out 【问题描述】 输入 k 及 k 个整数 n1,n2,?,nk,表示有 k 堆火柴棒,第 i 堆火柴棒的根数为 ni; 接着便是你和计算机取火柴棒的对弈游戏。 取的规则如下: 每次可以从一堆中取走若干根火 柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取。 谁取走最后一根火柴为胜利者。 例如:k=2,n1=n2=2,A 代表你,P 代表计算机,若决定 A 先取: A:(2,2)→(1,2) {从一堆中取一根} P:(1,2)→(1,1) {从另一堆中取一根} A:(1,1)→(1,0) P:(1,0)→ (0,0) {P 胜利} 如果决定 A 后取: P:(2,2)→(2,0) A:(2,0)→ 0,0) {A 胜利} 又如 k=3,n1=1,n2=2,n3=3,A 决定后取: P:(1,2,3)→(0,2,3) A:(0,2,3)→(0,2,2) A 已将游戏归结为(2,2)的情况,不管 P 如何取 A 都必胜。 编一个程序,在给出初始状态之后,判断是先取必胜还是先取必败,如果是先取必胜, 请输 出第一次该如何取。如果是先取必败,则输出“lose” 。 【样例 1】 match.in match.out 3 43 {表示第一次从第 3 堆取 4 个出来, 必胜} 369 365 {第一次取后的状态} 【样例 2】 match.in match.out 4 lose {先取必败} 15 22 19 10 【算法分析】 从问题的描述分析, 可以将问题中的 k 堆火柴棒抽象为 k 个非负整数, 而每取一次火柴 棒可抽象为使其中的一个自然数变小,当所有的数都变为 0 时,游戏结束,最后—次取火柴 棒的人为胜方。 当 k 较小,且 k 堆火柴棒也都较小时,可使用递推的方法来处理这个问题,具体做法是 从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败,因为某一状态的值可以从 它的所有的取一次后的下一状态得到, 如果某状态的所有的下一状态都为先取必败, 则这一 状态为先取必胜,否则为先取必败。 但当 k 和 ni 都很大时,上述方法很难行得通,为了解决这个问题,首先引进关于 n 个 非负整数的奇偶状态的定义: 如果把 n 个非负整数都化成二进制数, 然后对 n 个二进制数按

位相加(不进行进位), 若每一位相加的结果都为偶数, 则称这 n 个非负整数的状态为偶状态, 否则称之为奇状态。可以证明:任何一个偶状态在某一个数变小后一定成为奇状态,而对任 何一个奇状态,必定可以通过将某一个数的值变小,使得改变后的状态成为偶状态。前一种 情况是显然的, 因为一个数变小以后其对应的二进制数至少有一位发生改变。 这一位的改变 就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明,首先对任何一个奇状态, 从高位向低位寻找到第一位按位加之和为奇数的二进制位, 设这一位为第 k 位, 则 n 个数的 对应的二进制数中至少存在一个数,其第 k 位为 1,将这个二进制数的第 k 位变成 0,则所 有二进制数的第 k 位上的数字之和就变成了偶数。 然后再对这个数的比 k 位低的所有位作如 下调整:如果所有二进制数在该位按位加之和为偶数,则不改变该位的值,否则改变该数在 该位的值,若原来的值为 0,则改为 1,若原来的值为 1,则改为 0,这样就构造出了一个偶 状态,并且被改变的那个数一定变小了,因为这个数被改变的所有二进制位中的最高位从 1 变成了 0。 如 n=3 时, 三堆火柴棒的数量分别为 3, 6, 9, 则 3=(0011)2, 6=(0110)2, 9=(1001)2, 最高位之和为 1,其中 9 对应的二进制数的最高位为 1,将其变为 0,次高位之和也是 1,9 对应的二进制数的次高位为 0,根据证明过程将其变为 1,最后二位数字之和均为偶数,无 需作任何改变, 这样 9=(1001)2 被变成了(0101)2=5, 显然, 3=(0011)2, 6=(0110)2, 5=(0101)2 是一个偶状态。 有了前面的分析,一种贪心算法就出来了。程序中用 n 个包含 16 个元素的数组(线性 表)来存放对每个非负整数对应的二进制数,如 b[i, 0]存放第 i 个数的最低位,n 个数的状 态取决于它们对应的二进制数的各位数字之和的奇偶性,而各位数字之和的奇偶性只需用 0 和 1 来表示,0 表示偶,1 表示奇。最后的状态(全 0)为偶状态,所以开始状态为偶状态时, 先取必败,因为先取后局面变成了奇状态,后取方一定可将字取成偶状态,直至取光为止。 反之则先取必胜。 【后记】 大家都知道国际象棋特级大师卡斯帕罗夫与 IBM 公司研制的“深蓝”超级计算机进行国际 象棋人机大战的事吧! 有了以上算法后, 我们也可以编写出这样一个游戏程序。 让程序代表计算机与人做取火 柴棒游戏,由人或计算机先取,要求你编的程序能够尽可能使计算机获胜。 3.4 加工生产调度 源程序名 prod.???(pas, c, cpp) 可执行文件名 prod.exe 输入文件名 prod.in 输出文件名 prod.out 【问题描述】 某工厂收到了 n 个产品的订单,这 n 个产品分别在 A、B 两个车间加工,并且必须先在 A 车间加工后才可以到 B 车间加工。 某个产品 i 在 A、 B 两车间加工的时间分别为 Ai、 Bi。 怎样安排这 n 个产品的加工顺序, 才能使总的加工时间最短。 这里所说的加工时间是指: 从开始加工第一个产品到最后所有的 产品都已在 A、B 两车间加工完毕的时间。 【输入】 第一行仅—个数据 n(0<n<1000),表示产品的数量。 接下来 n 个数据是表示这 n 个产品在 A 车间加工各自所要的时间(都是整数)。 最后的 n 个数据是表示这 n 个产品在 B 车间加工各自所要的时间(都是整数)。

【输出】 第一行一个数据,表示最少的加工时间; 第二行是一种最小加工时间的加工顺序。 【样例】 prod.in 5 3 5 8 7 10 62149 prod.out 34 15423 【算法分析】 本题是要求一个加工顺序使得总的加工时间最少, 而要使加工时间最少, 就是让各车间 的空闲时间最少。一旦 A 车间开始加工,便会不停地进行加工(我们不要去管车间是否能够 一直生产,因为他们有三班,可以 24 时间不停地运转)。关键是 B 车间在生产的过程中,有 可能要等待 A 车间的初加工产品。很显然所安排的第一个产品在 A 车间加工时,B 车间是 要等待的,最后一个产品在 B 车间加工时,A 车间已经完成了任务。 要使总的空闲时间最少,就要把在 A 车间加工时间最短的部件优先加工,这样使得 B 车间能以最快的速度开始加工;把放在 B 车间加工时间最短的产品放在最后加工,这样使 得最后 A 车间的空闲时间最少。 设计出这样的贪心法: 设 Mi=min{Ai,Bi} 将 M 按照由小到大的顺序排序,然后从第一个开始处理,如果 Mi=Ai,则将它安排在 从头开始的已经安排的生产顺序后面,如果 Mi=Bi,则将它安排在从尾开始的已安排的生 产顺序前面。 这种安排是否是最少的加工时间,还要通过数学证明。证明如下: 设 S=<J1,J2,?,Jn),是等待加工的作业序列,如果 A 车间开始加工 S 中的产品时, B 车间还在加工其他产品, t 时刻后 B 车间就可利用 A 车间加工过的产品。 在这样的条件下, 加工 S 中任务所要的最短时间 T(S, t)=min{Ai+T(s-{Ji},Bi+max{t-Ai, 0})},其中,Ji∈S。 图 3-1 是加工作业 i 时 A 车间等待 B 车间的情况: 图 3-1 A 等 B 的情况 图 3-2 是加工作业 i 时 B 车间等待 A 车间的情形: 图 3-2 B 等 A 的情况 假设最佳的方案中,先加工作业 Ji,然后再加工作业 Jj,则有:

如果 ,则 如果 ,则 如果 ,则 如果将作业 Ji 和作业 Jj 的加工顺序调整,则有: 其中,

按照上面的假设,有 T<=T’ ,所以有: 从而有: 即: 这说是所谓的 Johnson 公式,也就是说在此公式成立的条件下,优先安排任务 Ji 在 Jj 之前 可以得到最优解。也就是在 A 车间加工时间短的安排在前面,在 B 车间加工时间短的任务 安排在后面。 以样例数据为例: (A1, A2, A3, A4, A5)=(3, 5, 8, 7, 10) (B1, B2, B3, B4, B5)=(6, 2, 1, 4, 9) 则(m1, m2, m3, m4, m5)=(3, 2, 1, 4, 9) 排序之后为: (m3, m2, m1, m4, m5) 处理 m3,因为 m3=B3,所以 m3 安排在后面(, , , ,3) ; 处理 m2,因为 m2=B2,所以 m2 安排在后面(, , ,2,3) ; 处理 m1,因为 m1=A1,所以 m1 安排在前面(1, , ,2,3) ; 处理 m4,因为 m4=B4,所以 m4 安排在后面(1, ,4,2,3) ; 处理 m5,因为 m5=B5,所以 m5 安排在后面(1,5,4,2,3) 。 从而得到加工的顺序 1,5,4,2,3。计算出最短的加工时间 34。 【补充说明】 由于本题的原始数据并没有保证数据间没有重复, 所以在数据有重复的情况下生产调度 安排并不是惟一的。但是最少的加工时间是惟一的。

3.5 最大乘积 源程序名 maxmul.???(pas, c, cpp) 可执行文件名 maxmul.exe 输入文件名 maxmul.in 输出文件名 maxmul.out 【问题描述】 一个正整数一般可以分为几个互不相同的自然数的和, 如 3=1+2, 4=1+3, 5=1+4=2+3, 6=1+5=2+4,?。 现在你的任务是将指定的正整数 n 分解成若干个互不相同的自然数的和, 且使这些自然 数的乘积最大。 【输入】 只一个正整数 n,(3?n?10000)。 【输出】 第一行是分解方案,相邻的数之间用一个空格分开,并且按由小到大的顺序。 第二行是最大的乘积。 【样例】 maxmul.in maxmul.out 10 235 30 【算法分析】

初看此题,很容易想到用回溯法进行搜索,但是这里的 n 范围比较大,最多到 10000, 如果盲目搜索,运行时间比较长,效率很低,对于部分数据可能得到结果,对于大部分数据 会超时或栈溢出。 先来看看几个 n 比较小的例子,看能否从中找出规律: n 分解方案 最大的乘积 5 23 6 6 24 8 7 3 4 12 8 3 5 15 9 234 24 10 2 3 5 30 可以发现, 将 n 分解成 a1, a2, a3, a4,?, am 这 m 个自然数, 该序列为从 2 开始的一串由 小到大的自然数,如果 a1 为 1,则对乘积没有影响,而且使 n 减少,没有实际意义,只有 特殊情况如 n 为 3、4 时才可能用上。 设 h>=5, 可以证明当将 h 拆分为两个不相同的部分并且两部分都大于 1 时两部分的乘 积大于 h。证明如下: 将 h 分为两部分:a,h-a 其中 2<=a<h/2,两部分的乘积为 a*(h-a)。 a*(h-a)-h=h*a-a*a-h=h*(a-1)-a*a 因为 h>2*a,所以 a*(h-a)-h>2*a*(a-1)-a*a=a*a-2*a=a*(a-2) 又因为 a>=2,所以 a*(a-2)>=0,所以 a*(h-a)-h>O 即 a*(h-a)>h。 从上面的证明可以看出,对于指定的正整数,如果其大于等于 5,将它拆分为不同的部分后 乘积变大,对于中间结果也是如此。因此可以将指定的 n,依次拆成 a1+a2+a3+a4+?+am, 乘积最大。 现在的问题是如何拆分才能保证 n=a1+a2+a3+a4+?+am 呢? 可以先这样取:当和不足 n 时,a1 取 2,a2 取 3,?,am-1 取 m,即从 2 开始按照自然数 的顺序取数,最后剩余的数给 am,如果 am<=am-1,此时 am 跟前面的数字出现了重复,则 把 am 从后面开始平均分布给前面的 m-1 个数。为什么要从后面开始往前呢?同样是考虑数 据不出现重复的问题,如果是从前面往后面来平均分配,如 2 加上 1 以后变成 3,就跟后面 的已有的 3 出现了重复。这样操作到底是否正确、是否能保证乘积最大呢?还要加以证明。 证明过程如下: 设两个整数 a, b 的和为 2s, 且 a<>b, 设 a=s-1, 则 b=s+1, a*b=(s-1)*(s+1)=s2-1, 如果 a=s-2, 则 b=s+2,a*b=(s-2)*(s+2)=s2-4。 a-b 的绝对值越小,乘积的常数项越大,即乘积越大,上面的序列 a1, a2, a3, a4, ?, am 正好 满足了 a-b 的绝对值最小。但是还要注意两个特例就是 n=3 和 n=4 的情况,它们的分解方案 分别为 1,2 和 1,3,乘积分别为 2 和 3。 以 n=10 为例,先拆分为:10=2+3+4+1,最后一项为 1,比 4 小,将其分配给前面的一项, 得到 10=2+3+5,所以最大的乘积为 2*3*5=30。 以 n=20 为 例 , 拆 分 为 : 20=2+3+4+5+6 , 正 好 是 连 续 自 然 数 的 和 , 所 以 最 大 乘 积 为 2*3*4*5*6=720。 再以 n=26 为例,先拆分为:26=2+3+4+5+6+6,因为最后一项为 6,不比最后第二项大,所 以将其平均分给前面的项,优先考虑后面的项,即前面的 4 项各分到 1,笫 5 项 6 分到 2, 最后是 26=3+4+5+6+8,所以最大的乘积为 3*4*5*6*8=2880。 由于 n 可能大到 10000,分解之后的各项乘积位数比较多,超过普通的数据类型的位数,所 以要用到高精度运算来进行整数的乘法运算,将结果保存在数组里。

本题的贪心策略就是: 要使乘积最大, 尽可能地将指定的 n(n>4)拆分成从 2 开始的连续的自然数的和, 如果最后有 剩余的数,将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。 基本算法描述如下: (1)拆分过程 拆分的数 a 先取 2; 当 n>a 时做 Begin 选择 a 作为一项; a 增加 1; n 减少 a; End; 如果 n>0,那么将 n 从最后一项开始平均分给各项; 如果 n 还大于 0,再从最后一项开始分一次; (2)求乘积 设置一个数组来存放乘积,初始状态位数为 1,结果为 1; 将上面拆分的各项依次跟数组各项相乘并考虑进位;

3.6 种树 源程序名 trees.???(pas, c, cpp) 可执行文件名 trees.exe 输入文件名 trees.in 输出文件名 trees.out 【问题描述】 一条街的一边有几座房子。 因为环保原因居民想要在路边种些树。 路边的地区被分割成 块,并被编号成 1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前 种些树并指定了三个号码 B,E,T。这三个数表示该居民想在 B 和 E 之间最少种 T 棵树。 当然,B?E,居民必须记住在指定区不能种多于区域地块数的树,所以 T?E-B+l。居民们 想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。 写一个程序完成以下工作: * 从 trees.in 读入数据 * 计算最少要种树的数量和位置 * 把结果写到 trees.out 【输入】 第一行包含数据 N,区域的个数(0<N?30000); 第二行包含 H,房子的数目(0<H?5000); 下面的 H 行描述居民们的需要:B E T,0<B?E?30000,T?E-B+1。 【输出】 输出文件第一行写有树的数目, 下面的行包括所有树的位置, 相邻两数之间用一个空格 隔开。 【样例】 trees.in trees.out 9 5

4 14589 142 462 892 352 【算法分析】 不难想到下面的贪心算法:按照每个区间的右端点排序,从左向右扫描,把每个区间内 的树都尽量种在该区间的右端,由于后一个区间的右端不在这个区间的右端的左边(排序), 可以保证这些树尽可能多地被下面的区间利用到。 扫描需要的时间为 O(h),更新需要的时间为 O(n),所以总的时间复杂度为 O(n*h)。

3.7 餐巾 源程序名 napkin.???(pas, c, cpp) 可执行文件名 napkin.exe 输入文件名 napkin.in 输出文件名 napkin.out 【问题描述】 一个餐厅在相继的 N 天里,第 i 天需要 Ri 块餐巾(i=l,2,?,N)。餐厅可以从三种途径 获得餐巾。 (1)购买新的餐巾,每块需 p 分; (2)把用过的餐巾送到快洗部,洗一块需 m 天,费用需 f 分(f<p)。如 m=l 时,第一天送 到快洗部的餐巾第二天就可以使用了,送慢洗的情况也如此。 (3)把餐巾送到慢洗部,洗一块需 n 天(n>m),费用需 s 分(s<f)。 在每天结束时,餐厅必须决定多少块用过的餐巾送到快洗部,多少块送慢洗部。在每天 开始时, 餐厅必须决定是否购买新餐巾及多少, 使洗好的和新购的餐巾之和满足当天的需求 量 Ri,并使 N 天总的费用最小。 【输入】 输入文件共 3 行,第 1 行为总天数;第 2 行为每天所需的餐巾块数;第 3 行为每块餐巾 的新购费用 p,快洗所需天数 m,快洗所需费用 f,慢洗所需天数 n,慢洗所需费用 s。 【输出】 输出文件共 n+1 行。第 1 行为最小的费用。下面的 n 行为从第 1 天开始每天需要的总 餐巾数、需购买的新餐巾数、结束时往快、慢洗部送洗的餐巾数以及用到的来自快洗的餐巾 数和来自慢洗的餐巾数。 【样例】 napkin.in napkin.out 3 64 324 331200 10 1 6 2 3 212010 400022 【算法分析】 在思考这个问题时, 一般容易想到从洗的角度去思考, 这就必然要对每天的餐巾来源进 行分类穷举,当天数较长,每天需求量较大时,穷举的数量级至少为每天的餐巾数之积,程 序很难在规定时间内运行出最优解。 如果从买的角度去思考这个问题, 则该问题就变得十分

简单。在确定要买的餐巾数之后,显然这些餐巾购买得越早,被反复利用的可能就越大。也 就是说,这些餐巾必须在最早的几天中购买,余下的缺口用洗出来的餐巾来填补,对每天用 下来的餐巾,假设全部都送洗,但送洗时不确定其状态,即它们有可能被快洗,有可能被慢 洗,也可能不用洗,其状态在今后被选用时再确定。在确定每天的需求时,除去买的,剩下 的首先要选用慢洗为好。这种餐巾有多少应用多少,不够再选用快洗出来的餐巾。选用快洗 出来的餐巾时, 应选用最近的若干天中才快洗出来的餐巾, 这样可以保证有更多的餐巾被慢 洗出来。这就是我 们的贪心思想。 对所要购买的餐巾数进行穷举, 开始时其值为所需用餐巾数之和, 当购买量太少而周转 不过来时,程序结束。在确定了购买的餐巾总数后,按上述算法构造出最小费用方案,所有 的最小费用方案中的最优解即为问题的解。程序(见本书光盘)中数组 need 存放每天需用的 餐巾数,数组 fromslow 记录每天来自慢洗的餐巾数。数组 fromfast 记录每天来自快洗的餐 巾数,数组 buy 记录每天购买的餐巾数。变量 restslow 存储当天可供选用的已经慢洗好的餐 巾数。这个算法的数量级为 O(n),其中 n 为所有天中需用的餐巾数之总和。 3.8 马拉松接力赛 源程序名 marathon.???(pas, c, cpp) 可执行文件名 marathon.exe 输入文件名 marath.in 输出文件名 marath.out 【问题描述】 某城市冬季举办环城 25km 马拉松接力赛,每个代表队有 5 人参加比赛,比赛要求每个 的每名参赛选手只能跑一次,一次至少跑 1km、最多只能跑 10km,而且每个选手所跑的公 里数必须为整数,即接力的地方在整公里处。 刘老师作为学校代表队的教练,精心选择了 5 名长跑能手,进行了训练和测试,得到 了这 5 名选手尽力连续跑 1km、2km、?、10km 的所用时间。现在他要进行一个合理的安 排,让每个选手跑合适的公里数,使学校代表队跑完 25km 所用的时间最短。根据队员的情 况,这个最短的时间是惟一的,但安排方案可能并不惟一。 根据测试情况及一般运动员的情况得知,连续跑 1km 要比连续跑 2km 速度快,连续跑 2km 又要比连续跑 3km 速度快??也就是说连续跑的路程越长,速度越慢,当然也有特殊 的,就是速度不会变慢,但是绝不可能变快。 【输入】 5 行数据,分别是 1 到 5 号队员的测试数据,每行的 10 个整数,表示某一个运动员尽 力连续跑 1km、2km、?、10km 所用的时间。 【输出】 两行,第一行是最短的时间,第二行是五个数据,分别是 1 到 5 号队员各自连续跑的公 里数。 【样例】 marath.in marath.out 333 700 1200 1710 2240 2613 3245 3956 4778 5899 9748 300 610 960 1370 1800 2712 3834 4834 5998 7682 65545 298 612 990 1560 2109 2896 3790 4747 5996 7654 289 577 890 1381 1976 2734 3876 5678 6890 9876 312 633 995 1467 1845 2634 3636 4812 5999 8123

【算法分析】 初看此题, 好象是一个排列问题, 选取 5 个 10 之间的数, 共有 10*10*10*10*10=100000 种情况,对每一种情况,再看其和是否为 25,在和为 25 的情况下再计算所用的总时间,找 出其中最少的。 这种枚举的方法,肯定能找到最优解,但是这样做的效率不高,执行时间长,这里是 5 个选手还行,如果更多,如 15 个选手,就要对 l015 种可能情况进行判定,再快的计算机也 要较长的时间来执行。 因为运动员连续跑一公里要比连续跑两公里速度快、 连续跑两公里又要比连续跑三公里 速度快??也就是说连续跑的路程越长, 速度越慢, 所以我们可以将每个选手的所跑时间进 行分段处理,计算出各自所跑每一公里所用的时间。又因为要求每个选手至少跑一公里,先 给每一个人分配一公里。剩下的里程由哪个选手来跑呢?这时检查各自所跑第二公里所用的 时间, 哪个用的时间最短就选这个选手继续跑一公里, 因为这样做可以保证当前所用的时间 最少,这个所手所跑的公里数增加 1。下一公里继续用这种方法选,看当前要跑一公里哪个 用的时间最短就选谁,选了谁,谁所跑的公里数增加 l,下面要检查的时间段就是他的下一 段??如此反复直到 25 公里分配完为止。 对于每个运动员跑各公里所用的时间不一定要单独计算出来, 如它跑第 5 公里所用的时 间等于他连续跑完 5 公里所用的时间减去他连续跑 4 公里所用的时间。 本题所用的贪心策略就是: 先分配每个运动员跑一公里;剩下的 20 公里始终选择所有运动员当中下一公里跑的时 间最短的,直到分配完。 这样局部的最优保证整体的最优。 3.9 线性存储问题 源程序名 storage.???(pas, c, cpp) 可执行文件名 storage.exe 输入文件名 storage.in 输出文件名 storage.out 【问题描述】 磁带等存储介质存储信息时基本上都是一种线性存储的方式,线性存储方式虽然简单, 但查询检索时往往要经过一些其它信息, 不象磁盘等存储介质在目录区找到后可直接定位到 某一区城,因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对 较长等优点,现在仍然在使用。 如果有 n 段信息资料要线性存储在某种存储介质上,它们的长度分别是 L1,L2,?, Ln, 存储介质能够保存下所有这些信息, 假设它们的使用(查询检索)的频率分别是 F1, F2, ?, Fn,要如何存储这些信息资料才能使平均检索时间最短。 你的任务就是编程安排一种平均检索时间最短的方案。 【输入】 第一行是一个正整数 n(n<10000), 接下来是 n 行数据, 每行两个整数分别是第 1 段信息 的长度(1 到 10000 之间)和使用的频率(万分比,在 0 到 9000 之间),总的频率之和为 10000。 所输入数据均不要判错。 【输出】 依次存储信息段的编号。每个数据之间用一个空格隔开。 【样例】 storage.in storage.out

5 41352 10 4000 20 1000 30 1000 35 1500 12 2500 【算法分析】 根据统计的基本原理, n 段信息资料的使用 (查询检索) 的频率之和应为 1, 即 F1+F2+? +Fn=1,如果总的检索次数为 m,第 I 段信息资料使用的次数为 m*Fi,设平均检索速度为 v 单位长度/单位时间,而它的长度为 Li,每次所用的时间为 Ti-1+Li/V,其中 Ti-1 为通过安排 在第 I 个信息段前面的所有信息所要的时间,访问信息段 I 所有次数总的时间时: m*Fi*(Ti-1+Li/v)。 因为上表达式中 m、v 可看作是常数,所以单一访问时间 Fi 与 Li 及前面的安排有关, 每段信息均是这样,由此我们可采用如下的贪心方法: 根据(频率*长度)进行由大到小的排序,然后根据这个排序安排某一信息段在相应位置, 从而得到的总的检索时间最短,也就是平均检索时间最短。

3.10 扇区填数 源程序名 fan.???(pas, c, cpp) 可执行文件名 fan.exe 输入文件名 fan.in 输出文件名 fan.out 【问题描述】 有一个圆,当输入一个整数 n(1?n?6)后,它被分成 n 个扇区,请你为每一扇区选择一 个自然数(大于 0 的整数)。 向各个扇区放入数之后, 你可以从单个扇区中选出—个数, 也可以从相邻的两个或多个 扇区中各选一个数, 相加后形成一个新的数, 请使用这些整数形成一个连续的整数序列, : 1, 2,3,?,i,你的任务是使 i 尽可能地大。 【输入】 只一个整数 n(1<=n<=6)。 【输出】 第一行是最大的 i,接下来的几行是所有能达到最大 i 的填法。 由于圆里不分顺序,所以同一种填法可以有多种输出。为了减少这种情况,这里规定从 1,开始输出(因为连续数里要有 1,所以所填的数中肯定有 1)。 【样例】 fan.in fan.out 1 1 1 【算法分析】 假设圆已经被分成了 n 个扇区, 并且已经在这 n 个扇区中填好了数字, 先来看看填好数 字后最多有多少种选择连续的数字并求和的方法,以 N=4 为例: 单独选一个,有 n 种即 1、2、3、4; 选择相邻两个也有 n 种即 12、23、34、41

选择相邻三个也有 n 种即 123、234、341、412; 选择相邻四个只有一种即 1234。 总共有 n*(n-1)+1 种,当 n=4 时有 13 种。 如果每一种选择所求的和都不同,那么能够构成的最多有 n*(n-1)+1 个不同的数。我们 当然希望能够达到的最大的连续数就是从 1 到 n*(n-1)+1 了,如 N=4 时就是 1 到 13。 现在的问题是如何保证这 n*(n-1)+1 个数就是从 1 到 n*(n-1)+1。在填数时首先填 1,接下 来的 n-1 个数都保证不同且最小为 2,再看其他的取相邻的多个数的情况了。在 n<=6 的情 况下都能满足这个要求,对于 n>6 时就不一定了。 从这种最优策略出发,再结合回溯法找出所有可能的情况。 第四章 分治 4.1 取余运算 源程序名 mod.???(pas, c, cpp) 可执行文件名 mod.exe 输入文件名 mod.in 输出文件名 mod.out 【问题描述】 输入 b,p,k 的值,求 b p mod k 的值。其中 b,p,k*k 为长整型数。 【样例】 mod.in mod.out 2 10 9 2^10 mod 9=7 【知识准备】 进制转换的思想、二分法。 【算法分析】 本题主要的难点在于数据规模很大(b, p 都是长整型数),对于 bp 显然不能死算,那样的 话时间复杂度和编程复杂度都很大。 下面先介绍一个原理:a*b mod k=(a mod k)*(b mod k)mod k。显然有了这个原理,就 可以把较大的幂分解成较小的,因而免去高精度计算等复杂过程。那么怎样分解最有效呢? 显然对于任何一个自然数 P, 有 p=2*p div 2+p mod 2, 如 19=2*19 div 2 十 19 mod 2=2*9+1, 利用上述原理就可以把 b 的 19 次方除以 k 的余数转换为求 b 的 9 次方除以 k 的余数,即 b19=b2*9+1=b*b9*b9,再进一步分解下去就不难求得整个问题的解。 这是一个典型的分治问题,具体实现的时候是用递推的方法来处理的,如 p=19,有 19=2*9+1,9=2*4+1,4=2*2+0,2=2*1+0,1=2*0+1,反过来,我们可以从 0 出发,通过 乘以 2 再加上一个 0 或 1 而推出 1,2,4,9,19,这样就逐步得到了原来的指数,进而递 推出以 b 为底,依次以这些数为指数的自然数除以 k 的余数。不难看出这里每一次乘以 2 后要加的数就是 19 对应的二进制数的各位数字,即 1,0,0,1,1,而 19=(10011)2,求 解的过程也就是将二进制数还原为十进制数的过程。 具体实现请看下面的程序, 程序中用数组 binary 存放 p 对应的二进制数, 总位数为 len, binary[1]存放最底位。变量 rest 记录每一步求得的余数。

4.2 地毯填补问题 源程序名

blank.???(pas, c, cpp)

可执行文件名 blank.exe 输入文件名 blank.in 输出文件名 blank.out 【问题描述】 相传在一个古老的阿拉伯国家里,有一座宫殿。宫殿里有个四四方方的格子迷宫,国王 选择驸马的方法非常特殊,也非常简单:公主就站在其中一个方格子上,只要谁能用地毯将 除公主站立的地方外的所有地方盖上, 美丽漂亮聪慧的公主就是他的人了。 公主这一个方格 不能用地毯盖住,毯子的形状有所规定,只能有四种选择(如图 4-l):

(1) (2) (3) (4) 并且每一方格只能用一层地毯,迷宫的大小为(2k)2 的方形。当然,也不能让公主无限制的 在那儿等,对吧?由于你使用的是计算机,所以实现时间为 1s。 【输入】 输入文件共 2 行。 第一行:k,即给定被填补迷宫的大小为 2k(0<k?10); 第二行:x y,即给出公主所在方格的坐标(x 为行坐标,y 为列坐标),x 和 y 之间有一 个空格隔开。 【输出】 将迷宫填补完整的方案:每一补(行)为 x y c (x,y 为毯子拐角的行坐标和列坐标,c 为 使用毯子的形状,具体见上面的图 1,毯子形状分别用 1、2、3、4 表示,x、y、c 之间用一 个空格隔开)。 【样例】 blank.in blank.out 3 551 33 224 114 143 412 441 273 154 183 363 481 722 514 632 812 841 771 661 583 852

881 【知识准备】 分治思想和递归程序设计。 【算法分析】 拿到这个问题后,便有一种递归重复的感觉。首先对最简单的情况(即 k=1)进行分析: 公主只会在 4 个方格中的一个: 左上角:则使用 3 号毯子补,毯子拐角坐标位于(2, 2);{下面就简称为毯子坐标} 左下角:则使用 2 号毯子补,毯子拐角坐标位于(1, 2); 右上角:则使用 1 号毯子补,毯子拐角坐标位于(2, 1); 右下角:则使用 4 号毯子补,毯子拐角坐标位于(1, 1); 其实这样不能说明什么问题, 但是继续讨论就会有收获, 即讨论 k=2 的情况(如图 4-1): # # # ● # ○ # # # ○ ○ # # # # # 我们假设公主所在的位置用实心圆表示,即上图中的(1, 4),那么我们就可以把 1 号毯 子放在(2, 3)处,这样就将(1, 3)至(2, 4)的 k=1 见方全部覆盖(#表示地毯)。接下来就是 3 个 k=1 的见方继续填满,这样问题就归结为 k=1 的情况了,但是有一点不同的是:没有“公 主”了,每一个 k=1 的小见方都会留下一个空白(即上图中的空心圆),那么空白就有:1*3 =3 个,组合后便又是一个地毯形状。 好了,现在有感觉了吧,我们用分治法来解决它!对于任意 k>1 的宫殿,均可以将其 化分为 4 个 k/2 大小的宫殿,先看一下公主站的位置是属于哪一块,因为根据公主所在的位 置,我们可以确定中间位置所放的毯子类型,再递归处理公主所站的那一块,直到出现边界 条件 k=1 的情况,然后在公主边上铺上一块合适的地毯,递归结束。 由于要递归到每一格,复杂度就是面积,就是 O(22*k*k)。

4.3 平面上的最接近点对 源程序名 nearest.???(pas, c, cpp) 可执行文件名 nearest.exe 输入文件名 nearest.in 输出文件名 nearest.out 【问题描述】 给定平面上 n 个点,找出其中的一对点的距离,使得在这 n 个点的所有点对中,该距离 为所有点对中最小的。 【输入】 第一行:n;2?n?60000 接下来 n 行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔 开。 【输出】 仅一行,一个实数,表示最短距离,精确到小数点后面 4 位。 【样例】 nearest.in nearest.out 3 1.0000

11 12 22 【参考程序】 中位数、解析几何、时间复杂度、二分法 【算法分析】 如果 n 很小,那么本题很容易。我们只要将每一点对于其它 n-1 个点的距离算出,找出 最小距离即可。时间复杂度 O(n2)。但本题 n 很大,显然会超时。所以我们要寻找更快的解 决问题的方法。 我们首先想到能不能缩小计算的规模, 即把 n 个点的问题分治成一些小规模 的问题呢? 由于二维情况下的问题计算过于复杂,所以先讨论一维的情况,假设点集为 S。 我们用 X 轴上某个点 m 将点集 S 划分为 2 个子集 S1 和 S2,使得 S1={x∈S|x?m}; S2={x∈S|x>m}。这样一来,对于所有 p∈S1 和 q∈S2 有 p<q。 递归地在 S1 和 S2 上找出其最接近的点对{p1, p2}和{q1, q2},并设δ =MIN{|p2-p1|, |q2-q1|},S 中的最接近点对或者是{p1, p2},或者是{q1, q2},或者是某个{p3, q3},其中 p3 ∈S1 且 q3∈S2。如图 4-2 所示: 图 4-2 一维情形的分治法 我们注意到,如果 S 的最接近点对是{p3, q3},即|p3-q3|<δ ,则 p3 和 q3 两者与 m 的 距离不超过δ ,即|p3-m|<δ ,|q3-m|<δ ,也就是说,p3∈(m-δ , m),q3∈(m, m+δ )。由于 每个长度为δ 的半闭区间至多包含 S1 中的一个点,并且 m 是 S1 和 S2 的分割点,因此(mδ , m)中至多包含 S 中的一个点,则此点就是 S1 中的最大点。同理,如果(m-δ , m)中有 S 中的点,则此点就是 S2 中最小点。因此,我们用线性时间就可以将 S1 的解和 S2 的解合并 成为 S 的解。也就是说,按这种分治策略,合并可在 O(n)时间内完成。这样是否就可以得 到一个有效算法了呢?还有一个问题有待解决,即分割点 m 的选择,即 S1 和 S2 的划分。选 取分割点 m 的一个基本要求是由此导出集合 S 的一个线性分割,即 S=S1∪S2,S1≠φ , S2≠φ ,且 S1∈{x|x?m},S2∈{x|x>m}。容易看出,如果选取 m=(MAX(S)+MIN(S))/2, 可以满足线性分割的要求。 选取分割点后, 再用 O(n)时间即可将 S 划分成 S1={x∈S|x?m} 和 S2={x∈S|x>m}。然而,这样选取分割点 m,有可能造成划分出的子集 S1 和 S2 的不平 衡。例如在最坏情况下,S1 只有 1 个,S2 有 n-1 个,由此产生的分治在最坏情况下所需的 时间 T(n)应满足递归方程: T(n)=T(n-1)+O(n) 它的解是 T(n)=O(n2)。这种效率降低的现象可以通过分治中“平衡子问题”的方法加 以解决。也就是说,我们可以通过适当选择分割点 m,使 S1 和 S2 中有大致相等个数的点。 自然地, 我们会想到用 S 的 n 个点的坐标的中位数来作分割点。 这样一来, 我们就能在 O(n) 的时间里确定 m(证明略),从而得到效率相对较高的分割点。 至此,我们可以设计出一个求一维点集 S 中最接近点对的距离的算法: Function npair1(S); Begin If S 中只有 2 个点 Then δ:=|x[2]-x[1]| Else if S 中只有 1 个点 Then δ :=∞ Else begin M:=S 中各点的坐标值的中位数;

构造 S1 和 S2;{S1∈{x|x?m },S2∈{x|x>m }} δ 1:=npair1(S1); δ 2:=npair1(S2); P:=max(S1); Q:=min(S2); δ :=min(δ 1, δ 2, q-p); end; Exit(δ) End; 由以上的分析可知,该算法的分割步骤总共耗时 O(n)。因此,算法耗费的计算时间 T(n)满 足递归方程: T(2)=1 T(n)=2T(n/2)+O(n); 解此递归方程可得 T(n)=O(n*Log2n)。 这个一维问题的算法看上去比用排序加扫描更加复杂,然而它可以推广到二维。 假设 S 为平面上的点集,每个点都有 2 个坐标值 x 和 y。为了将点集 S 线性分割为大小 大致相等的 2 个子集 S1 和 S2,我们选取一垂直线 l:x=m 来作为分割直线。其中 m 为 S 中各点 X 坐标的中位数。由此将 S 分割为 S1={p∈S|x(p)?m}和 S2={p∈S|x(p)>m}。从而 使 S1 和 S2 分别位于直线 l 的左侧和右侧,且 S=S1∪S2。由于 m 是 S 中各点 X 坐标值的 中位数,因此 S1 和 S2 中的点数大致相等。 递归地在 S1 和 S2 上求解最接近点对问题,我们分别得到 S1 和 S2 中的最小距离δ 1 和δ 2。现设δ =min(δ 1, δ 2)。若 S 的最接近点对(p, q)之间的距离 d(p, q)<δ ,则 p 和 q 必 分属于 S1 和 S2。不妨设 p∈S1,q∈S2。那么,p 和 q 距直线 L 的距离均小于δ 。 因此, 我们若用 P1 和 P2 分别表示直线 L 的左边和右边的宽为δ 的 2 个垂直长条,则 p∈P1 且 q ∈P2,如图 4-3 所示:

据直线 L 的距离小于δ 的所有点 在一维的情形下,距分割点距离为δ 的 2 个区间(m-δ , m),(m, m+δ )中最多各有 S 中 一个点,因而这 2 点成为惟一的未检查过的最接近点对候选者。二维的情形则要复杂一些, 此时, P1 中所有点与 P2 中所有点构成的点对均为最接近点对的候选者。 在最坏情况下有 对 这样的候选者。但是 P1 和 P2 中的点具有以下的稀疏性质,它使我们不必检查所有这 对候 选者。 考虑 P1 中任意一点 p, 它若与 P2 中的点 q 构成最接近点对的候选者, 则必有 d(p, q)< δ 。满足这个条件的 P2 中的点有多少个呢?容易看出这样的点一定落在一个δ *2δ 的矩形 R 中(如图 4-4 所示)。 由δ 的意义可知,P2 中任何 2 个 S 中的点的距离都不小于δ 。由此而来可以推出矩形 R 中最多只有 6 个δ /2*2/3*δ 的矩形(如图 4-5 所示)。

图 4-4 包 含 点 q 的 δ *2 δ 矩 形 R

图 4-5

图 4-6 若矩形 R 中有多于 6 个 S 中的点,则由鸽笼原理易知至少有一个δ /2*2/3*δ 的小矩形 中有 2 个以上 S 中的点。设 U,V 是这样 2 个点,它们位于同一小矩形中,则: ? 因此, ? 。这与δ 的意义相矛盾。也就是说矩形 R 中最多只有 6 个 S 中的点。 图 4-6 是矩形 R 中含有 S 中的 6 个点的极端情形。由于这种稀疏性质,对于 P1 中任一 点 p,P2 中最多只有 6 个点与它构成最接近点对的候选者。因此,在分治的合并步骤中, 我们最多需要检查 对候选者,而不是 对候选者。这是否就意味着我们可以在 O(n)时间内 完成分治法的合并步骤呢?现在还不能确定, 因为我们还不知道要检查哪 6 个点。 为了解决 这个问题,我们可以将 p 和 P2 中所有 S2 的点投影到垂线 L 上。由于能与 p 点一起构成最 接近点对候选者的 S2 中点一定在矩形 R 中, 所以它们在直线 L 上的投影距 p 在 L 上投影点 的距离小于δ 。由上面的分析可知,这种投影点最多只有 6 个。因此,若将 P1 和 P2 中所 有 S 的点按其 Y 坐标排好序,则对 P1 中所有点,对排好序的点列作一次扫描,就可以找出 所有最接近点对的候选者,对 P1 中每一点最多只要检查 P2 中排好序的相继 6 个点。 至此,我们得出用分治法求二维最接近点对距离的算法: Function npair(s); Begin If S 中只有 2 个点 Then δ :=S 中这 2 点的距离 Else if S 中只有 1 个点 Then δ :=∞ Else begin (1)m:=S 中各点 X 坐标值的中位数; 构造 S1 和 S2; (2)δ 1:=npair1(S1); δ 2:=npair1(S2); (3)δ m:=min(δ 1, δ 2); (4)设 P1 是 S1 中距垂直分割线 L 的距离在δ m 之间的所有点组 成的集合, P2 是 S2 中距分割线 L 的距离在δ m 之间的所有点组成的集 合。将 P1 和 P2 中的点依其 Y 坐标值从小到大排序,并设 P1*和 P2*

是相应的已 排好序的点列; (5)通过扫描 P1*,对于 P1*中每个点检查 P2*中与其距离在δ m 之内的所 有点(最多 6 个)可以完成合并。当 P1*中的扫描指针可在 宽为 2*δ m 的一个区间内移动。设δ 1 是按这种扫描方式找到的点对间 的最小距 离; (6)δ :=min(δ m, δ t); end; Exit(δ) End; 下面我们来分析上述算法的时间复杂性。设对于 n 个点的平面点集 S,在(1)和(5) 步用了 O(n)时间, (3)和(6)用的是常数时间, (2)则用了 时间,而在(4) ,最坏情况 要 O(nlog2n)时间,仍然无法承受,所以我们在整个程序的开始时,就先将 S 中的点对按 Y 座标值排序,这样一来(4)和(5)两步的时间就只需 O(n)的时间了,所以总的计算时间 同样满足: T(2)=1, 由此,该问题的时间复杂度为 O(nlog2n),在渐进的意义下为最优算法了。空间复杂度 为 O(n)。 4.4 求方程的根 源程序名 equation.???(pas, c, cpp) 可执行文件名 equation.exe 输入文件名 equation.in 输出文件名 equation.out 【问题描述】 输入 m,n,p,a,b,求方程 f(x)=mx+nx-px=0 在[a,b]内的根。m,n,p,a,b 均为 整数,且 a<b;m,n,p 都大于等于 1。如果有根,则输出,精确到 1E-11;如果无方程根, 则输出“NO” 。 【样例】 equation.in equation.out 23412 1.5071265916E+00 2.9103830457E-11 【算法分析】 首先这是一个单调递增函数,对于一个单调递增(或递减)函数,如图 4-7 所示,判断在[a, b] 范围内是否有解,解是多少。方法有多种,常用的一种方法叫“迭代法” ,也就是“二分法” 。 先判断 f(a)?f(b)?0,如果满足则说明在[a, b]范围内有解,否则无解。如果有解再判断 x= (a+b)/2 是不是解,如果是则输出解结束程序,否则我们采用二分法,将范围缩小到[a, x)或 (x, b],究竟在哪一半区间里有解,则要看是 f(a)?f(x)<0 还是 f(x)?f(b)<0。 当然对于 yx,我们需要用换底公式把它换成 exp(xln(y))。

4.5 小车问题 源程序名 car.???(pas, c, cpp) 可执行文件名 car.exe 输入文件名 car.in 输出文件名 car.out 【问题描述】 甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车,可是这辆 小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样,且小于车的速度。问:怎 样利用小车才能使两人尽快同时到达。 【输入】 仅一行,三个数据分别表示 AB 两地的距离 s,人的步行速度 a,车的速度 b。 【输出】 两人同时到达 B 地需要的最短时间。 【样例】 car.in car.out 120 5 25 9.6000000000E+00 【算法分析】 最佳方案为:甲先乘车到达 K 处后下车步行,小车再回头接已走到 C 处的乙,在 D 处 相遇后,乙再乘车赶往 B,最后甲、乙一起到达 B 地。这样问题就转换成了求 K 处的位置, 我们用二分法,不断尝试,直到满足同时到达的时间精度。算法框架如下: (1)输入 s,a,b; (2)c0:=0;c1:=s;c:=(c0+c1)/2; (3)求 t1,t2; (4)如果 t1<t2,那么 c:=(c0+c)/2 否则 c:=(c+c1)/2; 反复执行(3)和(4),直到 abs(t1-t2)满足精度要求(即小于误差标准) 。 4.6 黑白棋子的移动 源程序名 chessman.???(pas, c, cpp) 可执行文件名 chessman.exe 输入文件名 chessman.in 输出文件名 chessman.out 【问题描述】 有 2n 个棋子(n?4)排成一行,开始为位置白子全部在左边,黑子全部在右边,如下 图为 n=5 的情况: ○○○○○●●●●● 移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右 移到空位上去, 但不能调换两个棋子的左右位置。 每次移动必须跳过若干个棋子 (不能平移) , 要求最后能移成黑白相间的一行棋子。如 n=5 时,成为: ○●○●○●○●○● 任务:编程打印出移动过程。 【样例】

chessman.in 7

chessman.out step 0:ooooooo*******-step 1:oooooo--******o* step 2:oooooo--******o* step 3:ooooo--*****o*o* step 4:ooooo*****--o*o* step 5:oooo--****o*o*o* step 6:oooo****--o*o*o* step 7:ooo--***o*o*o*o* step 8:ooo*o**--*o*o*o* step 9:o--*o**oo*o*o*o* step 10:o*o*o*--o*o*o*o* step 11:--o*o*o*o*o*o*o*

【问题分析】 我们先从 n=4 开始试试看,初始时: ○○○○●●●● 第 1 步:○○○——●●●○●(—表示空位) 第 2 步:○○○●○●●——● 第 3 步:○——●○●●○○● 第 4 步:○●○●○●——○● 第 5 步:——○●○●○●○● 如果 n=5 呢?我们继续尝试,希望看出一些规律,初始时: ○○○○○●●●●● 第 1 步:○○○○——●●●●○● 第 2 步:○○○○●●●●——○● 这样,n=5 的问题又分解成了 n=4 的情况,下面只要再做一下 n=4 的 5 个步骤就行了。 同理,n=6 的情况又可以分解成 n=5 的情况,??,所以,对于一个规模为 n 的问题,我们 很容易地就把它分治成了规模为 n-1 的相同类型子问题。 数据结构如下: 数组 c[1..max]用来作为棋子移动的场所, 初始时, c[1]~c[n]存放白子 (用 字符 o 表示) ,c[n+1]~c[2n]存放黑子(用字符*表示) ,c[2n+1],c[2n+2]为空位置(用字符 —表示) 。最后结果在 c[3]~c[2n+2]中。 4.7 麦森数(NOIP2003) 源程序名 mason.???(pas, c, cpp) 可执行文件名 mason.exe 输入文件名 mason.in 输出文件名 mason.out 【问题描述】 形如 2p-1 的素数称为麦森数,这时 P 一定也是个素数。但反过来不一定,即如果 P 是 个素数,2p-1 不一定也是素数。到 1998 年底,人们已找到了 37 个麦森数。最大的一个是 P=3021377,它有 909526 位。麦森数有许多重要应用,它与完全数密切相关。 任务:从文件中输入 P(1000<P<3100000),计算 2p-1 的位数和最后 500 位数字(用十进 制高精度数表示)。 【输入】

文件中只包含一个整数 P(1000<P<3100000)。 【输出】 第一行:十进制高精度数 2p-1 的位数; 第 2~11 行:十进制高精度数 2p-1 的最后 500 位数字(每行输出 50 位,共输出 10 行, 不足 500 位时高位补 0); 不必验证 2p-1 与 P 是否为素数。 【样例】 mason.in 1279 mason.out 386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087 【问题分析】 本题的解题方法很多, 其中分治也是一种巧妙的方法。 首先可以想到: 2n=(2 n div 2)2*2 n mod 2 ,即:如果要计算 2n,就要先算出 2 n div 2,然后用高精度乘法算它的平方,如果 n 是奇数还要再乘以 2,写成递归公式就是:f(n)=(f(n div 2))2*2(n mod 2)。 当然,递归是要有边界值的,这就是当 n=0 时,f(n)=1。还要补充一点,该数的长度是 可以用公式计算的,所以在做高精度乘法时,只要取最后 500 位运算就行了。 4.8 旅行家的预算(NOIP1999) 源程序名 trip.???(pas, c, cpp) 可执行文件名 trip.exe 输入文件名 trip.in 输出文件名 trip.out 【问题描述】 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市 ( 假设出发时油箱是空 的)。给定两个城市之间的距离 D1、汽车油箱的容量 C(以升为单位)、每升汽油能行驶的距 离 D2、出发点每升汽油价格 P 和沿途油站数 N(N 可以为零),油站 i 离出发点的距离 Di、 每升汽油价格 Pi(i=1,2,?,N)。计算结果四舍五入至小数点后两位。如果无法到达目的 地,则输出“No Solution” 。 【样例】 trip.in 275.6 11.9 27.4 2.8 2 (分别表示 D1,C,D2,P,N) 102.0 2.9 (以下共 N 行,分别表示油站 i 离出发点的距离 Di 和每升汽油价格 Pi) 220.0 2.2

trip.out 26.95(该数据表示最小费用) 【问题分析】 看到这道题, 许多人都马上判断出穷举是不可行的, 因为数据都是以实数的形式给出的。 但是,不用穷举,有什么更好的方法呢?比较容易想到的是分治法。 首先找到(从后向前)油价最低的加油站,显然车至该站油箱应为空,这样就可将起点至 该站与该站至终点作为两段独立考虑,分别求其最小费用,二者之和即为总费用,这样一直 分下去, 若某段只有起点与终点两个加油站时无需再分, 如某一段油价最低的加油站即为起 点,则如能一次加油即到达该段终点则最好,若不能,则加满油再考虑油箱有油情况下的二 分法, 考虑起点之外所有的加油站中从后往前油价最低的加油站, 若该加油站位于起点加满 油后不能到达之处,则到达该站时油箱应该为空,以该站为界将全程分为两个独立段考虑, 前半段为有油情况,后半段为无油情况。第二种情况,若该加油站处于起点加满油后能到达 之处,则将该段总路程缩短为该加油站至终点的情况,该加油站在该段路程中最便宜,若从 该站加满油仍不能到达终点,则继续分治即可。 程序被设计成一个递归函数 money,形式参数 start 表示起点站,形式参数 stop 表示终 点站,形式参数 rest 表示到达加油站 start 时汽车油箱余下的油的容量,money 函数最终计 算出从加油站 start 到 stop 区间内的最小费用,细节详见光盘所附程序清单和注释。 4.9 飞行计划 源程序名 trgovac.???(pas, c, cpp) 可执行文件名 trgovac.exe 【问题描述】 16 岁那年,Mirko 从大学毕业当起了推销员。他必须访问 N 个城市一次且仅一次,为 他的产品做广告。像所有的推销员一样,他将乘坐飞机来往于城市之间。 每两个城市之间有且仅有一条航线, 而且总是花费 1 小时的时间。 飞机一刻不停地沿着 航线飞行。飞机的起飞时间总是在整点,例如,飞机中午从城市 A 起飞,飞向城市 B,那 么它将在下午 1 点在城市 B 降落,然后立即返回城市 A,再次到达城市 A 的时间应该是下 午 2 点。 Mirko 想作一个计划,使得他可以在沿途的每个城市(不包括起点和终点)花上一小时做 广告,然后立即前往下一个城市。换句话说,他想把 N 个城市排成一个序列 g1,?,gn,对 于每个 i(1<i<n),Mirko 可以在到达 gi 一小时后从 gi 出发到 gi+1。Mirko 可以在任何时候从 g1 出发(但要是整点)。 可惜的是,Mirko 没有飞机时刻表,所以他不得不打电话询问航空公司。每次打电话, Mirko 将选择两个不同的城市 A 和 B, 电话的那头会告诉他中午起飞的 AB 之间的航班是从 A 到 B 还是从 B 到 A。打电话是要付电话费的,所以如果 Mirko 不想在打电话上花太多的 钞票,就必须足够地聪明了。 另外,接电话的有可能是航空公司的老板。如果是他的话,他就会和 Mirko 开玩笑,使 得 Mirko 尽可能多地打电话。为了开玩笑,他就不见得会按照时刻表上写的回答 Mirko 了。 他会重新安排航班的路线,尽量让 Mirko 花最多的钱打电话。但是,如果接电话的是普通的 职员,他会如实地回答 Mirko。第一个接电话的人,以后也将一直接电话。 请你写一个程序帮助 Mirko 作计划。 【库】 这是一道交互式问题,你的程序必须和库 trg_lib 进行交互。库 trg_lib 中含有三个函数 或过程。

Init——只能在程序开始时调用一次。返回城市的数目 n,城市编号从 1 到 n。 Function init:integer; Int init(void); Pitaj——打电话的过程。对于一对不同的城市 A 和 B,如果中午的航班从 A 到 B 则返 回 A,否则返回 B。如果 pitaj(A,B)=A,则 pitaj(B,A)=A。 Function pitaj(a:integer; b:integer):integer; Int pitaj(int a,int b); Gotovo——调用这个过程输出你的计划。Raspored[i]表示题目中说的 gi。调用完这个过 程之后,你的程序会自动结束。 Procedure gotovo(raspored:array of integer); Void gotovo(int raspored[]); 【对使用 PascaI 的选手】 在程序开头加上 uses trg_lib 【对使用 C 或 C++的选手】 在程序开头加上#include “trg_lib.h” 最多会有 900 座城市,你的程序最多只能打 10000 次电话。 【如何测试自己的程序】 给你的库只包含普通职员的功能。Trgovac.in 里面包含所有问题的答案。第一行包含城 市的数目,第 i+1 行是 pitag(i,j)的答案(j=i+1,i+2,?,n)。相邻的数用空格隔开。 例子: 5 1115 345 35 5 你的程序结束后,库会建立两个新文件:trgovac.log 包含交互的具体情况;trgovac.out 包含打电话的次数, 和你的程序返回的最终计划。 如果你打电话的次数太多, 文件只包含-1; 如果问的问题不合法,文件只包含-2。 【注释】 一半的测试数据是普通职员回答的,另一半是精神错乱的老板回答的。 【问题分析】 本题我们可以采用二分法求解。具体分析如下: 对于已知的一条链和一个点,有以下 3 种情况: 1、*-->[]-->[]-->[] 2、[]-->[]-->[]-->* 3、---------->*--------> | | | | []-->[]-->[]-->[]-->[] 第 1、第 2 种情况很好解决,第 3 种情况采用二分法: ---------->*--------> | | | | | | [Be]——>[]——>[Mid]——>[]——>[En]

可以考虑*和 mid 的关系,if *-->mid then En:=mid else Be:=mid;这样,最后必然会出 现这样的情况: ---->*----> | | | | [Be]-->[En] 直接走上面的路径就可以了。总的提问次数为 n*log2n。 第五章 图 5.1 医院设置 源程序名 hospital.???(pas, c, cpp) 可执行文件名 hospital.exe 输入文件名 hospital.in 输出文件名 hospital.out 【问题描述】 设有一棵二叉树,如图 5-1: ○131 / \ 2○4 ○123 / \ 4○20 ○405 其中,圈中的数字表示结点中居民的人口。圈边上数字表示结点编号,现在要求在某个 结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相邻接点之间的距离 为 l。如上图中,若医院建在: 【输入】 第一行一个整数 n,表示树的结点数。(n?100) 接下来的 n 行每行描述了一个结点的状况,包含三个整数,整数之间用空格(一个或多 个)分隔,其中:第一个数为居民人口数;第二个数为左链接,为 0 表示无链接;第三个数 为右链接。 【输出】 一个整数,表示最小距离和。 【样例】 hospital.in hospital.out 5 81 13 2 3 400 12 4 5 20 0 0 40 0 0 【知识准备】 图的遍历和最短路径。 【算法分析】 本题的求解任务十分明了:求一个最小路径之和。 根据题意,对 n 个结点,共有 n 个路径之和:用记号 Si 表示通向结点 i 的路径之和,

则 ,其中 Wj 为结点 j 的居民数,g(i,j)为结点 j 到结点 i 的最短路径长度。下面表中反映的 是样例的各项数据: j g(i,j) i 1 2 3 4 5 Si 1 0 1 1 2 2 0× 13+1× 4+1× 12+2× 20+2× 40=136 2 1 0 2 3 3 1× 13+0× 4+2× 12+3× 20+3× 40=217 3 1 2 0 1 1 1× 13+2× 4+0× 12+1× 20+1× 40=81 4 2 3 1 0 2 2× 13+3× 4+1× 12+0× 20+2× 40=130 5 2 3 1 2 0 2× 13+3× 4+1× 12+2× 20+0× 40=90 从表中可知 S3=81 最小,医院应建在 3 号居民点,使得所有居民走的路径之和为最小。 由此可知,本题的关键是求 g[i,j],即图中任意两点间的最短路径长度。 求任意两点间的最短路径采用下面的弗洛伊德(Floyd)算法。 (1)数据结构: w:array[1..100]of longing; 描述个居民点人口数 g:array[1..100, 1..100]of longint 初值为图的邻接矩阵,最终为最短路径长度 (2)数据的读入: 本题数据结构的原形为二叉树,数据提供为孩子标识法,分支长度为 1,建立带权图的 邻接矩阵,分下面两步: ①g[i,j]←Max {Max 为一较大数,表示结点 i 与 j 之间无直接相连边} ②读入 n 个结点信息: for i:=1 to n do begin g[i,j]:=0; readln(w[i],l,r); if l>0 then begin g[i,l]:=l; g[l,i]:=l end; if r>0 then begin g[i,r]:=l; g[r,i]:=l end; (3)弗洛伊德算法求任意两点间的最短路径长度 for k:=1 to n do for i:=1 to n do if i<>k then for j:=1 to n do if (i<>j)and(k<>j)and(g[i,k]+g[k,j]<g[i,j]) then g[i,j]:=g[i,k]+g[k,j]; (4)求最小的路程和 min min:=max longint; for i:=1 to n do begin sum:=0; for j:=1 to n do sum:=sum+w[i]*g[i,j]; if sum<min then min:=sum;

end; (5)输出 writeln(min); 5.2 工程规划 源程序名 work.???(pas, c, cpp) 可执行文件名 work.exe 输入文件名 work.in 输出文件名 work.out 【问题描述】 造一幢大楼是一项艰巨的工程,它是由 n 个子任务构成的,给它们分别编号 1,2,?, n(5?n?1000)。 由于对一些任务的起始条件有着严格的限制, 所以每个任务的起始时间 T1, T2,?,Tn 并不是很容易确定的(但这些起始时间都是非负整数,因为它们必须在整个工程 开始后启动)。例如:挖掘完成后,紧接着就要打地基;但是混凝土浇筑完成后,却要等待 一段时间再去掉模板。 这种要求就可以用 M(5?m?5000)个不等式表示,不等式形如 Ti-Tj?b 代表 i 和 j 的起 始时间必须满足的条件。每个不等式的右边都是一个常数 b,这些常数可能不相同,但是它 们都在区间(-100,100)内。 你的任务就是写一个程序,给定像上面那样的不等式,找出一种可能的起始时间序列 T1,T2,?,Tn,或者判断问题无解。对于有解的情况,要使最早进行的那个任务和整个 工程的起始时间相同,也就是说,T1,T2,?,Tn 中至少有一个为 0。 【输入】 第一行是用空格隔开的两个正整数 n 和 m,下面的 m 行每行有三个用空格隔开的整数 i,j,b 对应着不等式 Ti-Tj?b。 【输出】 如果有可行的方案,那么输出 N 行,每行都有一个非负整数且至少有一个为 0,按顺序 表示每个任务的起始时间。如果没有可行的方案,就输出信息“NO SOLUTION” 。 【样例 1】 work.in work.out 58 0 120 2 1 5 –1 5 251 4 315 1 414 4 3 –1 5 3 –1 5 4 –3 【样例 2】 work.in work.out 55 NO SOLUTION 1 2 –3 1 5 –1 2 5 –1

5 1 –5 414 【算法分析】 本题是一类称为约束满足问题的典型问题,问题描述成 n 个子任务的起始时间 Ti 及它 们之间在取值上的约束,求一种满足所有约束的取值方法。 将工程的 n 个子任务 1,2,?,n 作为一有向图 G 的 n 个顶点,顶点 Vi(i=1,?,n) 的关键值为子任务 i 的起始时间 Ti,我们并不需要关心顶点之间的弧及其弧长,而是要确定 顶点的关键值 Ti 的取值,满足所有的约束条件。本题的约束条件由 m 个不等式 Ti-Tj?b 给 出,这样的有向图称为约束图。 为了确定每一个 Ti 的值,先假设某一个子任务的起始时间为零,如设 Tj=0,则其余子 任务的起始时间 Ti 相对于 T1 可设置其起始时间为一区间[-maxt,maxt]。 下面分析不等式 Ti-Tj?b。此不等式可变形为如下两种形式: (1)Ti?Tj+b 意味 Ti 的最大值为 Tj+b; (2)Tj?Ti-b 意味 Tj 的最大值为 Ti-b; 因此,根据题中给出的 m 个不等式,逐步调整各个 Ti 的最小值和最大值。 设 high[i]为 Ti 当前的最大值,low[i]为 Ti 当前的最小值。 high[j]为 Tj 当前的最大值,low[j]为 Tj 当前的最小值。 若 high[i]-high[j]>b,则 high[i]=high[j]+b(根据 Ti?Tj+b), 若 low[i]-low[j]<b,则 low[j]=low[i]-b(根据 Ti?Ti-b)。 以上的调整终止视下列两种情况而定: (1)对所有的不等式 Ti-Tj?b,不再有 high[i]或 low[j]的调整; (2)若存在 high[i]<low[i]或 high[j]<low[j]则表示不存在 T1,T2,?,Tn 能满足所有 m 个不等式 Ti-Tj?b,即问题无解。 根据以上思路,先建立约束图,每个结点代表一个起始时间值,并记录其可能的取值范 围: 数组 high,low:array[1..maxn]of longint;{n 个子任务起始时间的取值范围} high[1]=0; low[1]=0; {设置 n 个起始时间的初值,其中 Ti=0} for i:=2 to n do begin high[i]:=maxt; {Ti 的上界} low[i]:=-maxt; {Tj 的下界} end; 约束条件(m 个不等式)用记录数组表示: type {不等式结构} Tinequ=record i,j,b:longint; end; var arrinequ:array[1..maxm]of Tinequ; {存放 m 个不等式} 利用约束条件,逐一调整每一个起始时间的取值范围,直到无法调整为止。 主要算法如下: flag:=true; {调整状态标记} noans:=false; {解的有无标记} while (flag) do {进行约束传递,根据不等式调整各个起始时间值} begin

flag:=false; for k:=1 to m do with arrinequ[k] do begin if (high[i]-high[j]>b) then begin high[i]:=high[j]+b; flag:=true; end; {调整 Ti 的上 界} if (low[i]-low[j]>b) then begin low[j]:=low[i]-b; 界} if (low[i]>high[i]) or (low[j]>high[j]) then begin {无法满足当前不等式,则调整终止} noans:=true; {问题无解 noans=true} flag:=false; break; end; end; end; 下面以样例说明: 【样例 1】 8 个不等式如下 序号 1 2 3 4 5 6 7 8 i 1 1 2 3 4 4 5 5 j 2 5 5 1 1 3 3 4 b 0 -1 1 5 4 -1 -3 -3 顶点的关键值 Ti 的调整记录: 初值 第 1 轮调整 第 2 轮调整 第 3 轮调整 high[1] 0 0 0 0 low[1] 0 0 0 0 high[2] 100000 100000 2 2 low[2] -10000 2 2 2 high[3] 100000 5 5 5 low[3] -10000 4 5 5 high[4] 100000 4 4 4 low[4] -10000 4 4 4 high[5] 100000 1 1 1 low[5] -10000 1 1 1 调整状态 有变化 有变化 无变化 【样例 2】 5 个不等式如下 编号 1 2 3 4 5 i 1 1 2 5 4 j 2 5 5 1 1 b -3 -1 -1 -5 4 顶点关键值 Ti 的调整记录: 初值 第一轮调整 第二轮调整 flag:=true; end; {调整 Tj 的下

1

high 0 0 low 0 0 2 high 100000 99999 low -10000 3 3 high 100000 10000 low -10000 -10000 4 high 100000 4 low -10000 -10000 5 high 100000 -5 low -10000 1 调整情况 high[5]<low[5]终止 经第一轮调整,调整过程终止,即问题无解。 从样例 2 所给不等式也可看出,因为: T1-T2?-3,→T2>T1 T2-T5?-1,→T5>T2 T5-T1?-5,→T1>T5 这三个不等式不能同时成立,因此问题无解。 5.3 服务器储存信息问题 源程序名 servers.???(pas, c, cpp) 可执行文件名 servers.exe 输入文件名 servers.in 输出文件名 servers.out 【问题描述】 Byteland 王国准备在各服务器间建立大型网络并提供多种服务。 网络由 n 台服务器组成, 用双向的线连接。 两台服务器之间最多只能有一条线直接连接, 同时,每台服务器最多只能和 10 台服务器直接连接,但是任意两台服务器间必然存在一条 路径将它们连接在一起。 每条传输线都有一个固定传输的速度。 δ (V, W)表示服务器 V 和 W 之间的最短路径长度,且对任意的 V 有δ (V, V)=0。 有些服务器比别的服务器提供更多的服务, 它们的重要程度要高一些。 我们用 r(V)表示 服务器 V 的重要程度(rank)。rank 越高的服务器越重要。 每台服务器都会存储它附近的服务器的信息。当然,不是所有服务器的信息都存,只有 感兴趣的服务器信息才会被存储。 服务器 V 对服务器 W 感兴趣是指, 不存在服务器 U 满足, r(U)>r(W)且δ (V, U)<δ (V, W)。 举个例子来说,所有具有最高 rank 的服务器都会被别的服务器感兴趣。如果 V 是一台 具有最高 rank 的服务器,由于δ (V, V)=0,所以 V 只对具有最高 rank 的服务器感兴趣。我 们定义 B(V)为 V 感兴趣的服务器的集合。 我们希望计算所有服务器储存的信息量,即所有服务器的|B(V)|之和。Byteland 王国并 不希望存储大量的数据,所以所有服务器存储的数据量(|B(V)|之和)不会超过 30n。 你的任务是写一个程序,读入 Byteland 王国的网络分布,计算所有服务器存储的数据 量。 【输入】 第一行两个整数 n 和 m,(1?n?30000,1?m?5n)。n 表示服务器的数量,m 表示传 输线的数量。 接下来 n 行, 每行一个整数, 第 i 行的整数为 r(i)(1?r(i)?10), 表示第 i 台服务器的 rank。

接下来 m 行,每行表示各条传输线的信息,包含三个整数 a,b,t(1?t?1000,1?a, b?n,a≠b)。a 和 b 是传榆线所连接的两台服务器的编号,t 是传输线的长度。 【输出】 一个整数,表示所有服务器存储的数据总量,即|B(V)|之和。 【样例】 servers.in servers.out 43 9 2 3 1 1 1 4 30 2 3 20 3 4 20 注:B(1)={1,2},B(2)={2},B(3)={2,3},B(4)={1,2,3,4}。 【知识准备】 Dijkstra 算法,及其 O((n+e)log2n)或 O(nlog2n+e)的实现。 【算法分析】 本题的难点在于问题的规模。 如果问题的规模在 100 左右, 那么这将是一道非常容易的 题目。因为 O(n3)的算法是很容易想到的: (1)求出任意两点间的最短路径,时间复杂度为 O(n3); (2)枚举任意两点,根据定义判断一个节点是否对另一个节点感兴趣,时间复杂度为 O(n3)。 当然,对于 30000 规模的本题来说,O(n3)的算法是绝对不可行的,即便降到 O(n2)也不 行,只有 O(nlog2n)或 O(n)是可以接受的。 既然现在可以得到的算法与要求相去甚远, 要想一鼓作气得到一个可行的算法似乎就不 是那么容易了。我们不妨先来看看我们可以做些什么。 判断一个节点 V 是否对节点 W 感兴趣,就是要判断是否存在一个 rank 大于 r(W)的节 点 U,δ (V, U)<δ (V, W)。所以,节点 V 到某个特定的 rank 的节点(集合)的最短距离是 一个非常重要的值。如果我们可以在 O(nlog2n)时间内求出所有节点到特定 rank 的节点(集 合)的最短距离,我们就成功地完成了算法的一个重要环节。 用 Dijkstva 算法反过来求特定 rank 的节点(集合)到所有点的最短距离——以所有特 定 rank 的节点为起点(rank=1, 2, 3, ?或 10),求这一点集到所有点的最短距离。由于图中 与每个点关联的边最多只有 10 条, 所以图中的边数最多为 5n。 用 Priority Queue (Heap, Winner Tree 或 Fibonacci Heap 等)来实现 Dijkstra 算法,时间复杂度为 O((n+e)log2n)(用 Fibonacci Heap 实现,更确切的时间复杂度是 O(nlog2n+e))。这里,e=5n,因而求一遍最短路径的时 间复杂度为 O(nlog2n)。由于 1?rank?10,每个 rank 都要求一遍最短路径,所以求出每个 节点到所有 rank 的最短路径长度的时间复杂度为 O(10*(5+1)nlog2n),即 O(nlog2n)。 求出所有点到特定 rank 的节点(集合)的最短距离,就完成了判断任意节点 V 对 W 是否 感兴趣的一半工作。另一半是求任意节点 V 到 W 的最短距离。前面求节点到 rank 的最短距 离时,利用的是 rank 范围之小——只有 10 种,以 10 个 rank 集合作起点,用 Dijkstra 算法 求 10 次最短路径。但是,如果是求任意两点的最短路径,就不可能只求很少次数的最短路 径了。一般来说,求任意两点最短路径是Ω (n2)的(这只是一个很松的下界) ,这样的规模 已经远远超出了可承受的范围。但是,要判断 V 对 W 是否感兴趣,δ (V, W)又是必须求的,

所以 n 次 Dijkstra 算法求最短路径肯定是逃不掉的(或者也可以用一次 Floyd 算法代替,但 是时间复杂度一样,可认为等价)。那么,我们又能从哪里来降这个时间复杂度呢? 题目中提到:所有服务器储存的数据量(|B(V)|之和)不会超过 30n。这就是说,最多 只存在 30n 对(V, W)满足 V 对 W 感兴趣。所以,就本题来说,我们需要处理的点对最少可 能只有 30n 个,求最短距离的下界也就变成Ω (30n)=Ω (n)了(当然,这也只是很松的下界) 。 虽说下界是Ω (n),其实我们只需要有 O(nlog2n)的算法就可以满足要求了。 从前面估算下界的过程中我们也看到, 计算在下界中的代价都是感兴趣的点对 (一个节 点对另一个节点感兴趣) ,其余部分为不感兴趣的点对。我们如果想降低时间复杂度,就要 避免不必要的计算,即避免计算不感兴趣的点对的最短路径。 我们来看当 V 对 W 不感兴趣时的情况。根据定义,δ (V, W)>δ (V, r(W)+1)。如果是以 W 为起点,用 Dijkstra 算法求最短路径的话。当扩展到 V 时,发现 V 对 W 不感兴趣,即δ (V, W)>δ (V, r(W)+1)。那么,如果再由 V 扩展求得到 U 的最短路径,则: δ (U, W)=δ (V, W)+δ (U, V), δ (U, r(W)+1)=δ (V, r(W)+1)+δ (U, V), 由于δ (V, W)>δ (V, r(W)+1), 所以δ (V, W)+δ (U, V)>δ (V, r(W)+1)+δ (U, V),即δ (U, W)>δ (U, r(W)+1) 所以,U 对 W 也不感兴趣。因此,如果以 W 为起点,求其他点到 W 的最短路径,以 判断其他点是否对 W 感兴趣,当扩展到对 W 不感兴趣的节点时,就可以不继续扩展下去了 (只扩展对 W 感兴趣的节点) 。 我们知道,所有感兴趣的点对不超过 30n。因此,以所有点作起点,用 Dijkstra 算法求 最短路径的时间复杂度可由平摊分析得为 O(30(n+e)log2n)=O(30(n+5n)log2n)=O(nlog2n)。 由此, 我们看到判断一节点是否对另一节点感兴趣, 两个关键的步骤都可以在 O(nlog2n) 时间内完成。当然算法的系数是很大的,不过由于 n 不大,这个时间复杂度还是完全可以承 受的。下面就总结一下前面得到的算法: (1)分别以 rank=1, 2, ?, 10 的节点(集合)作为起点,求该节点(集合)到所有点 的最短距离(其实也就是所有点到该节点(集合)的最短距离) ; (2)以每个点作为起点,求该点到所有点的最短距离。当求得某节点的最短距离的同 时根据求得的最短距离和该节点到 rank 大于起点的节点(集合)的最短距离,判断该节点 是否对起点感兴趣。如果感兴趣,则找到一对感兴趣的点对,否则,停止扩展该节点,因为 该节点不可能扩展出对起点感兴趣的节点。 总结解题的过程,可以发现解决本题的关键有三点:一是稀疏图,正因为图中边比较稀 疏 所 以 我 们 可 以 用 Dijkstra+Priority Queue 的 方 法 将 求 最 短 路 径 的 时 间 复 杂 度 降 为 O(nlog2n);二是 rank 的范围很小,rank 的范围只有 10,所以我们只用了 10 次 Dijkstra 算法 就求得了所有点到特定 rank 的最短距离;三是感兴趣的点对只有很少,由于感兴趣的点对 只有 30n,我们通过只计算感兴趣点对的最短路径,将求点与点间最短路径的时间复杂度降 到了 O(nlog2n)。这三点,只要有一点没有抓住。本题就不可能得到解决。

5.4 间谍网络(AGE) 源程序名 可执行文件名 输入文件名 输出文件名 【问题描述】

age.???(pas, c, cpp) age.exe age.in age.out

由于外国间谍的大量渗入,国家安全正处于高度的危机之中。如果 A 间谍手中掌 握着关于 B 间谍的犯罪证据,则称 A 可以揭发 B。有些间谍收受贿赂,只要给他们一定数 量的美元,他们就愿意交出手中掌握的全部情报。所以,如果我们能够收买一些间谍的话, 我们就可能控制间谍网中的每一分子。 因为一旦我们逮捕了一个间谍, 他手中掌握的情报都 将归我们所有,这样就有可能逮捕新的间谍,掌握新的情报。 我们的反间谍机关提供了一份资料, 色括所有已知的受贿的间谍, 以及他们愿意收受的 具体数额。 同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。 假设总共有 n 个间谍 (n 不超过 3000),每个间谍分别用 1 到 3000 的整数来标识。 请根据这份资料,判断我们是否有可能控制全部的间谍,如果可以,求出我们所需要支 付的最少资金。否则,输出不能被控制的一个间谍。 【输入】 输入文件 age.in 第一行只有一个整数 n。 第二行是整数 p。表示愿意被收买的人数,1?p?n。 接下来的 p 行,每行有两个整数,第一个数是一个愿意被收买的间谍的编号,第二个数 表示他将会被收买的数额。这个数额不超过 20000。 紧跟着一行只有一个整数 r,1?r?8000。然后 r 行,每行两个正整数,表示数对(A, B), A 间谍掌握 B 间谍的证据。 【输出】 答案输出到 age.out。 如果可以控制所有间谍,第一行输出 YES,并在第二行输出所需要支付的贿金最小值。 否则输出 NO,并在第二行输出不能控制的间谍中,编号最小的间谍编号。 【样例 1】 age.in age.out 3 YES 2 110 1 10 2 100 2 13 23 【样例 2】 age.in age.out 4 NO 2 3 1 100 4 200 2 12 34 【算法分析】 根据题中给出的间谍的相互控制关系,建立有向图。找出有向图中的所有强连通分量, 用每个强连通分量中最便宜的点(需支付最少贿金的间谍)来代替这些强连通分量,将强连 通分量收缩为单个节点。 收缩强连通分量后的图中, 入度为 0 的节点即代表需要贿赂的间谍。 5.5 宫廷守卫

源程序名 guards.???(pas, c, cpp) 可执行文件名 guards.exe 输入文件名 guards.in 输出文件名 guards.out 【问题描述】 从前有一个王国,这个王国的城堡是一个矩形,被分为 M×N 个方格。一些方格 是墙,而另一些是空地。这个王国的国王在城堡里设了一些陷阱,每个陷阱占据一块空地。 一天,国王决定在城堡里布置守卫,他希望安排尽量多的守卫。守卫们都是经过严格训 练的,所以一旦他们发现同行或同列中有人的话,他们立即向那人射击。因此,国王希望能 够合理地布置守卫,使他们互相之间不能看见,这样他们就不可能互相射击了。守卫们只能 被布置在空地上,不能被布置在陷阱或墙上,且一块空地只能布置一个守卫。如果两个守卫 在同一行或同一列,并且他们之间没有墙的话,他们就能互相看见。(守卫就像象棋里的车 一样) 你的任务是写一个程序,根据给定的城堡,计算最多可布置多少个守卫,并设计出布置 的方案。 【输入】 第一行两个整数 M 和 N(1?M,N?200),表示城堡的规模。 接下来 M 行 N 列的整数,描述的是城堡的地形。第 i 行 j 列的数用 ai,j 表示。 ai,j=0,表示方格[i,j]是一块空地; ai,j=1,表示方格[i,j]是一个陷阱; ai,j=2,表示方格[i,j]是墙。 【输出】 第一行一个整数 K,表示最多可布置 K 个守卫。 此后 K 行,每行两个整数 xi 和 yi,描述一个守卫的位置。 【样例】 guards.in guards.out 34 2 2000 12 2221 33 0102 样例数据如图 5-2(黑色方格为墙,白色方格为空地,圆圈为陷阱,G 表示守卫) ○ ○ G ○ ○ G 【算法分析】 本题的关键在构图。 城堡其实就是一个棋盘。 我们把棋盘上横向和纵向连续的极长段 (不含墙) 都分离出来。 显然,每一段上最多只能放一个 guard,而且 guard 总是放在一个纵向段和一个横向段的交 界处,所以一个 guard 和一个纵向段和一个横向段有关。 我们把纵向段和横向段都抽象成图中的节点,如果一个纵向段和一个横向段相交的话,

就在两点之间连一条边。这样,guard 就成为了图中的边。前面得出的性质抽象成图的语言 就是, 每个点只能和一条边相连, 每条边只能连接一个纵向边的点和一个横向边的点。 因此, 这样的图是二分图,我们所求的正是二分图的匹配。而要布置最多的 guards,就是匹配数要 最大,即最大匹配。 图中节点数为 n(n?200) ,求最大匹配的时间复杂度为 O(n2.5)。 5.6 K-联赛 源程序名 kleague.???(pas, c, cpp) 可执行文件名 kleague.exe 输入文件名 kleague.in 输出文件名 kleague.out 【问题描述】 K-联赛职业足球俱乐部的球迷们都是有组织的训练有素的啦啦队员,就像红魔啦 啦队一样(2002 年韩日世界杯上韩国队的啦啦队)。这个赛季,经过很多场比赛以后,球迷们 希望知道他们支持的球队是否还有机会赢得最后的联赛冠军。 换句话说, 球队是否可以通过 某种特定的比赛结果最终取得最高的积分 (获胜场次最多)。(允许出现多支队并列第一的情 况。) 现在,给出每个队的胜负场数,wi 和 di,分别表示 teami 的胜场和负场(1?i?n)。还给出 ai,j,表示 teami 和 teamj 之间还剩多少场比赛要进行(1?i,j?n)。这里,n 表示参加联赛的队 数,所有的队分别用 1,2,?,n 来编号。你的任务是找出所有还有可能获得冠军的球队。 所有队参加的比赛数是相同的,并且为了简化问题,你可以认为不存在平局(比赛结果只有 胜或负两种)。 【输入】 第一行一个整数 n(1?n?25),表示联赛中的队数。 第二行 2n 个数,w1,d1,w2,d2,??,wn,dn,所有的数不超过 100。 第三行 n2 个数,a1,1,a1,2,?,a1,n,a2,1,?,a2,2,a2,n,?,an,1,an,2,?,an,n, 所有的数都不超过 10。ai,j=aj,i,如果 i=j,则 ai,j=0。 【输出】 仅一行,输出所有可能获得冠军的球队,按其编号升序输出,中间用空格分隔。 【样例 1】 kleague.in kleague.out 3 123 201102 022202220 【样例 2】 kleague.in kleague.out 3 12 402204 011101110 【样例 3】 kleague.in kleague.out 4 24 03311330 0002001001002000

【算法分析】 看一个队是否有希望夺冠,首先,这个队此后的比赛自然是赢越多越好,所以先让这个 队把以后的比赛都赢下来, 算出这个队最高能拿多少分。 下面关键就看是否有可能让其他队 的积分都低于刚才计算出的最高分。 建立一个网络,所有的球队作为图中的节点,每两个队之间的比赛也作为图中的节点。 从网络的源各连一条边到“比赛的节点” ,容量为两队间还剩的比赛场数。从“每个队的节 点”都连一条边到网络的汇,容量为这个队当前的积分与最高分之差。如果一个“比赛的节 点”代表的是 A 与 B 之间的比赛,那么从这个节点连两条边分别到“A 队的节点”和“B 队的节点” ,容量为无穷大。 如果这个网络的最大流等于所有还未进行的比赛的场次之和, 那么需要我们判断的那个 队抗有可能夺得冠军。 本题要我们找出所有可能夺冠的队, 那么只需枚举所有的球队, 判断它们是否有可能夺 冠即可。 5.7 机器调度 源程序名 machine.???(pas, c, cpp) 可执行文件名 machine.exe 输入文件名 machine.in 输出文件名 machine.out 【问题描述】 我们知道机器调度是计算机科学中一个非常经典的问题。 调度问题有很多种, 具体条件 不同,问题就不同。现在我们要处理的是两个机器的调度问题。 有两个机器 A 和 B。机器 A 有 n 种工作模式,我们称之为 mode_0,mode_l,??, mode_n-1。同样,机器 B 有 m 种工作模式,我们称之为 mode_0,mode_1,??,mode_m-1。 初始时,两台机器的工作模式均为 mode_0。现在有 k 个任务,每个工作都可以在两台机器 中任意一台的特定的模式下被加工。例如,job0 能在机器 A 的 mode_3 或机器 B 的 mode_4 下被加工,jobl 能在机器 A 的 mode_2 或机器 B 的 mode_4 下被加工,等等。因此,对于任 意的 jobi,我们可以用三元组(i,x,y)来表示 jobi 在机器 A 的 mode_x 或机器 B 的 mode_y 下 被加工。 显然,要完成所有工作,我们需要不时的改变机器的工作模式。但是,改变机器的工作 状态就必须重启机器,这是需要代价的。你的任务是,合理的分配任务给适当的机器,使机 器的重启次数尽量少。 【输入】 第一行三个整数 n,m(n,m<100) ,k(k<1000) 。接下来的 k 行,每行三个整数 i,x,y。 【输出】 只一行一个整数,表示最少的重启次数。 【样例】 machine.in machine.out 5 5 10 3 011 112 213 314 421

522 623 724 833 943 【问题分析】 本题所求的是工作模式的最少切换次数,实际上也就是求最少需要使用多少个工作模 式, 因为一个工作模式被切换两次肯定是不合算的, 一旦切换到一个工作模式就应该把这个 工作模式可以完成的工作都完成。 将两台机器的工作模式分别看成 n 个和 m 个节点。jobi 分别和机器 A 和 B 的 mode_x 和 mode_y 相关: jobi 要被完成, 就必须切换到机器 A 的 mode_x 或切换到机器 B 的 mode_y。 将 jobi 看作图中的一条边——连接节点 x 和节点 y 的边,那么这条边就要求 x 和 y 两个节 点中至少要有一个节点被取出来。这正符合覆盖集的性质。 我们构成的图是二分图,要求最少的切换次数,就是要使覆盖集最小。二分图的最小覆 盖集问题等价于二分图的最大匹配问题。 因此, 只需对此二分图求一个最大匹配即是我们要 求的答案。时间复杂度 。 5.8 公路修建 源程序名 road.???(pas, c, cpp) 可执行文件名 road.exe 输入文件名 road.in 输出文件名 road.out 【问题描述】 某国有 n 个城市,它们互相之间没有公路相通,因此交通十分不便。为解决这一“行路 难”的问题,政府决定修建公路。修建公路的任务由各城市共同完成。 修建工程分若干轮完成。在每一轮中,每个城市选择一个与它最近的城市,申请修建通 往该城市的公路。政府负责审批这些申请以决定是否同意修建。 政府审批的规则如下: (1)如果两个或以上城市申请修建同一条公路,则让它们共同修建; (2)如果三个或以上的城市申请修建的公路成环。如下图,A 申请修建公路 AB,B 申请修 建公路 BC,C 申请修建公路 CA。则政府将否决其中最短的一条公路的修建申请;

(3)其他情况的申请一律同意。 一轮修建结束后,可能会有若干城市可以通过公路直接或间接相连。这些可以互相:连 通的城市即组成“城市联盟” 。在下一轮修建中,每个“城市联盟”将被看作一个城市,发 挥一个城市的作用。 当所有城市被组合成一个“城市联盟”时,修建工程也就完成了。 你的任务是根据城市的分布和前面讲到的规则,计算出将要修建的公路总长度。 【输入】 第一行一个整数 n,表示城市的数量。(n?5000) 以下 n 行,每行两个整数 x 和 y,表示一个城市的坐标。(-1000000?x,y?1000000) 【输出】 一个实数,四舍五入保留两位小数,表示公路总长。(保证有惟一解)

【样例】 road.in road.out 修建的公路如图所示: 4 6.47 00 12 -1 2 04 【问题分析】 三条规则中的第二条是故弄玄虚。 如果三个或三个以上的城市申请修建的公路成环, 那 么这些公路的长度必然都相同,否则不满足“每个城市选择一个与它最近的城市,申请修建 通往该城市的公路” 。所以,如果成环,其实是任意去掉一条路。 本题要我们求的实际上是最小成成树,也就是说,按规则生成的是图的最小生成树。为 什么呢?很显然,按规则生成的应该是树。根据规则:每个城市选择一个与它最近的城市, 申请修建通往该城市的公路。那么,对于图中任意的环,环上最长边必被舍弃。这就与求最 小生成树的“破环法”完全相符了。 用 Prim 算法求图中的最小生成树,最小生成树上各边的长度只和即是所求的答案。时 间复杂度为 O(n2)。 但是,本题还有其特殊性。本题是在 Euclid 空间求最小生成树,Euclid 空间最小生成树 有 O(nlog2n)的算法,是用 Voronoi 图+Kruskal 算法(或用 Prim+heap 代替 Kruskal)实现的。 5.9 速度限制 源程序名 speed.???(pas, c, cpp) 可执行文件名 speed.exe 输入文件名 speed.in 输出文件名 speed.out 【问题描述】 在这个繁忙的社会中,我们往往不再去选择最短的道路,而是选择最快的路线。开车时 每条道路的限速成为最关键的问题。不幸的是,有一些限速的标志丢失了,因此你无法得知 应该开多快。一种可以辩解的解决方案是,按照原来的速度行驶。你的任务是计算两地间的 最快路线。 你将获得一份现代化城市的道路交通信息。为了使问题简化,地图只包括路口和道路。 每条道路是有向的,只连接了两条道路,并且最多只有一块限速标志,位于路的起点。两地 A 和 B, 最多只有一条道路从 A 连接到 B。 你可以假设加速能够在瞬间完成并且不会有交通 堵塞等情况影响你。当然,你的车速不能超过当前的速度限制。 【输入】 输入文件 SPEED.IN 的第一行是 3 个整数 N,M 和 D(2<=N<=150),表示道路的数目, 用 0..N-1 标记。M 是道路的总数,D 表示你的目的地。接下来的 M 行,每行描述一条道路, 每行有 4 个整数 A(0?A<N),B(0?B<N),V(0?V?500)and L(1?L?500),这条路是从 A 到 B 的,速度限制是 V,长度为 L。如果 V 是 0,表示这条路的限速未知。如果 V 不为 0, 则经过该路的时间 T=L/V。否则 T=L/Vold,Vold 是你到达该路口前的速度。开始时你位于 0 点,并且速度为 70。 【输出】 输出文件 SPEED.OUT 仅一行整数,表示从 0 到 D 经过的城市。 输出的顺序必须按照你经过这些城市的顺序,以 0 开始,以 D 结束。仅有一条最快路 线。

【样例】 speed.in speed.out 6 15 1 05231 0 1 25 68 0 2 30 50 0 5 0 101 1 2 70 77 1 3 35 42 2 0 0 22 2 1 40 86 2 3 0 23 2 4 45 40 3 1 64 14 3 5 0 23 4 1 95 8 5 1 0 84 5 2 90 64 5 3 36 40 【问题分析】 首先, 利用预处理计算任意两个节点之间只经过无限速标志的路的最短距离。 这可以用 F1ovd 算法得到,时间复杂度为 O(n3)。 计算城市 1 到城市 D 之间最快路径时,只需对 Dijkstra 稍作修改即可:在 Dijkstra 算法 中, 用一个已计算出最短路径的节点去刷新其他节点当前最短路径长度时, 除了要枚举有限 速标志的路以外, 还要在此路的基础上, 枚举通过此路后要经过无限速标志的路到达的节点。 时间复杂度为 O(n2+mn),即 O(mn)。

第六章 树 6.1 排序二叉树 源程序名 tree.???(pas, c, cpp) 可执行文件名 tree.exe 输入文件名 tree.in 输出文件名 tree.out 【问题描述】 一个边长为 n 的正三角形可以被划分成若干个小的边长为 1 的正三角形,称为单位三 角形。如右图,边长为 3 的正三角形被分成三层共 9 个小的正三角形,我们把它们从顶到 底,从左到右以 1~9 编号,见右图。同理,边长为 n 的正三角形可以划分成 n2 个单位三 角形。 四个这样的边长为 n 的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依 顺时针次序(从顶向底视角)编号为 A, B, C,底面编号为 D。侧面的 A, B, C 号三角形以 三棱锥的顶点为顶,底面的 D 号三角形以它与 A,B 三角形的交点为顶。左图为三棱锥展 开后的平面图,每个面上标有圆点的是该面的顶,该图中侧面 A, B, C 分别向纸内方向折 叠即可还原成三棱锥。我们把这 A,B、C、D 四个面各自划分成 n2 个单位三角形。 对于任意两个单位三角形,如有一条边相邻,则称它们为相邻的单位三角形。显然,每

个单位三角形有三个相邻的单位三角形。现在,把 1—4n2 分别随机填入四个面总共 4n2 个 单位三角形中。 现在要求你编程求由单位三角形组成的最大排序二叉树。 所谓最大排序二叉树, 是指在 所有由单位三角形组成的排序二叉树中节点最多的一棵树. 对于任一单位三角形, 可选它三 个相邻的单位三角形中任意一个作为父节点,其余两个分别作为左孩子和右孩子。当然,做 根节点的单位三角形不需要父节点, 而左孩子和右孩于对于二叉树中的任意节点来说并不是 都必须的。 【输入】 输入文件为 tree.in。其中第一行是一个整数 n(1<=n<=18),随后的 4n2 个数,依次为三 棱锥四个面上所填的数字。 【输出】 输出文件为 tree.out。其中仅包含一个整数,表示最大的排序二又树所含的节点数目。 【样例】 输入文件对应下图:

A B C tree.in tree.out 3 22 13 9 17 19 25 15 1 33 20 26 28 32 21 18 7 31 12 17 2 29 24 8 6 3 23 16 36 5 34 27 4 35 11 30 14 10 输出样例文件对应的最大排序二叉树如下图所示:

D

【知识准备】 记忆化搜索的基本概念和实现方法。 【算法分析】 在讨论问题的解法之前,我们先来看看二叉排序树的性质。 二叉排序树是一棵满足下列性质的二又树: 性质 1 它或是一棵空树,或是一棵二叉树,满足左子树的所有结点的值都小于根结点 的值,右子树的所有结点的值都大于根结点的值; 性质 2 它若有子树,则它的子树也是二叉排序树。 根据性质 1,我们可以知道,二叉排序树的左右子树是互不交叉的。也就是说,如果确 定了根结点, 那么我们就可以将余下的结点分成两个集合, 其中一个集合的元素可能在左子 树上,另一集合的元素可能在右子树上,而没有一个结点同时可以属于两个集合。这一条性

质,满足了无后效性的要求,正因为二叉排序树的左右子树是互不交叉的,所以如果确定根 结点后,求得的左子树,对求右子树是毫无影响的。因此,如果要使排序树尽可能大,就必 须满足左右子树各自都是最大的,即局部最优满足全局最优。 根据性质 2,二叉排序树的左右子树也是二叉排序树。而前面已经分析得到,左右子树 也必须是极大的。所以,求子树的过程也是一个求极大二叉排序树的过程,是原问题的一个 子问题。那么,求二叉排序树的过程就可以分成若干个阶段来执行,每个阶段就是求一棵极 大的二叉排序子树。 由此,我们看到,本题中,二叉排序树满足阶段性(性质 2)和无后效性(性质 1) ,可 以用动态规划解决。 下面来看具体解决问题的方法。 不用说,首先必须对给出的正三棱锥建图,建成一张普通的无向图。 根据正三棱锥中结点的性质,每个结点均与三个结点相连。而根据二叉排序树的性质, 当一个结点成为另一个结点的子结点后,它属于左子树还是右子树也就确定下来了。所以, 可以对每个结点进行状态分离, 分离出三种状态——该结点作为与它相连的三个结点的子结 点时,所得的子树的状态。但是,一个子结点可以根据它的父结点知道的仅仅是该子树的一 个界(左子树为上界,右子树为下界) ,还有一个界不确定,所以还需对分离出来的状态再 进行状态分离,每个状态代表以一个值为界(上界或下界)时的子树状态。 整个分离过程如下图所示:

确定了状态后,我们要做的事就是推出状态转移方程。 前面已经提到,一个极大的二叉排序树,它的左右子树也必须是极大的。因此,如果我 们确定以结点 n 为根结点,设所有可以作为它左子结点的集合为 N1,所有可以作为它右子 结点的集合为 N2,则以 n 为根结点、结点大小在区间[l, r]上的最大二叉排序树的结点个数 为: 我们所要求的最大的二叉排序树的结点个数为: ,其中 n 为结点的总个数 从转移方程来看,我们定义的状态是三维的。那么,时间复杂度理应为 O(n3)。其实并 非如此。每个结点的状态虽然包含下界和上界,但是不论是左子结点还是右子结点,它的一 个界取决于它的父结点, 也就是一个界可用它所属的父结点来表示, 真正需要分离的只有一 维状态, 要计算的也只有一维。 因此, 本题时间复杂度是 O(n2) (更准确的说应该是 O(3n2)) 。 此外,由于本题呈现一个无向图结构,如果用递推形式来实现动态规划,不免带来很大

的麻烦。因为无向图的阶段性是很不明显的,尽管我们从树结构中分出了阶段。不过,实现 动态规划的方式不仅仅是递推, 还可以使用搜索形式——记忆化搜索。 用记忆化搜索来实现 本题的动态规划可以大大降低编程复杂度。 6.2 树的重量 源程序名 weight.???(pas, c, cpp) 可执行文件名 weight.exe 输入文件名 weight.in 输出文件名 weight.out 【问题描述】 树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树,其叶节点表 示一个物种,两个叶节点之间的距离表示两个物种的差异。现在,一个重要的问题是,根据 物种之间的距离,重构相应的“进化树” 。 令 N={1..n},用一个 N 上的矩阵 M 来定义树 T。其中,矩阵 M 满足:对于任意的 i,j, k,有 M[i,j]+M[j,k]<=M[i,k]。树 T 满足: 1.叶节点属于集合 N; 2.边权均为非负整数; 3.dT(i,j)=M[i,j],其中 dT(i,j)表示树上 i 到 j 的最短路径长度。 如下图,矩阵 M 描述了一棵树。 树的重量是指树上所有边权之和。对于任意给出的合法矩阵 M,它所能表示树的重量是惟 一确定的,不可能找到两棵不同重量的树,它们都符合矩阵 M。你的任务就是,根据给出 的矩阵 M,计算 M 所表示树的重量。下图是上面给出的矩阵 M 所能表示的一棵树,这棵树 的总重量为 15。 【输入】 输入数据包含若干组数据。每组数据的第一行是一个整数 n(2<n<30)。其后 n-l 行,给出的 是矩阵 M 的一个上三角(不包含对角线),矩阵中所有元素是不超过 100 的非负整数。输入 数据保证合法。 输入数据以 n=0 结尾。 【输出】 对于每组输入,输出一行,一个整数,表示树的重量。 【样例】 weight.in weight.out 5 15 5 9 12 8 71 8 11 7 51 4 4 15 36 60 31 55 36 0

【知识准备】 树的基本特征。 【算法分析】 本题是一道涉及树性质的算法题, 所以我们应该以树的性质为突破口, 来讨论本题的算 法。 首先来看一下简单的实例,就以题目中给出的例子来说明。下图所示的树,有 5 个叶子 节点,两个内点,6 条边。我们已知的信息是任意两个叶子节点之间的距离,所以我们讨论 的必然是叶子节点之间的关系,不可能涉及内点。 从图中我们可以看出,有些叶子结点是连在同一个内点上的,如①和②;也有些连在不 同的内点上,如①和④。我们来看连在同一内点上的叶子节点有什么特殊的性质。就以①和 ②为例,①到③、④、⑤的距离分别为 9、12、8,②到③、④、⑤的距离分别为 8、11、7, 正好都相差 l。这个“1”差在哪里呢?①连到内点的边长为 3,②连到内点的边长为 2,两 者相差为 1。所以,相差的“1”正好就是两节点连到内点上的边长的差。再看①到②的距 离,由于两叶子节点都是连在同一个内点上的,所以他们之间的距离,就是两者到内点的边 长和。知道的边长和以及边长差,求出两边长就不难做到了。 (注意:两叶子节点连到内点 的边长是未知的) 再看一下不连在同一内点上的节点,①和④。①到②、③、⑤的距离分别为 5、9、8, ④到②、③、⑤的距离分别为 11、5、4,没有一个统一的“差” 。 其实,前面的结论都是非常直观而显然的,只不过关键是如何去利用。我们先来总结一 下前面的结论: (1)如果两叶子节点连在同一个内点上,则它们到其他叶子节点的距离有一个统一的 “差” ; (2)如果两叶子节点连在不同的内点上,则它们到其他叶子节点的距离没有一个统一 的“差” ; ○ / ○────●────● a \ ○ 值得注意的是,图 6-3 中的 a 点不能算内点。我们所指的内点是至少连接两个叶子节点 的点,像 a 这样的点完全可以去掉,不会影响树的权值和,如下图。 ○ / ○─────────● \ ○ (3)如果两叶子节点连在同一个内点上,则它们之间的距离等于它们各自到内点的边 长的和。 根据(1)和(2)两条性质,很容易得到判断连接相同内点的两个叶子节点的方法,即 必须满足它们到其他所有叶子节点有统一的距离差(充分且必要) 。 找到两个连接相同内点的叶子节点并计算出它们各自到内点的边长 (不妨设为 l1 和 l2) 以后,我们可以作这样的操作:删去一个节点,令另一个节点到内点的边长为 l1+l2。这样 得到的新树,权值和与原树相同,但叶子节点少了一个,如下图。

反复利用上述操作, 最后会得到一棵只有两个叶子节点的树, 这两个节点之间的边长就 是原树的权值和。 算法需要反复执行 n-2 次删除节点的操作。每次操作中,需要枚举两个叶子节点,并且 还要有一个一维的判断,时间复杂度是 O(n3)的。所以,整个算法的时间复杂度是 O(n4)的。 对于一个规模仅有 30 的题目来说,O(n4)的算法足以解决问题了。当然,算法本身应该还是 有改进的余地的,不过这里就不加以讨论了。 6.3 信号放大器 源程序名 booster.???(pas, c, cpp) 可执行文件名 booster.exe 输入文件名 booster.in 输出文件名 booster.out 【问题描述】 树型网络是最节省材料的网络。所谓树型网络,是指一个无环的连通网络,网络中任意 两个结点间有且仅有一条通信道路。 网络中有一个结点是服务器, 负责将信号直接或间接地发送到各终端机。 如图 6-4, server 结点发出一个信号给结点 a 和 c,a 再转发给 b。如此,整个网络都收到这个信号了。 server a b ●────○────○ │ │ ○ 但是,实际操作中,信号从一个结点发到另一个结点,会出现信号强度的衰减。衰减量 一般由线路长度决定。 server 3 a 2 b ●────○────○ │ │1 ○ 如上图, 边上所标的数字为边的衰减量。 假设从 server 出发一个强度为 4 个单位的信号, 发到结点 a 后强度衰减为 4-3=1 个单位。结点 a 再将其转发给结点 b。由于信号强度为 1, 衰减量为 2,因此信号无法发送到 b。 一个解决这一问题的方法是, 安装信号放大器。 信号放大器的作用是将强度大于零的信 号还原成初始强度(从服务器出发时的强度) 。 上图中,若在结点 a 处安装一个信号放大器,则强度为 4 的信号发到 a 处,即被放大至 4。这样,信号就可以被发送的网络中的任意一个节点了。为了简化问题,我们假定每个结 点只处理一次信号,当它第二次收到某个信号时,就忽略此信号。 你的任务是根据给出的树型网络,计算出最少需要安装的信号放大器数量。 【输入】 第一行一个整数 n,表示网络中结点的数量。 (n<=100000) 第 2~n+1 行,每行描述一个节点的连接关系。其中第 i+1 行,描述的是结点 i 的连接关 系:首先一个整数 k,表示与结点 i 相连的结点的数量。此后 2k 个数,每两个描述一个与结 点 i 相连的结点,分别表示结点的编号(编号在 1~n 之间)和该结点与结点 i 之间的边的信 号衰减量。结点 1 表示服务器。 最后一行,一个整数,表示从服务器上出发信号的强度。 【输出】

一个整数,表示要使信号能够传遍整个网络,需要安装的最少的信号放大器数量。 如果不论如何安装信号放大器,都无法使信号传遍整个网络,则输出“No solution.” 【样例】 booster.in booster.out 4 1 22331 21342 111 122 4 【问题分析】 用贪心算法求解。从叶结点往根结点回推,当信号强度不够继续传送时,即增加一个信 号放大器。算法的时间复杂度为 O(n)。 6.4 “访问”术馆 源程序名 gallery.???(pas, c, cpp) 可执行文件名 gallery.exe 输入文件名 gallery.in 输出文件名 gallery.out 【问题描述】 经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。 艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer 知道每个展室里 藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要 5 秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画。 【输入】 第 1 行是警察赶到的时间, 以 s 为单位。 第 2 行描述了艺术馆的结构, 是一串非负整数, 成对地出现:每一对的第一个数是走过一条走廊的时间,第 2 个数是它末端的藏画数量;如 果第 2 个数是 0, 那么说明这条走廊分叉为两条另外的走廊。 数据按照深度优先的次序给出, 请看样例。 一个展室最多有 20 幅画。通过每个走廊的时间不超过 20s。艺术馆最多有 100 个展室。 警察赶到的时间在 10min 以内。 【输出】 输出偷到的画的数量。 【样例】 gallery.in(如图 6-6) gallery.out 60 2 7 0 8 0 3 1 14 2 10 0 12 4 6 2 【问题分析】 用树型动态规划求解。首先,题目保证数是二叉树。定义状态 f(n, t)表示在结点 n 所在 子树上花 t 时间所能取到的最大分值,则状态转移方程为 f(n, t)=max{f(left, t0)+f(right, t-t0)} 其中 left 和 right 为 n 的左右子结点,t0 的取值范围为[0, t]。 算法的时间复杂度为 O(n3)。

6.5 聚会的快乐 源程序名 party.???(pas, c, cpp) 可执行文件名 party.exe 输入文件名 party.in 输出文件名 party.out 【问题描述】 你要组织一个由你公司的人参加的聚会。 你希望聚会非常愉快, 尽可能多地找些有趣的 热闹。但是劝你不要同时邀请某个人和他的上司,因为这可能带来争吵。给定 N 个人(姓名, 他幽默的系数,以及他上司的名字),编程找到能使幽默系数和最大的若干个人。 【输入】 第一行一个整数 N(N<100)。接下来有 N 行,每一行描述一个人的信息,信息之间用空 格隔开。姓名是长度不超过 20 的字符串,幽默系数是在 0 到 100 之间的整数。 【输出】 所邀请的人最大的幽默系数和。 【样例】 party.in party.out 5 8 BART 1 HOMER HOMER 2 MONTGOMERY MONTGOMERY 1 NOBODY LISA 3 HOMER SMITHERS 4 MONTGOMERY 【问题分析】 用动态规划求解。首先,很显然公司的人员关系构成了一棵树。设 f[a]为 a 参加会议的 情况下,以他为根的子树取得的最大幽默值;g[a]为 a 不参加会议的情况下,以他为根的子 树取得的最大幽默值。那么,状态转移方程就是: f[a]=g[b1]+g[b2]+…+g[bk]+1 g[a]=max(f[b1], g[b1])+max(f[b2], g[b2])+…+max(f[bk], g[bk]) 其中 b1, b2, ?, bk 为 a 的子结点。 最后的答案就是 max(f[root], g[root]),root 是树根。

6.6 重建道路 源程序名 roads.???(pas, c, cpp) 可执行文件名 roads.exe 输入文件名 roads.in 输出文件名 roads.out 【问题描述】 一场可怕的地震后, 人们用 N 个牲口棚(1?N?150, 编号 1..N)重建了农夫 John 的牧场。

由于人们没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是惟一 的。因此,牧场运输系统可以被构建成一棵树。John 想要知道另一次地震会造成多严重的 破坏。有些道路一旦被毁坏,就会使一棵含有 P(1?P?N)个牲口棚的子树和剩余的牲口棚 分离,John 想知道这些道路的最小数目。 【输入】 第 1 行:2 个整数,N 和 P 第 2..N 行:每行 2 个整数 I 和 J,表示节点 I 是节点 J 的父节点。 【输出】 单独一行,包含一旦被破坏将分离出恰含 P 个节点的子树的道路的最小数目。 【样例】 roads.in roads.out 11 6 2 12 13 14 15 26 27 28 49 4 10 4 11 【样例解释】 如果道路 1-4 和 1-5 被破坏,含有节点(1,2,3,6,7,8)的子树将被分离出来 【问题分析】 用树型动态规划求解。定义 f(n, m)为在 n 为根的子树中取 m 个节点的最小代价,则状 态转移方程为: f(n, m)=min{f(n0, m0)+f(n1, m1)+f(n2, m2)+…+f(nk, mk)} 其中,n0, n1, n2, ?, nk 为 n 的 k 个儿子,m0+m1+m2+?+mk=m,并且定义 f(ni, 0)=1。 最后的结果为: min{f(root, p), min{f(n, p) | n≠root}}

6.7 有线电视网 源程序名 tele.???(pas, c, cpp) 可执行文件名 tele.exe 输入文件名 tele.in 输出文件名 tele.out 【问题描述】 某收费有线电视网计划转播一场重要的足球比赛。 他们的转播网和用户终端构成一棵树 状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的 内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的, 一场转播 的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛, 有线电视网有权决定给哪 些用户提供信号而不给哪些用户提供信号。 写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能 多。 【输入】 输入文件的第一行包含两个用空格隔开的整数 N 和 M,其中 2?N?3000,1?M ?N-1,N 为整个有线电视网的结点总数,M 为用户终端的数量。 第一个转播站即树的根结点编号为 1,其他的转播站编号为 2 到 N-M, 用户终端编号为 N-M+1 到 N。 接下来的 N-M 行每行表示—个转播站的数据,第 i+1 行表示第 i 个转播站的数据,其 格式如下: K A1 C1 A2 C2 … Ak Ck K 表示该转播站下接 K 个结点(转播站或用户), 每个结点对应一对整数 A 与 C, A 表示 结点编号,C 表示从当前转播站传输信号到结点 A 的费用。最后一行依次表示所有用户为 观看比赛而准备支付的钱数。 【输出】 输出文件仅一行,包含一个整数,表示上述问题所要求的最大用户数。 【样例】 tele.in tele.out 53 2 22253 23243 342 【样例解释】 如右图所示,共有五个结点。结点①为根结点,即现场直播站,②为一 个中转站,③④⑤为用户端,共 M 个,编号从 N-M+1 到 N,他们为观看比 赛分别准备的钱数为 3、4、2,从结点①可以传送信号到结点②,费用为 2, 也可以传送信号到结点⑤,费用为 3(第二行数据所示) ,从结点②可以传输信号到结点③, 费用为 2。也可传输信号到结点④,费用为 3(第三行数据所示) ,如果要让所有用户(③④ ⑤)都能看上比赛,则信号传输的总费用为: 2+3+2+3=10,大于用户愿意支付的总费用 3+4+2=9,有线电视网就亏本了,而只让③④两 个用户看比赛就不亏本了。 【问题分析】 用动态规划求解。状态这样定义,设 F[A, M]为 A 结点下支持 M 个用户所能得到的最 大赢利。转移方程为: F[A, M]=Max{F[B1, M1]+F[B2, M2]+?+F[Bk, Mk] | Bi 是 A 的子结点,M1+M2+? +Mk=M} 可以考虑将多叉数转换成二叉树来做,也可以考虑动态地分配内存。这样,空间复杂度 约为 O(n),时间复杂度为 O(n2)。 第七章 搜索 7.1 最多因子数 源程序名 可执行文件名

divisors.???(pas, c, cpp) divisors.exe

输入文件名 divisors.in 输出文件名 divisors.out 【问题描述】 数学家们喜欢各种类型的有奇怪特性的数。例如,他们认为 945 是一个有趣的数,因为 它是第一个所有约数之和大于本身的奇数。 为了帮助他们寻找有趣的数, 你将写一个程序扫描一定范围内的数, 并确定在此范围内 约数个数最多的那个数。不幸的是,这个数和给定的范围的都比较大,用简单的方法寻找可 能需要较多的运行时间。所以请确定你的算法能在几秒内完成最大范围内的扫描。 【输入】 只有一行,给出扫描的范围,由下界 L 和上界 U 确定。满足 2?L?U?1000000000。 【输出】 对于给定的范围,输出该范围内约数个数 D 最多的数 P。若有多个,则输出最小的 那个。请输出“Between L and U,P has a maximum of D divisors. ” ,其中 L,U,P 和 D 的 含义同前面所述。 【样例】 divisors.in divisors.out 1000 2000 Between 1000 and 2000, 1680 has a maximum of 40 divisors. 【知识准备】 深度优先搜索的基本实现方法及剪枝的基本概念。 【算法分析】 本题的要求是,求出一个给定区间内的含因子数最多的整数。 首先,有必要明确一下如何求一个数的因子数。若一个数 N 满足 N=P1N1?P2N2?P3N3???PmNm,其中 P1, P2, ?, Pm 是 N 的 m 个质因子。则 N 的约数个 数为(N1+1)?(N2+1)?(N3+1)???(Nm+1)。这一公式可以通过乘法原理来证明。 有了求因子数的公式后,最容易想到的算法就是,枚举区间内的每个整数,统计它们的 约数个数。这个算法很容易实现,但是时间复杂度却相当高。因为区间中整数的范围是 1~ 1000000000,整个枚举一遍并计算因子数的代价约为 109×(109)0.5=1013.5。这个规模是无 法忍受的。所以,我们需要尽量优化时间。 分析一下枚举的过程就会发现,如果我们分别枚举两个数 n 和 p?n(p 为一相对较大的 质数) ,那么我们将重复计算两次 n 的因子数。其实,如果枚举顺序得当的话,完全可以在 n 的基础上去计算 p?n,而如果能在 n 的基础上计算 p?n,就相当于计算 p?n 的因子数只用 了 O(1)的时间。这是一个比较形象的例子,类似的(可能相对更复杂一些)重复计算在枚 举过程中应该是普遍存在的。这就是枚举效率低的根本所在。为了解决这一重复,我们可以 选取另一种搜索顺序——枚举质因子。这样的搜索顺序可以避免前面所说了类似 n 和 p?n 的重复计算。 定义 number 为当前搜索到的数。 初始时, 令 number=1, 然后从最小的质数 2 开始枚举, 枚举因子中包含 0 个 2、1 个 2、2 个 2、?、k 个 2 的情况??直至 number?2k 大于区间的 上限(max)。对于每个“2k 的情况” ,令 number:=number*2k,在这个基础上,再枚举因子 3 的情况。 然后在 3 的基础上枚举因子 5 的情况, 然后是 7 的情况??整个过程是一个深度搜 索的过程,搜索的过程中,利用前面提到的求因子数的公式可以算出当前的 number 的因子 数供下一层枚举继承。当 number 大于等于区间下限(min)时,我们就找到了一个区间内的数 (枚举的过程已保证 number 不超过上界)。所有枚举得到的区间内的数中,因子数的最大值 就是我们要求的目标。 这样的枚举完全去除了重复计算, 但是这还是不够的, 因为光 1~1000000000 内的数每

枚举一遍就有 109 个单位的操作。 所以, 我们还需要找到一些剪枝的方法, 进一步优化时间。 我们看到,如果当前搜索状态为(from, number, total),其中,from 是指当前枚举到的质 因子(按从小到大枚举) , total 是指 number 中包含的因子数。那么剩下的因子数最多为 q=logfrommax/number,这些因子组成的因子个数最大为 2q。因此,当前所能取到的(理想 情况)最大约数个数就是 total?2q。如果这个数仍然无法超过当前最优解,则这一分支不可 能产生最优解,可以剪去。 此外,如果[(min-1)/number]=[max/number],则表示以当前状态搜索下去,结果肯定不 在区间内了,就无法产生合法解,也可剪去。不过, 这一剪枝作用不是很大, 因为即使不剪, 再搜索一层也就退出了。 以上两个剪枝,前一个是最优化剪枝,后一个是合法性剪枝。相比较而言,前一个剪枝 的作用要大得多。 下面我们用平摊分析的方法来讨论一下搜索的复杂度。由于枚举的过程中没有重复计 算,每枚举一个质因子,都可以得到一个不同的 number(number?max),所以可以将每一个 单位的枚举质因子的代价与一个不超过 max 的 number 对应, 并且还可在两者之间建立双射。 不同的 number 最多只有 max 个,所以枚举的总代价不超过 O(max),max?109。 加上了剪枝以后,计算总代价就远远小于 O(max)了。从运行效果来看,即便是最大数 据,也可以很快出解。 从本题的解决过程中可以看到,最关键的有两步: (1)采用合理的搜索顺序,避免重复计算; (2)利用最优化剪枝和合法性剪枝,剪去一些不可能产生最优解或合法解的分支。 这两种优化的方法在搜索中的地位是极其重要的, 当然可能在本题中的重要性体现得格 外突出。

7.2 黑白棋游戏 源程序名 game.???(pas, c, cpp) 可执行文件名 game.exe 输入文件名 game.in 输出文件名 game.out 【问题描述】 黑白棋游戏的棋盘由 4×4 方格阵列构成。棋盘的每一方格中放有 1 枚棋子,共有 8 枚 白棋子和 8 枚黑棋子。这 16 枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有 1 条公共边的 2 个方格称为相邻方格。 一个方格最多可有 4 个相邻方格。 在玩黑白棋游戏时, 每一步可将任何 2 个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态, 编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。 【输入】 输入文件共有 8 行。前四行是初始游戏状态,后四行是目标游戏状态。每行 4 个数分别 表示该行放置的棋子颜色。 “0”表示白棋; “1”表示黑棋。 【输出】 输出文件的第一行是着棋步数 n。接下来 n 行,每行 4 个数分别表示该步交换棋子的两 个相邻方格的位置。例如,abcd 表示将棋盘上(a,b)处的棋子与(c,d)处的棋子换位。 【样例】 game.in game.out 1111 4

0000 1222 1110 1424 0010 3242 1010 4344 0101 1010 0101 【知识准备】 (1)宽度优先搜索的基本概念; (2)位操作相关知识。 【算法分析】 本题是一道典型的宽度优先搜索题。 宽度优先搜索的方法本身应该是很显然的: 根据题 目的描述,对于任意一个棋盘状态,可以通过交换相邻两个格子中的棋子得到新的状态(一 次最多得到 24 个新状态) 。所以,我们可以从题目给出的起始状态开始不停的扩展,直至扩 展出目标状态。最后,只需输出扩展的路径即可。 上述算法已经可以完全解决本题了。但是,我们现在要继续往细节里讨论本题,讨论本 题的实现。 宽度优先搜索的核心是状态的扩展, 状态的扩展是通过状态转换实现的。 普通的状态转 换的方法就是按照题目的定义模拟实现。 这里, 我们要讨论的是高效简洁的状态转换的方法。 首先是状态的表示。题目中的棋盘是由 16 个格子组成的(4×4),如下图。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 这 16 个格子,每个格子里非 0 即 1,所以可以将棋盘写成一个长度为 16 的 01 串。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 这个 0l 串可以用一个 16bit 的整数来表示。也就是说,我们可以用一个 0~65535 的整 数来表示一个状态。 下面最关键的就是状态的转换了。 根据题目的定义, 每次操作可以交换棋盘上相邻两个 格子中的棋子。显然,如果相邻两个格子中的棋子相同,交换是没有意义的,所以我们只需 要考虑相邻格子中棋子颜色不同的情况。相邻有两种情况,左右相邻和上下相邻。如图,a1 和 a2 为左右相邻, 而 a8 和 a12 为上下相邻。 我们讨论状态转换的时候,将对这两种 “相邻” 分别处理。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 图 7-2 首先来看左右相邻的情况,以 a15 和 a16 为例。它们交换以后,得到的棋盘状态为: a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a16 a15 图 7-3

但是, 从另一个角度来考虑问题, a15=??a16, 所以经过转换后, 就相当于将 a15 和 a16 取反。从位操作的角度来看,设原状态为 s,那么 a15 和 a16 交换后得到的新状态 s15 为: s15=s xor 3 同样的,还可以推出 a14 和 a15 交换后得到的新状态 s14 为: s14=s xor 6=s xor (3*21) 当然,还有以下很多状态公式: s13=s xor 12=s xor(3*22) s11=s xor 48=s xor(3*24) s10=s xor 96=s xor(3*25) 这里有两个需要注意之点: (1)交换的两个棋子的颜色必须不同,否则公式不成立; (2)根据状态转换的定义 s4、s8、s12、s16 对应的公式不成立,因为它们右边没有相 邻的棋子。 最后,我们总结一下左右相邻情况下的状态转换公式(棋子颜色必须不同) sk=s xor(3*215-k),其中 k≠4, 8, 12, 16 与“左右相邻”对应的是“上下相邻” 。 “上下相邻”情况的分析与“左右相邻”类似, 这里就不详细展开了,只列出转换的公式(同样,棋子颜色也必须不同) sk=s xor(17*212-k),其中 k?12 有了上面两个状态转换的公式,我们只需将起始状态和目标状态转换成 16bit 的整数, 利用公式从起始状态扩展至目标状态即可。整个过程的时间复杂度是 O(24*216)。 从另一个角度考虑问题。 本题给出了起始状态和目标状态, 那么我们完全可以从这两个 状态开始,分别扩展——也就是用双向宽度优先搜索的方法来解决本题。一般来说,双向搜 索扩展出的状态总数要比单向少很多,时间和空间复杂度都会有所降低。 7.3 纵横填字游戏 源程序名 puzzle.???(pas, c, cpp) 可执行文件名 puzzle.exe 输入文件名 puzzle.in 输出文件名 puzzle.out 【问题描述】 这个题目要求你编写一个程序来解决一个纵横填字游戏。 这个游戏比我们在报纸上见到的通常的填字游戏要简单。 游戏仅给出单词的起始位 置,方面(横向或纵向)以及单词的长度。只要单词的长度正好,游戏中能填入任何一个来自 词典的单词。 在游戏中单词相交处的字母必须相同,当然,任何单词只准使用一次。 思考一下以下这个游戏。 例如,假定从上到下有 5 行,用 0 到 4 来表示,从左到右有 5 列,用 0 到 4 来表示。我们用 (X, Y)来表示填字游戏中第 X 列和第 Y 行的字母。

在这个游戏中,我们需填入 5 个单词:在(0, 0)的右边填入一个 4 个字母的单词,在(0, 0)的 下方填入一个 4 个字母的单词,在(2, 0)的下方填入一个 4 个字母的单词,在(0, 2)的右边填

入一个 3 个字母的单词,最后在(2, 3)的右边填入一个 3 个字母的单词。字典上所有的单词 都能使用但最多只能使用一次。例如,以下是一个可能的解决方案。 (0, 0)右边,LATE (0, 0)下面,LIED (2, 0)下面,TELL (2, 3)右边,LOW 【输入】 输入文件的第一行是作为字典使用的—个文本文件名, 你可以假定这个文件存在, 是可 读的并且包含最多不超过 100000 个单词,并且按词典顺序存储,每行一个单词。字典中所 有的单词所含的字母可以是大写或小写(在这个问题中字母的大小写是无关紧要的)。你可以 假设字典中所有单词的长度不超过 20 个字符。输入文件的下一行包含一个整数 n(n?15), 表示要填的单词的数量。 接下来的 n 行中每行给出关于一个单词的提示, 在每个提示中分别 给出单词的首字母在填字游戏中的列和行的位置, 后面根据单词的方向是横向还是纵向, 相 应跟字符 A 或字符 D,最后一个数表示该单词的长度,以上数据之间均用空格隔开。 你能作以下的进一步的假设。 (1)填字游戏的尺寸不超过 10×10。 (2)游戏盘中放得下所有的单词。 (3)用给定的词典是能够破解出该游戏的。 【输出】 输出文件应该包含 n 行,输出游戏中可填入的所有单词。单词应该每行出现一个,并且 按输入文件中提示的顺序输出。 每个单词中所有的字母必须是大写的。 所有的单词必须来自 给定的词典文件(忽略大小写)。任何单词只能使用一次。对于给定输入文件可能有大量的正 确解决方案,你只须输出其中的任意一个解决方案。 【样例】 puzzle.in puzzle.out words.txt LATE 5 LIED 0 0A4 TELL 00D4 EEL 20D4 LOW 0 2A3 2 3A3 【知识准备】 (1)深度优先搜索的基本实现方法; (2)Hash 表的基本理论及其实现方法(主要是“吊桶处理冲突法” ) 。 【算法分析】 本题是一个规模巨大的搜索问题,其规模主要体现在词典(单词表)中的单词数(最多 可达到 100000) ,这意味着每在一个空位中填一个单词就可能有 100000 种选择。 搜索题一般来说都会有很强的剪枝性,但是本题没有,除了一些合法性的剪枝外,基本 上找不到任何可行的剪枝,哪怕是效果很弱的剪枝也没有。 先来看看最简单而且能够非常自然想到的搜索方法: 一个一个空位枚举, 对于题目给出 的每个空位在单词表中枚举一个暂时符合要求的单词填进去。 这个算法最坏情况的时间复杂 度是 O(100000n)的(n?20)。当然,10000020 的阶一般是达不到的,但是要达到 1000002 应 该不是很难办到的,而 1000002 已经足以让程序超时了。

让我们分析一下上面算法的瓶颈。 对于 O(100000n)的算法来说,降一点指数其实效果不是非常明显的,因为起码要把 n 降到 1.x 才能不超时,而且降指数也不是那么容易办到的。然而,如果能把 100000 这个底 数降低到很小,比方说一个小常数,效果应该就很好了。由于 n 不大,只有 20,如果底数 很小的话(设为 c) ,算法的时间复杂度就是 O(cn),再加上一些可行性的剪枝,程序的效率 应该是很高的。 现在的问题就是,如何来降这个 100000 的底数了。前面提到的最简单的搜索方法,每 枚举一个单词都要扫描一遍单词表, 这是极大的浪费, 因为单词表中绝大多数的单词都是非 法的(根据一般英语词典的情况来说)。实际上,我们扫描一遍单词表的目的是找出所有当 前合法的单词,而实现这一目的并非只能用扫描一遍单词表这种方法。 我们知道有一个概率常数级的查找方法——Hash 法。 当然,Hash 一般是用来查找单一元素的,而我们要查找的是所有的合法单词(每个合 法单词都是不同的) ,也就是查找多个元素。在这点上,Hash 是不适合作本题的查找数据结 构的。不过,稍微利用一下 Hash 的特殊性质,这个问题就解决了。Hash 需要设计 Hash 函 数,而 Hash 函数是有不可避免的冲突的,如果被查找元素发生冲突,则可能找到多个目标 元素,必须在多个目标元素中找出真正要查找的元素。我们正好可以抓住“冲突”这一点, 利用这个“冲突” ,设计一个比较特殊的 Hash 函数,让所有的合法单词的 Hash 函数值相同, 即让所有合法单词“冲突” 。这样,要找合法单词,只要计算一下任一合法单词对应的 Hash 函数值,然后在 Hash 表中把该值对应的所有冲突单词找出来即可。 现在我们就来设计这个 Hash 函数。其实这个函数说来也简单:首先确定一个搜索的顺 序(即先搜索哪个空位,后搜索哪个空位) ,然后就可以确定搜索每个空位时该空位中被确 定的字母的位置。 如图 7-4,共有两个空位可填单词,(0, 1)~(2, 1)和(1, 0)~(1, 2)。假设先填(0, 1)~(2, 1), 这时没有任何位置的字母被确定,所有长度为 3 的单词都是合法的单词。但是,填完第一个 单词以后, 对于空位(1, 0)~(1, 2)来说, 就有一个位置的字母已经被确定下来了, 它就是(1, 1) 位置上的字母。

图 7-4 ?? ??

图 7-5 如图 7-5,设一个长度为 L 的单词的第 i1、i2、?in 位上已经被确定下来,那么一种可 以选择的 Hash 函数是 这里,p 可以是任取的一个数(一般来说,p 取质数效果比较好) ,HASHLEN 是 Hash 表的长度(一般也是取质数效果较佳) 。 设计完了 Hash 函数以后,一切的做法就一目了然了:首先确定一个搜索的顺序,根据 每一步空位上确定的字母的位置,对每个单词按特定的 Hash 函数计算其 Hash 函数值,并

将其放入 Hash 表(建议用“吊桶法”处理冲突) ,这是一个初始化的过程。然后,按前面 定的顺序进行搜索(这个顺序最好是每次都选能确定字母数最多空位) ,根据确定的字母计 算出合法单词对应的 Hash 函数值,并从 Hash 表中取出所有合法单词(当然,也可能会取 出少量的非法单词,可以稍加判断将其去除) ,进行枚举。 算法的总体思想是利用 Hash 表来快速的查找合法单词,以达到可行性剪枝的目的。 最后,我们来简单分析一下算法的复杂性。由于使用了 Hash 表,复杂度是概率的,很 难估算。需要指出的是,待选的单词表是一个词典,词典一般是正态分布的,所以除了搜索 的第一层以外,以后的合法单词肯定都是很少的,再加上合法性剪枝的成分,实际上程序的 效率应该是很高的。但是,这个算法毕竟还是指数级的,虽然使用了 Hash 表基本上把所有 的无用功都去掉了(当然,还会有一些非法单词产生冲突,不过,当 Hash 表长度达到单词 数的两倍以上后,这样的冲突概率一般都很小,基本可以忽略) 。指数级的算法肯定不是一 个完美的算法,所以如果数据非常强的话,这个算法也是有可能超时的,只是这样的数据很 难出,至少现在还没能找出这样的数据来。

7.4 魔术数字游戏 源程序名 magic.???(pas, c, cpp) 可执行文件名 magic.exe 输入文件名 magic.in 输出文件名 magic.out 【问题描述】 填数字方格的游戏有很多种变化,如下图所示的 4×4 方格中,我们要选择从数字 1 到 16 来填满这十六个格子(Aij,其中 i=1..4,j=1..4)。为了让游戏更有挑战性,我们要求 下列六项中的每一项所指定的四个格子,其数字累加的和必须为 34: 四个角落上的数字,即 A11+A14+A41+A44=34。 每个角落上的 2×2 方格中的数字,例如左上角:A11+A12+A21+A22=34。 最中间的 2×2 方格中的数字,即 A22+A23+A32+A33=34。 每条水平线上四个格子中的数字,


更多相关文章:
全国青少年信息学奥林匹克联赛大纲
提供备选题题目若干,在 9 月 1 日之前提交科学委员会; 备选试题的保密期为 2 年,在该段时间内不得泄密或另作他用; 搜集本省信息学奥赛的有关信息并向...
信息学奥赛培训学习感受
信息学奥赛培训学习感受_高二数学_数学_高中教育_教育专区。信息学奥赛培训学习感受吴忠三中 何晓萍参加本次培训之前, 对信息学奥赛我仅是听说过而已, 对它的了解几...
信息学奥赛试题精选33题(附带题解)
信息学奥赛试题精选33题(附带题解)_学科竞赛_高中教育_教育专区。信息学奥赛试题精选33题(附带题解) 基础题:【1 Prime Frequency】 【问题描述】给出一个仅包含...
信息学奥赛C++
信息学奥赛C++_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档信息学奥赛C++_学科竞赛_高中教育_教育专区。目 录 青少年信息学奥林匹克竞赛情况...
青少年信息学奥林匹克联赛培训习题与解答
青少年信息学奥林匹克联赛培训习题与解答_IT/计算机_专业资料。全国青少年信息学奥林匹克联赛培训习题与解答(中学高级本) 电子版目录习 题篇 第一章 回溯法 1.1 ...
深入开展信息学奥赛之我见
深入开展信息学奥赛之我见安徽省蚌埠第九中学 张恩权 bbjzzeq@126.com 摘要:信息学奥林匹克竞赛是一项益智性的竞赛活动,核心是考查参赛选手的智力、 分析问题...
信息学奥赛历年试题(解答)
信息学奥赛——算法入门教... 35页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
凭什么我得了信息学奥赛国家一等奖
凭什么我得了信息学奥赛国家一等奖_教学反思/汇报_教学研究_教育专区。这人就是牛啊!凭啥!凭的是意志!凭的是信念!凭什么我得了信息学奥赛国家一等奖 山东省莱州...
信息学奥赛初赛复习题
中国信息学奥赛 B. 中国国家奥委会 C. 国际信息学奥赛D. 中国信息学联赛 [重要作业] 1、微机内的存储器的地址是以( )编址的。 A.二进制位 B.字长 C....
第十届全国青少年信息学奥林匹克联赛初赛试题及答案
2004 第十届全国青少年信息学奥林匹克联赛初赛试题及答案 第十届全国青少年信息学奥林匹克联赛初赛试题 (普及组 Pascal 语言 二小时完成) 一、选择一个正确答案代码...
更多相关标签:
信息奥赛    信息学奥赛一本通    信息学奥赛培训    信息学    小学信息学奥赛    信息学竞赛    信息学奥林匹克竞赛    信息学奥赛辅导    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图