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

'全国青少年信息学奥林匹克联赛培训习题与解答（中学高级本）目录习题篇与解析篇第一章回溯法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取余运算141 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.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.5魔板7.6三维扫描7.7拼字游戏7.8公路修建7.9单词游戏第八章动态规划8.1字串距离8.2血缘关系8.3尼克的任务8.4书的复制8.5多米诺骨8.6平板涂色141 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可见矩形141 第一章回溯法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.out66336【算法分析】从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。最后输出所有的路径数。这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。141 1.2出栈序列统计源程序名stack1.???（pas,c,cpp）可执行文件名stack1.exe输入文件名stack1.in输出文件名stack1.out【问题描述】栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两·种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。【输入】一个整数n（1<=n<=15）【输出】一个整数，即可能输出序列的总数目。【样例】stack1.instack1.out35【算法分析】先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。141 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”。如果两个操作数有大小的话则先输出大的。如果没有解则输出“Noanswer!”【样例】point24.inpoint24.out12372+1=37*3=2121+3=24【算法分析】计算24点主要应用四种运算．开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少(只有三层)，所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。141 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，然后是依赖函数号，接着是"isredundantusingFDs：”最后是说明的序列号。如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。如果这些函数依赖中不包含冗余依赖，则输出“NoredundantFDs”信息。【样例1】【样例2】redund.inredund.outredund.inredund.out3FD3isredundantusingFDs:126FD3isredundantusingFDs:1A->BD{即C可以通过1、2得到}P->RSTFD5isredundantusingFDs:462BD->CVRT->SQPA->CPS->TQ->TRQS->PSR->V【算法分析】一个依赖冗余，就是说它可以由其他依赖推导出来。如何判断一个依赖能否被其他依赖推导出来呢？假设判断的依赖为“a->b”，先找出所有形式为“a->*”的依赖，再由*开始找相关依赖，直到出现“#->b”为止(这里a、b、*、#都表示任意一个域名)。如何实现这种查找呢？可以通过筒单的回溯来完成。只是找出冗余(如果有的话)还不说明工作就已结束，要到找出所有的能够推导出b的依赖序列，选出其中长度最短的(最短的也可能并不惟一，因此本题答案有可能并不惟一)，最短的证明序列中一定不存在多余的依赖，如果不是最短的证明序列，那么该证明序列中就有可能还有冗余依赖。141 1.5走迷宫源程序名maze.???（pas,c,cpp）可执行文件名maze.exe输入文件名maze.in输出文件名maze.out【问题描述】有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。【输入】第一行是两个数m，n(1”表示方向。如果没有一条可行的路则输出-1。【样例】maze.in561001011111110011101111101110111156maze.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)，四个可能走的方向的点描述如下表：141 14x,y23对应的位置为：(x-1,y)，(x,y+1)，(x+1,y)，(x,y-1)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。这个查找过程用search来描述如下：proceduresearch(x,y,b,p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路}beginfori:＝1to4do{分别对4个点进行试探}begin先记住当前点的位置，已走过的情况和走过的路；如果第i个点(xl，y1)可以走，则走过去；如果已达终点，则输出所走的路径并置有路可走的信息，否则继续从新的点往下查找search(xl，y1，b1，p1)；end；end；【思考与提高】该程序通过引进新的变量和数组来继续新的查找，如果不引进新的变量和数组，那么每一次返回时要将原来的值还原才行，如果那样，程序应如何修改?其实那样更加符合回溯的思想——换条路再试。这类问题也可以归为搜索的问题，如果m和n的值相对比较大，则解可能很多，若题目只要找到一条路就结束程序时，在程序的输出部分后面加上一个halt就行了。有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。141 1.6单向双轨道源程序名track.???（pas,c,cpp）可执行文件名track.exe输入文件名track.in输出文件名track.out【问题描述】入口A出口DBC如图所示l，某火车站有B，C两个调度站，左边入口A处有n辆火车等待进站(从左到右以a、b、c、d编号)，右边是出口D，规定在这一段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度站不限定所能停放的车辆数。从文件输入n及n个小写字母的一个排列，该排列表示火车在出口D处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如“hLR”的字母序列，其中h为火车编号，L为h车原先所在位置(位置都以A、B、C、D表示)，R为新位置。或者输出‘NO’表示不能完成这样的调度。【输入】一个数n(130时速度就比较慢了。实际情况调头的次数并不会多的，到底在什么时候掉头根据情况而定。我们可以从最后一步来思考：141 最后一次关的可能是第一个灯也可能是最后一个灯，哪种情况所费的功小就选哪种；最后一次关的是第一个灯的话，说明最后的方向是从最后到最前(右边到左边)，最后倒数第二次的方向为从左到右，起点可能是原始起点(此时是第一趟)，也可能是原始起点左边的点(此时至少是第二趟)，一个个地试过去，先设拐一次弯，有可能拐的点都试过去，再试有两次拐弯换方向的情况，当再多的拐弯超过已有的解时就不要再向下试了。采用这种回溯方法，效率更高。如果n再大一些，如到300以上，上述方法也有它的局限性，此时最好从动态规划法或贪心法的角度去思考。141 第二章递规与递推2.1遍历问题源程序名travel.???（pas,c,cpp）可执行文件名travel.exe输入文件名travel.in输出文件名travel.out【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：aaaa//\bbbb//cccc所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。【输入】输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】trave1.intrave1.outabc4bca【算法分析】根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。设二叉树的结点总数为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)，先序遍历的结果是从第二个结点(字符)141 开始取，而后序遍历的结果里是从第1个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数：Functioncount(先序结果first，后序结果last:string):longint;beginLen:=遍历结果的长度；如果len为0或1，则返回结果即count:=l否则begint为当前统计后符合条件的数目，初值为0；分类统计fori:=len-1downto0dobegin在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;其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现：functioncheck(先序字符串F，后序字符串L)：boolean；beginCheck:=true;如果F的首字符不等于L的尾字符则check:=false;从F的第二个字符取到最后一个字符，如果该字符不在L中，则check:=false;end;【思考与提高】上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有可能解的个数，如果输入的两个字符串没有解，上述算法同样能得到结果。在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个结点时，如先序为ab、后序为ba，此时有可能有如下两种结构：aa/bb这两种结构的中序遍历结果分别为：ba、ab，有两种。根据分步相乘的原理，对比两个字符串，每出现一次如上的情况，可能有的结构数目(结构不同，中序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目)就乘以2一次，最终得到总的数目。这也可以理解为一种递推的方法。从这里可以看到，在肯定有解的情况下，给定先序遍历的结果和后序遍历的结果，可能有2n种可能的结构，也就是中序遍历可能得到2n种不同的结果，其中n>141 ＝0。那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。递推的程序如下：Programtravel(intput,output);VarTotal,I,m:longint;S1,s2:string;BeginAssign(input,’travel.in’);Assign(output,’travel.out’);Reset(input);rewrite(output);Readln(s1);readln(s2);total:=1;Fori:=1tolength(s1)-1doBeginM:=pos(s1[i],s2);Ifm>1thenifs[i+1]=s[m-1]thentotal:=total*2;End;Writeln(total);close(iinput);close(output);End.141 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.inbuild.out123621223【算法分析】如果本题用搜索，搜索的范围会很大(因为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，即：fork:=0to9dofori:=0to9doforj:=0to9dog[i,j]＝g[i,j]or(g[i,k]andg[k,j])；最后还要注意，当n很大时，解的个数很大，所以要用高精度运算。141 2.3出栈序列统计源程序名stack.???（pas,c,cpp）可执行文件名stack.exe输入文件名stack.in输出文件名stack.out【问题描述】栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。【输入】【输出】就一个数n(1≤n≤1000)。一个数，即可能输出序列的总数目。【样例】stack.instack.out35【算法分析】在第一章练习里，我们通过回溯的方法计算并输出不同的出栈序列，这里只要求输出不同的出栈序列总数目，所以我们希望能找出相应的递推公式进行处理。从排列组合的数学知识可以对此类问题加以解决。我们先对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)。又由上面的两种移动方法，我们可类似的得到两种状态转移方式：141 再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：边界值：f(0,0)=1。有了这个递归公式后，再写程序就比较简单了，请读者自己写出递归程序。141 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.incount.out111411111111【算法分析】本题可以用一个循环从1到n，将其拆为一位一位的数字，并加到相应的变量里，如拆下来是1，则count[1]增加1。这种方法最简单，但当n比较大时，程序运行的时间比较长。这种方法的基本程序段如下：fori:=1tondobeginj:=i;whilej>0dobegincount[jmod10]:=count[jmod10]+1;j:=jdiv10;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各个数字的使用次数)141 最高位(千位)为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次(＝nmod100)，因此count[3]增加657；接下来对百位6再进行类似的处理，0到9在个位和十位平均重复使用6*20次，所以count[0]～count[9]先各增加6*20，0到5作为百位重复使用了100次，所以count[0]～count[5]再各增加100，6作为百位在这里重复用了57次(＝nmod100)；因此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控制位数，fori:=lendownto1dobegin0到9的使用次数增加平均使用的次数b[i-1]*(i-1)*c[i]；0到c[i-1]的使用次数增加作为当前位使用的次数b[i-1]；c[i]的使用次数增加nmodb[i-1]end最后减去多计算的0的个数；输出结果。141 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.inempire.out224【样例说明】四种安置方案如图2-4所示。注意：镜面和旋转的情况属于不同的方案。【算法分析】重新描述一下问题，其实就是在一个边长为2n-1的正菱形(如上图2-2为n＝3的情形)上摆放k个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种?141 看到这道题目，我们就会立即想起一道经典的老题目：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时，问题无解。141 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＝5，可以证明当将h拆分为两个不相同的部分并且两部分都大于1时两部分的乘积大于h。证明如下：将h分为两部分：a，h-a其中2<＝a2*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-141 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；将上面拆分的各项依次跟数组各项相乘并考虑进位；141 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，区域的个数(0m)，费用需s分(s6时就不一定了。从这种最优策略出发，再结合回溯法找出所有可能的情况。141 第四章分治4.1取余运算源程序名mod.???（pas,c,cpp）可执行文件名mod.exe输入文件名mod.in输出文件名mod.out【问题描述】输入b，p，k的值，求bpmodk的值。其中b，p，k*k为长整型数。【样例】mod.inmod.out21092^10mod9=7【知识准备】进制转换的思想、二分法。【算法分析】本题主要的难点在于数据规模很大(b,p都是长整型数)，对于bp显然不能死算，那样的话时间复杂度和编程复杂度都很大。下面先介绍一个原理：a*bmodk＝(amodk)*(bmodk)modk。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢?显然对于任何一个自然数P，有p＝2*pdiv2+pmod2，如19＝2*19div2十19mod2＝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记录每一步求得的余数。141 4.2地毯填补问题源程序名blank.???（pas,c,cpp）可执行文件名blank.exe输入文件名blank.in输出文件名blank.out【问题描述】相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择(如图4-l)：（1）（2）（3）（4）并且每一方格只能用一层地毯，迷宫的大小为(2k)2的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1s。【输入】输入文件共2行。第一行：k，即给定被填补迷宫的大小为2k(01的宫殿，均可以将其化分为4个k/2大小的宫殿，先看一下公主站的位置是属于哪一块，因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界条件k＝1的情况，然后在公主边上铺上一块合适的地毯，递归结束。由于要递归到每一格，复杂度就是面积，就是O(22*k*k)。141 4.3平面上的最接近点对源程序名nearest.???（pas,c,cpp）可执行文件名nearest.exe输入文件名nearest.in输出文件名nearest.out【问题描述】给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。【输入】第一行：n；2≤n≤60000接下来n行：每行两个实数：xy，表示一个点的行坐标和列坐标，中间用一个空格隔开。【输出】仅一行，一个实数，表示最短距离，精确到小数点后面4位。【样例】nearest.innearest.out31.0000111222【参考程序】中位数、解析几何、时间复杂度、二分法【算法分析】如果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有pm}。容易看出，如果选取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-141 1个，由此产生的分治在最坏情况下所需的时间T(n)应满足递归方程：T(n)＝T(n-1)+O(n)它的解是T(n)＝O(n2)。这种效率降低的现象可以通过分治中“平衡子问题”的方法加以解决。也就是说，我们可以通过适当选择分割点m，使S1和S2中有大致相等个数的点。自然地，我们会想到用S的n个点的坐标的中位数来作分割点。这样一来，我们就能在O(n)的时间里确定m(证明略)，从而得到效率相对较高的分割点。至此，我们可以设计出一个求一维点集S中最接近点对的距离的算法：Functionnpair1(S);BeginIfS中只有2个点Thenδ:=|x[2]-x[1]|ElseifS中只有1个点Thenδ:=∞ElsebeginM:=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)＝1T(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中的点数大致相等。S1S2P2P1Lδδδ1δ2递归地在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所示：141 据直线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所示)。P1P2LpRδδδR图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个点。至此，我们得出用分治法求二维最接近点对距离的算法：Functionnpair(s);Begin141 IfS中只有2个点Thenδ:=S中这2点的距离ElseifS中只有1个点Thenδ:=∞Elsebegin（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)。141 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[]-->[]-->[]2、[]-->[]-->[]-->*3、---------->*-------->||||[]-->[]-->[]-->[]-->[]第1、第2种情况很好解决，第3种情况采用二分法：---------->*-------->||||||[Be]——>[]——>[Mid]——>[]——>[En]可以考虑*和mid的关系，if*-->midthenEn:=midelseBe:=mid；这样，最后必然会出现这样的情况：---->*---->||||[Be]-->[En]直接走上面的路径就可以了。总的提问次数为n*log2n。141 第五章图5.1医院设置源程序名hospital.???（pas,c,cpp）可执行文件名hospital.exe输入文件名hospital.in输出文件名hospital.out【问题描述】设有一棵二叉树，如图5-1：1/23/45其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为l。如上图中，若医院建在：【输入】第一行一个整数n，表示树的结点数。(n≤100)接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格(一个或多个)分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。【输出】一个整数，表示最小距离和。【样例】hospital.inhospital.out5811323400124520004000【知识准备】图的遍历和最短路径。【算法分析】本题的求解任务十分明了：求一个最小路径之和。根据题意，对n个结点，共有n个路径之和：用记号Si表示通向结点i的路径之和，则，其中Wj为结点j的居民数，g(i,j)为结点j到结点i的最短路径长度。下面表中反映的是样例的各项数据：jg(i,j)i12345Si1011220×13+1×4+1×12+2×20+2×40=1362102331×13+0×4+2×12+3×20+3×40=2173120111×13+2×4+0×12+1×20+1×40=814231022×13+3×4+1×12+0×20+2×40=130141 5231202×13+3×4+1×12+2×20+0×40=90141 从表中可知S3=81最小，医院应建在3号居民点，使得所有居民走的路径之和为最小。由此可知，本题的关键是求g[i,j]，即图中任意两点间的最短路径长度。求任意两点间的最短路径采用下面的弗洛伊德（Floyd）算法。（1）数据结构：w:array[1..100]oflonging;描述个居民点人口数g:array[1..100,1..100]oflongint初值为图的邻接矩阵，最终为最短路径长度（2）数据的读入：本题数据结构的原形为二叉树，数据提供为孩子标识法，分支长度为1，建立带权图的邻接矩阵，分下面两步：①g[i,j]←Max{Max为一较大数，表示结点i与j之间无直接相连边}②读入n个结点信息：fori:=1tondobeging[i,j]:=0;readln(w[i],l,r);ifl>0thenbeging[i,l]:=l;g[l,i]:=lend;ifr>0thenbeging[i,r]:=l;g[r,i]:=lend;（3）弗洛伊德算法求任意两点间的最短路径长度fork:=1tondofori:=1tondoifi<>kthenforj:=1tondoif(i<>j)and(k<>j)and(g[i,k]+g[k,j]b，则high[i]=high[j]+b(根据Ti≤Tj+b)，若low[i]-low[j]b)thenbeginhigh[i]:=high[j]+b;flag:=true;end;{调整Ti的上界}if(low[i]-low[j]>b)thenbeginlow[j]:=low[i]-b;flag:=true;end;{调整Tj的下界}if(low[i]>high[i])or(low[j]>high[j])thenbegin{无法满足当前不等式，则调整终止}noans:=true;{问题无解noans=true}flag:=false;break;end;end;end;141 下面以样例说明：【样例1】8个不等式如下序号12345678i11234455j25511334b0-1154-1-3-3顶点的关键值Ti的调整记录：初值第1轮调整第2轮调整第3轮调整high[1]0000low[1]0000high[2]10000010000022low[2]-10000222high[3]100000555low[3]-10000455high[4]100000444low[4]-10000444high[5]100000111low[5]-10000111调整状态有变化有变化无变化【样例2】5个不等式如下编号12345i11254j25511b-3-1-1-54顶点关键值Ti的调整记录：初值第一轮调整第二轮调整1high00low002high10000099999low-1000033high10000010000low-10000-100004high1000004low-10000-100005high100000-5low-100001调整情况high[5]T1T2-T5≤-1，→T5>T2T5-T1≤-5，→T1>T5这三个不等式不能同时成立，因此问题无解。141 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.inservers.out4392311143023203420注：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)的算法是很容易想到的：141 （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。用PriorityQueue（Heap,WinnerTree或FibonacciHeap等）来实现Dijkstra算法，时间复杂度为O((n+e)log2n)（用FibonacciHeap实现，更确切的时间复杂度是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的节点（集合）作为起点，求该节点（集合）到所有点的最短距离（其实也就是所有点到该节点（集合）的最短距离）；141 （2）以每个点作为起点，求该点到所有点的最短距离。当求得某节点的最短距离的同时根据求得的最短距离和该节点到rank大于起点的节点（集合）的最短距离，判断该节点是否对起点感兴趣。如果感兴趣，则找到一对感兴趣的点对，否则，停止扩展该节点，因为该节点不可能扩展出对起点感兴趣的节点。总结解题的过程，可以发现解决本题的关键有三点：一是稀疏图，正因为图中边比较稀疏所以我们可以用Dijkstra+PriorityQueue的方法将求最短路径的时间复杂度降为O(nlog2n)；二是rank的范围很小，rank的范围只有10，所以我们只用了10次Dijkstra算法就求得了所有点到特定rank的最短距离；三是感兴趣的点对只有很少，由于感兴趣的点对只有30n，我们通过只计算感兴趣点对的最短路径，将求点与点间最短路径的时间复杂度降到了O(nlog2n)。这三点，只要有一点没有抓住。本题就不可能得到解决。141 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.inage.out3YES2110110210021323【样例2】age.inage.out4NO231100420021234【算法分析】根据题中给出的间谍的相互控制关系，建立有向图。找出有向图中的所有强连通分量，用每个强连通分量中最便宜的点（需支付最少贿金的间谍）来代替这些强连通分量，将强连通分量收缩为单个节点。收缩强连通分量后的图中，入度为0的节点即代表需要贿赂的间谍。141 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.inguards.out3422000122221330102样例数据如图5-2（黑色方格为墙，白色方格为空地，圆圈为陷阱，G表示守卫）○○G○○G【算法分析】本题的关键在构图。城堡其实就是一个棋盘。我们把棋盘上横向和纵向连续的极长段（不含墙）都分离出来。显然，每一段上最多只能放一个guard，而且guard总是放在一个纵向段和一个横向段的交界处，所以一个guard和一个纵向段和一个横向段有关。我们把纵向段和横向段都抽象成图中的节点，如果一个纵向段和一个横向段相交的话，就在两点之间连一条边。这样，guard就成为了图中的边。前面得出的性质抽象成图的语言就是，每个点只能和一条边相连，每条边只能连接一个纵向边的点和一个横向边的点。因此，这样的图是二分图，我们所求的正是二分图的匹配。而要布置最多的guards，就是匹配数要最大，即最大匹配。图中节点数为n（n≤200），求最大匹配的时间复杂度为O(n2.5)。141 5.6K-联赛源程序名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.inkleague.out3123201102022202220【样例2】kleague.inkleague.out312402204011101110【样例3】kleague.inkleague.out424033113300002001001002000【算法分析】看一个队是否有希望夺冠，首先，这个队此后的比赛自然是赢越多越好，所以先让这个队把以后的比赛都赢下来，算出这个队最高能拿多少分。下面关键就看是否有可能让其他队的积分都低于刚才计算出的最高分。建立一个网络，所有的球队作为图中的节点，每两个队之间的比赛也作为图中的节点。从网络的源各连一条边到“比赛的节点”，容量为两队间还剩的比赛场数。从“每个队的节点”都连一条边到网络的汇，容量为这个队当前的积分与最高分之差。如果一个“比赛的节点”代表的是A与B之间的比赛，那么从这个节点连两条边分别到“A队的节点”和“B队的节点”，容量为无穷大。如果这个网络的最大流等于所有还未进行的比赛的场次之和，那么需要我们判断的那个队抗有可能夺得冠军。本题要我们找出所有可能夺冠的队，那么只需枚举所有的球队，判断它们是否有可能夺冠即可。141 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.inmachine.out55103011112213314421522623724833943【问题分析】本题所求的是工作模式的最少切换次数，实际上也就是求最少需要使用多少个工作模式，因为一个工作模式被切换两次肯定是不合算的，一旦切换到一个工作模式就应该把这个工作模式可以完成的工作都完成。将两台机器的工作模式分别看成n个和m个节点。jobi分别和机器A和B的mode_x和mode_y相关：jobi要被完成，就必须切换到机器A的mode_x或切换到机器B的mode_y。将jobi看作图中的一条边——连接节点x和节点y的边，那么这条边就要求x和y两个节点中至少要有一个节点被取出来。这正符合覆盖集的性质。我们构成的图是二分图，要求最少的切换次数，就是要使覆盖集最小。二分图的最小覆盖集问题等价于二分图的最大匹配问题。因此，只需对此二分图求一个最大匹配即是我们要求的答案。时间复杂度。141 5.8公路修建源程序名road.???（pas,c,cpp）可执行文件名road.exe输入文件名road.in输出文件名road.out【问题描述】某国有n个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。政府审批的规则如下：（1）如果两个或以上城市申请修建同一条公路，则让它们共同修建；ABC（2）如果三个或以上的城市申请修建的公路成环。如下图，A申请修建公路AB，B申请修建公路BC，C申请修建公路CA。则政府将否决其中最短的一条公路的修建申请；（3）其他情况的申请一律同意。一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相：连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。【输入】第一行一个整数n，表示城市的数量。(n≤5000)以下n行，每行两个整数x和y，表示一个城市的坐标。(-1000000≤x，y≤1000000)(0,4)(0,0)(-1,2)(1,2)【输出】一个实数，四舍五入保留两位小数，表示公路总长。(保证有惟一解)【样例】road.inroad.out修建的公路如图所示：46.470012-1204【问题分析】三条规则中的第二条是故弄玄虚。如果三个或三个以上的城市申请修建的公路成环，那么这些公路的长度必然都相同，否则不满足“每个城市选择一个与它最近的城市，申请修建通往该城市的公路”。所以，如果成环，其实是任意去掉一条路。本题要我们求的实际上是最小成成树，也就是说，按规则生成的是图的最小生成树。为什么呢？很显然，按规则生成的应该是树。根据规则：每个城市选择一个与它最近的城市，申请修建通往该城市的公路。那么，对于图中任意的环，环上最长边必被舍弃。这就与求最小生成树的“破环法”完全相符了。用Prim算法求图中的最小生成树，最小生成树上各边的长度只和即是所求的答案。时间复杂度为O(n2)。但是，本题还有其特殊性。本题是在Euclid空间求最小生成树，Euclid空间最小生成树有O(nlog2n)的算法，是用Voronoi图+Kruskal算法（或用Prim+heap代替Kruskal）实现的。141 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为A串中A1到Ai的一个扩展串，为B串中B1到Bj的一个扩展串。这两个扩展串形成最佳匹配的条件是（1）长度一样；（2）对应位置字符距离之和最小。首先分析扩展串与扩展串长度一样的构造方法。扩展串与扩展串可以从下列三种情况扩张成等长：（1）与为两个等长的扩展串，则在后加一空格，加字符Bj；（2）与为两个等长的扩展串，则在添加字符Ai，在后加一空格；（3）与为两个等长的扩展串，则在后添加字符Ai，在后添加字符Bj。其次，如何使扩展成等长的这两个扩展串为最佳匹配，即对应位置字符距离之和最小，其前提是上述三种扩展方法中，被扩展的三对等长的扩展串都应该是最佳匹配，以这三种扩展方法形成的等长扩展串(A1,A2,…,Ai>和也有三种不同情形，其中对应位置字符距离之和最小的是最佳匹配。为了能量化上述的构造过程，引入记号g[i,j]为字符串A的子串A1,A2,…,Ai与字符串B的子串B1,B2,…,Bj的距离，也就是扩展串与扩展串是一个最佳匹配。则有下列状态转移方程：g[i,j]=Min{g[i-1,j]+k,g[i,j-1]+k,g[i-1,j-1]+}0≤i≤La0≤j≤Lb其中，k位字符与字符之间的距离；为字符ai与字符bi的距离。初始值：g[0,0]=0g[0,j]=j·kg[i,0]=i·k综上所述，本题的主要算法如下：（1）数据结构vara,b:array[1..2000]ofbyte;{以ASCII码表示的字符串}g:array[0..2000,0..2000]oflongint;{各阶段的匹配距离}（2）读入字符串A、B，转换为ASCII码la:=0;lb:=0;whilenot(eoln(f))do{子串长度单元}begin{从文件中读入一行字符}read(f,c);inc(la);a[la]:=ord(c);end;readln(f);whilenot(eoln(f))dobeginread(f,c);inc(lb);b[lb]:=ord(c);end;readln(f);（3）根据状态转移方程求g[la,lb]g[0,0]:=0;fori:=1toladog[i,0]:=k+g[i-1,0];forj:=1tolbdog[0,j]:=k+g[0,j-1];fori:=1toladoforj:=1tolbdobeging[i,j]:=k+g[i-1,j];temp:=g[i,j-1]+k;ifg[i,j]>temptheng[i,j]:=temp;temp:=g[i-1,j-1]+abs(a[i]-b[j]);ifg[i,j]>temptheng[i,j]:=temp;end;（4）输出writeln(f,g[la,lb]);141 8.2血缘关系源程序名family.???（pas,c,cpp）可执行文件名family.exe输入文件名family.in输出文件名family.out【问题描述】我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之间相同基因的数量。妖怪之间的基因继承关系相当简单：如果妖怪C是妖怪A和B的孩子，则C的任意一个基因只能是继承A或B的基因，继承A或B的概率各占50％。所有基因可认为是相互独立的，每个基因的继承关系不受别的基因影响。现在，我们来定义两个妖怪X和Y的基因相似程度。例如，有一个家族，这个家族中有两个毫无关系(没有相同基因)的妖怪A和B，及它们的孩子C和D。那么C和D相似程度是多少呢？因为C和D的基因都来自A和B，从概率来说，各占50％。所以，依概率计算C和D平均有50％的相同基因，C和D的基因相似程度为50％。需要注意的是，如果A和B之间存在相同基因的话，C和D的基因相似程度就不再是50％了。你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相似程度。【输入】第一行两个整数n和k。n（2≤n≤300）表示家族中成员数，它们分别用1,2,…,n来表示。k（0≤k≤n-2）表示这个家族中有父母的妖怪数量（其他的妖怪没有父母，它们之间可以认为毫无关系，即没有任何相同基因）。接下来的k行，每行三个整数a,b,c，表示妖怪a是妖怪b的孩子。然后是一行一个整数m（1≤m≤n2），表示需要计算基因相似程度的妖怪对数。接下来的m行，每行两个整数，表示需要计算基因相似程度的两个妖怪。你可以认为这里给出的家谱总是合法的。具体来说就是，没有任何的妖怪会成为自己的祖先，并且你也不必担心会存在性别错乱问题。【输出】共m行。可k行表示第k对妖怪之间的基因相似程度。你必须按百分比输出，有多少精度就输出多少，但不允许出现多余的0（注意，0.001的情况应输出0.1%，而不是.1%）。具体格式参见样例。【样例】family.infamily.out740%41250%52381.25%645100%756412267533【知识准备】（1）基本的概率计算知识；141 （2）递推原理（包括记忆化搜索）。【算法分析】本题是一道概率计算题，但这个概率计算又是建立在FamilyTree模型上的。FamilyTree是一个有向无环图，有明显的阶段性(辈分关系)，而且没有后效性（没有人可以成为自己的祖先），符合动态规划模型的基本条件。因此，应该可以套用类似动态规划的方法来解决。我们先来明确一下相似程度的计算方法。假设我们要求的是A和B的相似程度（设为P(A,B)），那么有两种情况是显然的：（1）A=B:P(A,B)=1；（2）A与B无相同基因：P(A,B)=0。这是计算其他复杂情况的基础。因为动态规划就是从一些特定的状态（边界条件）出发，分阶段推出其他状态的值的。再来看一般的情况，设A0和A1是A的父母。那么，取概率平均情况，A拥有A0和A1的基因各占一半。假设A0与B的相似程度为P(A0,B)，A1与B的相似程度为P(A1,B)，那么P(A,B)与P(A0,B)和P(A1,B)之间应该是一个什么样的关系呢？很容易猜想到：P(A,B)=(P(A0,B)+P(A1,B))/2但是，这只是一个猜想。要让它变为一个结论还需要证明：我们用归纳法来证明。首先，我们知道，在这个问题中不同基因都是从特定的祖先传下来的，不会出现同一个基因采自不同的祖先的情况(注：这里的祖先是指那些没有父母的妖怪)。所以，如果A与B有相同的基因，这些基因必然来自同一个祖先。这里，我们最想说明的是，祖先那代是不存在两个人，它们之间不同的基因相同的概率不一样，因为它们相同的概率都是0。现在，A有祖先A0和A1，A0和A1与B的相似程度分别为P(A0,B)和P(A1,B)。从祖先一代开始归纳，可由归纳假设A0与B、A1与B之间每个基因相同的概率都是一样的，分别都是P(A0,B)和P(A1,B)。A的单个基因，它可能是继承A0的，也可能是继承A1的，概率各50%。继承A0的话与B相同的概率是P(A0,B)，继承A1的话与B相同的概率是P(A1,B)。那么这个基因与B相同的概率就是：(P(A0,B)+P(A1,B))/2因此，A的每个基因与B相同的概率都是(P(A0,B)+P(A1,B))/2，具有相同的概率。进而，A与B相同基因的数量概率平均也为(P(A0,B)+P(A1,B))/2，A与B的相似程度P(A,B)=(P(A0,B)+P(A1,B))/2这样就归纳证明了P(A,B)的概率递推公式。下面总结一下前面得出的结论：(1)边界条件：①A=B:P(A,B)＝1；②A与B无相同基因：P(A,B)=0；(2)递推关系：P(A,B)＝(P(A0,B)+P(A1,B))/2，其中A0和A1是A的父母有了边界条件和递推关系，以及FamilyTree的阶段性和无后效性作为前提，用动态规划解决问题的所有条件都已满足。应该说，从理论上来讲，本题已经完全解决。下面需要讨论的仅仅是实现方法而已。动态规划的实现方法有两种：一种是逆向的递推，另一种是正向的记忆化搜索（递归）。这两种方法都是可行的，区别仅仅在于，递推需要更多的考虑状态的阶段性，按照阶段计算出所有状态的值；而记忆化搜索只需要承认状态具有阶段性，无需考虑阶段，只需要按照递推式本身设计带记忆化的递归函数即可。本题给出的仅仅是一棵FamilyTree，并没有给出FamilyTree的阶段，如果要用递推的话，就必须先给FamilyTree分阶段（拓扑排序）。所以，本题显然更适合用记忆化搜索来实现。另外，需要注意的是，本题所求的答案是有多少精度就输出多少精度。300个节点的图，少说也可以构成几十层的FamilyTree，算出的结果至少也有小数点后几十位。所以，高精度是必不可少的（保险起见，可以设置300位的高精度）。分析一下本题的时间复杂度。动态规划的状态有n2个，转移代价为O(C)141 （高精度计算的代价）。因此，时间复杂度为为O(Cn2)，n≤300。严格的讲，本题的算法不能算动态规划的方法，因为本题不存在最优化，应该仅仅是一个递推。不过，从分析问题的过程来看，它里面包含了很多动态规划的思想，例如，阶段性和无后效性，特别是使用了动态规划的一种实现方法记忆化搜索。141 8.3尼克的任务源程序名lignja.???（pas,c,cpp）可执行文件名lignja.exe输入文件名lignja.in输出文件名lignja.out【问题描述】尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。尼克的一个工作日为N分钟，从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完戍，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去完成，假如某些任务开始时刻尼克正在工作，则这些任务也由尼克的同事完成。如果某任务于第P分钟开始，持续时间为T分钟，则该任务将在第P+T-1分钟结束。写一个程序计算尼克应该如何选取任务，才能获得最大的空暇时间。【输入】输入数据第一行含两个用空格隔开的整数N和K(1≤N≤10000，1≤K≤10000)，N表示尼克的工作时间，单位为分钟，K表示任务总数。接下来共有K行，每一行有两个用空格隔开的整数P和T，表示该任务从第P分钟开始，持续时间为T分钟，其中1≤P≤N，1≤P+T-1≤N。【输出】输出文件仅一行，包含一个整数，表示尼克可能获得的最大空暇时间。【样例】lignja.inlignja.out156412164118581115【算法分析】题目给定的数据规模十分巨大：1≤K≤10000。采用穷举方法显然是不合适的。根据求最大的空暇时间这一解题要求，先将K个任务放在一边，以分钟为阶段，设置minute[i]表示从第i分钟开始到最后一分钟所能获得的最大空暇时间，决定该值的因素主要是从第i分钟起到第n分钟选取哪几个任务，与i分钟以前开始的任务无关。由后往前逐一递推求各阶段的minute值：（1）初始值minute[n+1]=0（2）对于minute[i]，在任务表中若找不到从第i分钟开始做的任务，则minute[i]比minute[i+1]多出一分钟的空暇时间；若任务表中有一个或多个从第i分钟开始的任务，这时，如何选定其中的一个任务去做，使所获空暇时间最大，是求解的关键。下面我们举例说明。设任务表中第i分钟开始的任务有下列3个：任务K1P1=iT1=5任务K2P2=iT2=8任务K3P3=iT3=7而已经获得的后面的minute值如下：minute[i+5]=4，minute[i+8]=5，minute[i+7]=3若选任务K1141 ，则从第i分钟到第i+1分钟无空暇。这时从第i分钟开始能获得的空暇时间与第i+5分钟开始获得的空暇时间相同。因为从第i分钟到i+5-1分钟这时段中在做任务K1，无空暇。因此，minute[i]=minute[i+5]＝4。同样，若做任务K2，这时的minute[i]=minute[i+8]=5若做任务K3，这时的minute[i]=minute[1+7]=3显然选任务K2，所得的空暇时间最大。因此，有下面的状态转移方程：其中，Tj表示从第i分钟开始的任务所持续的时间。下面是题目所给样例的minute值的求解。任务编号K123456开始时间P1148811持续时间T2611515时刻I16151413121110987654321minute[i]0123401234561234选任务号k0000060040003002注：选任务号为该时刻开始做的任务之一，0表示无该时刻开始的任务。问题所求得最后结果为从第1分钟开始到最后时刻所获最大的空暇时间minute[1]。主要算法描述如下：（1）数据结构varp:array[1..10000]ofinteger;{任务开始时间}t:array[1..10000]ofinteger;{任务持续时间}minute:array[0..10001]ofinteger;{各阶段最大空暇时间}（2）数据读入①readln(n,k);{读入总的工作时间n及任务k}②读入k个任务信息fori:=1tokdoreadln(p[i],t[i]);{假设任务的开始时间按有小到大排列}（3）递推求minute[i]j:=k;{从最后一个任务选起}fori:=ndownto1dobeginminute[i]:=0;ifp[i]<>ithenminute[i]:=1+minute[i+1]{无任务可选}elsewhilep[j]=ido{有从i分钟开始的任务}beginifminute[i+t[j]]>minute[i]thenminute[i]:=minute[i+t[j]];{求最大空暇时间}j:=j-1;{下一个任务}end;end;（4）输出解writeln(minute[1]);141 8.4书的复制源程序名book.???（pas,c,cpp）可执行文件名book.exe输入文件名book.in输出文件名book.out【问题描述】现在要把m本有顺序的书分给k给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。【输入】第一行两个整数m，k；（k≤m≤500）第二行m个整数，第i个整数表示第i本书的页数。【输出】共k行，每行两个整数，第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。【样例】book.inbook.out93151234567896789【问题分析】本题可以用动态规划解决，但是动态规划并不是一个聪明的方法，这个后面会提到。不管怎样，我们还是先介绍动态规划的方法。设f(n,k)为前n本书交由k个人抄写，需要的最短时间，则状态转移方程为f(n,k)=min{max{f(i,k-1),},i=1,2,…,n-1}状态数为n·k，转移代价为O(n)，故时间复杂度为O(n2·k)。不难看出，上述方程满足四边形不等式，所以如果利用四边形不等式的性质，转移代价由平摊分析可得平均为O(1)。因此，时间复杂度可以降为O(n·k)。动态规划求出的仅仅是最优值，如果要输出具体方案，还需根据动态规划计算得到的最优值，做一个贪心设计。具体来说，设最优值为T，那么k个人，每个人抄写最多T页。按顺序将书分配给k人去抄写，从第一个人开始，如果他还能写，就给他；否则第一个人工作分配完毕，开始分配第二个人的工作；以后再是第三个、第四个、……直至第k个。一遍贪心结束后，具体的分配方案也就出来了。贪心部分的复杂度是O(n)的。从前面的分析可以看到，动态规划部分仅仅是求出了一个最优值，具体方案是通过贪心求得的。而动态规划这部分的时间复杂度却是相当之高，所以用动态规划来求最优值是很不合算的。可以看到，当每人抄写的页数T单调增加时，需要的人数单调减少，这就符合了二分法的基本要求。我们可以对T二分枚举，对每个枚举的T，用贪心法既求出需要的人数又求出具体的方案。所以，通过二分就能求得需要人数为k的最小的Tmin和相应的方案了。时间复杂度为O(nlog2c)，c为所有书本的页数和。从这道题目的解题过程中，我们可以看到动态规划也不是万金油，有时更一般的方法却可以得到更好的结果。141 8.5多米诺骨源程序名dom.???（pas,c,cpp）可执行文件名dom.exe输入文件名dom.in输出文件名dom.out【问题描述】多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的n个多米诺骨牌如图8-1所示。●●●●●●●●●●●●●●●●●●●●上方块中点数之和记为，下方块中点数之和记为，它们的差为。例如在图8-1中，=6+1+1+1=9，=1+5+3+2=11，=2。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。对于图8-1中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。【输入】输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。【输出】输出文件仅一行，包含一个整数。表示求得的最小旋转次数。【样例】dom.indom.out4161151312【问题分析】本问题可归约为经典的背包问题。假设一个骨牌的点数差的绝对值是s，那么它实际可以取到的点数差就是-s或s。我们不妨对取值进行一下平移，让每个骨牌可以取到的点数差为0和2s。这样，骨牌的“取正值还是负值”就转化为背包的“取与不取”了。那么，我们求解的目标会怎样变化呢？本来，我们的目标是让取值的总和为0。现在，我们对每个骨牌的取值作了平移，平移的距离为s。那么，最后的取值总和就应该是∑s，即所有骨牌的平移距离之和。141 8.6平板涂色源程序名paint.???（pas,c,cpp）可执行文件名paint.exe输入文件名paint.in输出文件名paint.out【问题描述】CE数码公司开发了一种名为自动涂色机（APM）的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。││↓y0123456──→x0123456Blue(A)Red(B)Red(D)Blue(E)Blue(C)Red(G)Blue(F)为了涂色，APM需要使用一组刷子。每个刷子涂一种不同的颜色C。APM拿起一把有颜色C的刷子，并给所有颜色为C且符合下面限制的矩形涂色：为了避免颜料渗漏使颜色混合，一个矩形只能在所有紧靠它上方的矩形涂色后，才能涂色。例如图中矩形F必须在C和D涂色后才能涂色。注意，每一个矩形必须立刻涂满，不能只涂一部分。写一个程序求一个使APM拿起刷子次数最少的涂色方案。注意，如果一把刷子被拿起超过一次，则每一次都必须记入总数中。【输入】文件paint.in第一行为矩形的个数N。下面有N行描述了N个矩形。每个矩形有5个整数描述，左上角的y坐标和x坐标，右下角的y坐标和x坐标，以及预定颜色。颜色号为1到20的整数。平板的左上角坐标总是(0,0)。坐标的范围是0..99。N小于16。【输出】输出至文件paint.out，文件中记录拿起刷子的最少次数。【样例】paint.inpaint.out7300221021622042112442143614064134662【问题分析】指数型动态规划。由于N小于16，故可以以一个N-bit的二进制数A作为状态，其中每个二进制位表示一个格子的涂色情况，二进制位0表示该格子未被涂色，二进制1表示该格子已被涂色。用F[A]表示要得到状态A，最少需要改变多少次颜色。对于每个状态A，通过枚举涂色方案来推新的状态。141 8.7三角形牧场源程序名pasture.???（pas,c,cpp）可执行文件名pasture.exe输入文件名pasture.in输出文件名pasture.out【问题描述】和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板，每块的长度Li(1≤Li≤40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。请帮助Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。【输入】第1行：一个整数N第2..N+1行：每行包含一个整数，即是木板长度。【输出】仅一个整数：最大牧场面积乘以100然后舍尾的结果。如果无法构建，输出-1。【样例】pasture.inpasture.out569211334【样例解释】692=舍尾后的（100×三角形面积），此三角形为等边三角形，边长为4。【问题分析】二维的背包问题。将所有的木板当作背包，木板的长度作为背包的重量。与普通背包问题不同的是，这里有两个背包。所以，我们要求的不是重量w是否能得到，而是一个重量二元组(w0,w1)是否能得到。求解的方法与普通背包问题基本相同，只不过状态是二维的。求得所有可以得到的二元组后，枚举所有的二元组。对于任意的(w0,w1)，w0,w1，w—w0—w1(w表示所有背包的总重量)即是对应的三角形三边之长(可能是非法三角形)。这些三角形中面积最大者就是我们所求的答案。141 8.8分组源程序名teams.???（pas,c,cpp）可执行文件名teams.exe输入文件名teams.in输出文件名teams.out【问题描述】你的任务是把一些人分成两组，使得：·每个人都被分到其中一组；·每个组都至少有一个人；·一组中的每个人都认识其他同组成员；·两组的成员人数近两接近。这个问题可能有多个解决方案，你只要输出任意一个即可，或者输出这样的分组法不存在。【输入】为了简单起见，所有的人都用一个整数标记，每个人号码不同，从1到N。输入文件的第一行包括一个整数N（2≤N≤100），N就是需要分组的总人数；接下来的N行对应了这N个人，按每个人号码的升序排列，每一行给出了一串号码Aij（1≤Aij≤N，Aij≠i），代表了第i个人所认识的人的号码，号码之间用空格隔开，并以一个“0”结束。【输出】如果分组方法不存在，就输出信息“Nosolution”（输出时无需加引号）至输出文件；否则用两行输出分组方案；第一行先输出第一组的人数，然后给出第一组成员的号码，每个号码前有一个空格，同理给出第二组的信息。每组的成员号码顺序和组别顺序并不重要。【样例】teams.inteams.out531352350224145301250123043210【问题分析】首先，确定这样的一组集合(Ai,Bi)，集合Ai中的人必须和集合Bi的人分在不同组。这些集合可通过人与人之间认识与不认识的关系得到。得到这些集合对后，问题就转化为一个背包问题了——即如何分配这些二元组，使得两边人数差尽量小。这个背包问题可以通过“平移”的方法转化为普通的背包问题。141 第九章数学问题9.1多项式展开系数源程序名equal.???（pas,c,cpp）可执行文件名equal.exe输入文件名equal.in输出文件名equal.out【问题描述】二项式展开系数大家已经十分熟悉了：现在我们将问题推广到任意t个实数的和的n次方(x1+x2+…+xt)n的展开式。我们想知道多项式(x1+x2+…+xt)n中的任意一项的系数。例如，将一个三项式(x1+x2+x3)3展开后，可以得到：(x1+x2+x3)3=+++++++++其中，的系数为3【输入】第一行，两个整数n和t，中间用空格分隔。分别表示多项式幂和项数。第二行，t个整数n1,n2,…，nt，中间用空格分隔。分别表示x1,x2,…,xn的幂。（n1+n2+…+nt=n，1≤n,t≤12）【输出】仅一行，一个整数（保证在长整型范围内）。表示多项式(x1+x2+…+xt)n中的项的系数。【样例】equal.inequal.out333210【知识准备】组合数运算；二项式展开；代数式的恒等变形。【算法分析】（1）利用二项式展开公式推广到多项式的展开：其中含有的一项即为上式右边展开后的一项：141 整理得到：①所以要想求(x1+x2+…+xt)n的任意一项的系数只要将①式中令x1=x2=…=xt=1，得到（2）因为……所以（3）由分析（1）、（2）求的系数化为求上述的除法运算：①先计算n!；②将n!逐一去除n1,n2,…,nt；③最后的商为所求结果。由于题目所给n≤12，计算n!可在长整型范围内，无需采用高精度运算。设数组no:array[1..t]为nt；total为n!。主要算法描述如下total:=1;fori:=1tondototal:=total+i;{求n!}fori:=1totdoforj:=1tono[i]dototal:=totaldivj;{整除n!}141 9.2两数之和源程序名pair.???（pas,c,cpp）可执行文件名pair.exe输入文件名pair.in输出文件名pair.out【问题描述】我们知道从n个非负整数中任取两个相加共有n*(n-1)/2个和，现在已知这n*(n-1)/2个和值，要求n个非负整数。【输入】输入文件仅有一行，包含n*(n-1)/2+1个空格隔开的非负整数，其中第一个数表示n(21,r≥1）证明：设n个不同的球为b1,b2,…,bn，从中取一个球设为b1。把这n个球放入r个盒子无一空盒的方案全体可分为两类：（1）b1独占一盒，其余n-1个球放入r-1个盒子无一空盒的方案数为S(n-1，r-1)（2）b1不独占一盒，这相当于先将b2,b3,…,bn。这n-1个球放入r个盒子，不允许有空盒的方案数共有S(n-1,r)，然后将b1放入其中一盒，这一盒子有r种可挑选，故b1不独占一盒的方案数为r·S(n-1,r)。根据加法原理，则有：S(n,r)＝r·S(n-1,r)+S(n-1,r-1)(n>1，r≥1)对于n＝r，或r＝1，显然有S(n,n)＝1，S(n,1)＝1。综上所述，本题的算法可用第二类Stirling数的递推关系先求出S(n,r)，再乘上r!，即得所求方案数。主要算法描述如下：（1）数据结构constmaxn=10{球的最大数目}vars:array[0..maxn,0..maxn]oflongint;{存放第二类数}（2）用下列二重循环求S(n,r)①置S[0,0]=1;②fori:=1tondoforj:=1tordoS(i,j)=i*S(i-1,j)+S(i-1,j-1)③计算方案数SS:=S[n,r]Fori:=1tordoS:=S*I;141 9.4取数游戏源程序名cycle.???（pas,c,cpp）可执行文件名cycle.exe输入文件名cycle.in输出文件名cycle.out【问题描述】有一个取数的游戏。初始时，给出一个环，环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后，将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏，两人轮流取数，取数的规则如下：（1）选择硬币左边或者右边的一条边，并且边上的数非0；（2）将这条边上的数减至任意一个非负整数(至少要有所减小)；（3）将硬币移至边的另一端。如果轮到一个玩家走，这时硬币左右两边的边上的数值都是0，那么这个玩家就输了。如下图，描述的是Alice和Bob两人的对弈过程，其中黑色节点表示硬币所在节点。结果图(d)中，轮到Bob走时，硬币两边的边上都是0，所以Alcie获胜。（a）Alice（b）Bob（c）Alice（d）Bob现在，你的任务就是根据给出的环、边上的数值以及起点（硬币所在位置），判断先走方是否有必胜的策略。【输入】第一行一个整数N（N≤20），表示环上的节点数。第二行N个数，数值不超过30，依次表示N条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。【输出】仅一行。若存在必胜策略，则输出“YES”，否则输出“NO”。【样例】cycle.incycle.out4YES2530cycle.incycle.out3NO000【问题分析】本题的数据规模(N≤20，边上的数值不超过30)实际上是一个幌子，是想误导我们走向搜索的道路。考虑一个简化的问题。如果硬币的一边的数值为0，那么惟一可能取胜的走法就是向另一边移动，并且把边上的数减到0。因为如果不把边上的数减到0，那么下一步对方会将硬币移动到原来的位置，并且将边上的数减到0，这样硬币两边的数值就都为0了。所以，对于一边有0的情况，双方惟一的走法就是不停的向另一边移动，并取完边上的数值。因此，判断是否有必胜策略，就是看另一个方向上连续的非零边是否为奇数条。141 那么两边都非零的情况呢?如果有一个方向上连续的非零边为奇数条，那么显然是有必胜策略的，因为只需往这个方向走并取完边上的数即可。如果两个方向上连续的非零边都是偶数条，则没有必胜策略。因为不管往哪个方向走，必然不能取完边上的数，否则必败。如果不取完，则下一步对方可以将硬币移动回原来的位置并取完边上的数，这样就变成了一边为0、另一边有偶数条连续的非零边的情况，还是必败。所以，对于一般的情况，只需判断硬币的两边是否至少有一边存在奇数条连续的非零边。如果存在，则有必胜策略；否则无必胜策略。算法的时间复杂度为O(N)。141 9.5磁盘碎片整理源程序名defrag.???（pas,c,cpp）可执行文件名defrag.exe输入文件名defrag.in输出文件名defrag.out【问题描述】出于最高安全性考虑，司令部采用了特殊的安全操作系统，该系统采用一个特殊的文件系统。在这个文件系统中所有磁盘空间都被分成了相同尺寸的N块，用整数1到N标识。每个文件占用磁盘上任意区域的一块或多块存储区，未被文件占用的存储块被认为是可是用的。如果文件存储在磁盘上自然连续的存储块中，则能被以最快的速度读出。因为磁盘是匀速转动的，所以存取上面不同的存储块需要的时间也不同。读取磁盘开头处的存储块比读取磁盘尾处的存储块快。根据以上现象，我们事先将文件按其存取频率的大小用整数1到K标识。按文件在磁盘上的最佳存储方法，1号文件将占用1,2,…,S1的存储块，2号文件将占用S1+1,S1+2,…，S1+S2的存储块，以此类推（Si是被第i个文件占用的存储块的个数）。为了将文件以最佳形式存储在磁盘上，需要执行存储块移动操作。一个存储块移动操作包括从磁盘上读取一个被占用的存储块至内存并将它写入其他空的存储块，然后宣称前一个存储块被释放，后一个存储块被占用。本程序的目的是通过执行最少次数的存储块移动操作，将文件安最佳方式存储到磁盘上，注意同一个文件的存储块在移动之后其相对次序不可改变。【输入】每个磁盘说明的第一行包含两个用空格隔开的整数N和K(1≤K≤N≤100000)，接下来的K行每行说明一个文件，对第i个文件的说明是这样的：首先以整数Si开头，表示第i个文件的存储块数量，1<=Si<=N-K，然后跟Si个整数，每个整数之间用空格隔开，表示该文件按自然顺序在磁盘上占用的存储块的标识。所有这些数都介于1和N之间，包括1和N。一个磁盘说明中所有存储块的标识都是不同的，并且该盘至少有一个空的存储块。【输出】对于每一个磁盘说明，只需输出一行句子“WeneedMmoveoperations”，M表示将文件按最佳方式存储到磁盘上所需进行的最少存储块移动操作次数。如果文件已按最佳方式存储，仅需输出“Nooptimizationneeded.”。【样例】defrag.indefrag.out203Weneed9moveoperations423111217318510【问题分析】本题可以看作是一个置换的调整问题。按文件块的目标位置对文件块编号后，调整文件块位置的问题就转化为调整置换的问题了。不过，本题还有一点特殊之处，就是存在一些数，它们不要求归位，这些数可作为交换空间。找出所有的循环节，分情况讨论。如果一个循环节上所有的数都是要求归位的，那么必须先利用交换空间将一个数先交换出去，然后其他数都归位，最后再把交换出去的数换回来。如果这个循环节上有不需要归位的数，则可直接贪心，将可以归位的尽量归位即可。141 9.6欧几里德的游戏源程序名game.???（pas,c,cpp）可执行文件名game.exe输入文件名game.in输出文件名game.out【问题描述】欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。然后是Ollie，对刚才得到的数，和M，N中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。下面是他们用(25，7)两个数游戏的过程：Start：257Stan：117Ollie：47Stan：43Ollie：13Stan：10Stan赢得了游戏的胜利。现在，假设他们完美地操作，谁会取得胜利呢？【输入】第一行为测试数据的组数C。下面有C行，每行为一组数据，包含两个正整数M,N。（M,N不超过长整型。）【输出】对每组输入数据输出一行，如果Stan胜利，则输出“Stanwins”；否则输出“Olliewins”【样例】game.ingame.out2Stanwins257Olliewins2415【问题分析】这是一道博弈题。解题的关键在于把握胜负状态的关系。任意的状态只有两种可能：一种可能是胜状态——即有必胜策略，另一种可能是负状态——即没有必胜策略。对于任意的胜状态，无论如何走，都不可能走到另一个胜状态；而任意的负状态，至少存在一种走法可以走到胜状态。(0,0)是初始的胜状态。考察任意的状态(a,b)，不妨假设a≥b。如果<2，则只有一种走法，即将(a,b)变为(a-b,b)。那么，(a,b)是何种状态就取决于(a-b,b)是何种状态：根据前面胜负状态的定义可知，(a-b,b)为胜状态时，(a,b)为负状态；(a-b,b)为负状态时，(a,b)为胜状态。如果≥2，则至少存在两种走法：将(a,b)变为(c,b)或(c+b,b)，这里c＝amodb。如果这两个状态中至少有一个是负状态，则根据定义(a,b)是胜状态。如果两个状态都是胜状态，由于(c+b,b)可以变为(c,b)，这就与“胜状态只能走到负状态”产生了矛盾，所以两个状态都是胜状态的情况是不存在的。因此，≥2时，(a,b)必为胜状态。总结一下前面的结论，设f(a,b)为状态(a,b)的胜负情况(1表示胜状态，0表示负状态)，a≥b，则：1、2、141 9.7百事世界杯之旅源程序名pepsl.???（pas,c,cpp）可执行文件名pepsl.exe输入文件名pepsl.in输出文件名pepsl.out【问题描述】“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。还不赶快行动！”你关上电视，心想：假设有n个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？【输入】整数n（2≤n≤33），表示不同球星名字的个数。【输出】输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为：35--20第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。减号的个数应等于分母的为数。分子和分母的首位都与第一个减号对齐。分数必须是不可约的。【样例】pepsi.inpepsi.out23【提示】“平均”的定义：如果在任意多次随机实验中，需要购买k1,k2,k3,…瓶饮料才能凑齐，而k1,k2,k3,…出现的频率分别是p1,p2,p3,…，那么，平均需要购买的饮料瓶数应为：k1*p1+k2*p2+k3*p3+…【算法分析】这道题目主要考察的是数学的推导能力。假设f[n,k]为一共有n个球星，现在还剩k个未收集到，还需购买饮料的平均次数。则有：经移项整理，可得：我们所要求的实际上应该是f(n,n)，根据f(n,k)的递推式，可得其中，H(n)表示HarmonicNumber。141 9.8倒酒源程序名pour.???（pas,c,cpp）可执行文件名pour.exe输入文件名pour.in输出文件名pour.out【问题描述】Winy是一家酒吧的老板，他的酒吧提供两种体积的啤酒，aml和bml，分别使用容积为aml和bml的酒杯来装载。酒吧的生意并不好。Winy发现酒鬼们都非常穷。有时，他们会因为负担不起aml或者bml啤酒的消费，而不得不离去。因此，Winy决定出售第三种体积的啤酒(较小体积的啤酒)。Winy只有两种杯子，容积分别为aml和bml，而且啤酒杯是没有刻度的。他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。为了简化倒酒的步骤，Winy规定：（1）a≥b；（2）酒桶容积无限大，酒桶中酒的体积也是无限大(但远小于桶的容积)；（3）只包含三种可能的倒酒操作：①将酒桶中的酒倒入容积为bml的酒杯中；②将容积为aml的酒杯中的酒倒入酒桶；③将容积为bml的酒杯中的酒倒入容积为aml的酒杯中。（4）每次倒酒必须把杯子倒满或把被倾倒的杯子倒空。Winy希望通过若干次倾倒得到容积为aml酒杯中剩下的酒的体积尽可能小，他请求你帮助他设计倾倒的方案【输入】两个整数a和b（0B杯；2、B杯->A杯；3、桶->B杯；4、B杯->A杯；5、A杯->桶;6、B杯->A杯；【问题分析】解模方程。首先，c＝gcd(a,b)。写成模方程形式即为bx≡c(moda)。设Pa，Pb分别为从体积为aml。的酒杯中倒出酒的次数和将酒倒入体积为bmL的酒杯中的次数，则有c＝bPb-aPa。用Euclid辗转相除法求出Pa，Pb即可。时间复杂度为O(log2n)。141 9.9班级聚会源程序名reunion.???（pas,c,cpp）可执行文件名reunion.exe输入文件名reunion.in输出文件名reunion.out【问题描述】毕业25年以后，我们的主人公开始准备同学聚会。打了无数电话后他终于搞到了所有同学的地址。他们有些人仍在本城市，但大多数人分散在其他的城市。不过，他发现一个巧合，所有地址都恰好分散在一条铁路线上。他准备出发邀请但无法决定应该在哪个地方举行宴会。最后他决定选择一个地点，使大家旅行的花费和最小。不幸的是，我们的主人公既不擅长数学，也不擅长计算机。他请你帮忙写一个程序，根据他同学的地址，选择聚会的最佳地点。【输入】输入文件的每一行描述了一个城市的信息。首先是城市里同学的个数，紧跟着是这个城市到Moscow（起点站）的距离（km），最后是城市的名称。最后一行描述的总是Moscow，它在铁路线的一端，距离为0。【输出】聚会地点城市名称和旅行费用（单程），两者之间用一空格隔开。每km花费一个卢布。【样例】reunion.inreunion.out79289VladivostokYalutorovsk11212558523Chabarovsk35184Irkutsk82213Yalutorovsk100Moscow【问题分析】中位数问题。找这样一个点(城市)——它左边的人数与右边的人数差的绝对值最小。时间复杂度为O(n)。本问题的参考程序作者特意不加注释，以考察读者能否根据以上问题分析，将程序看懂并理解。141 第十章杂题10.1排序源程序名sillysort.???（pas,c,cpp）可执行文件名sillysort.exe输入文件名sillysort.in输出文件名sillysort.out【问题描述】有一列数，要对其进行排序(升序)。排序只能通过交换来实现。每次交换，可以选择这列数中的任意两个，交换他们的位置，并且交换的代价为这两个数的和。排序的总代价是排序过程中所有交换代价之和。现要求计算，对于任意给出的一列数，要将其排成升序所需的最小代价。【输入】输入包含多组数据。每组数据有两行组成。第一行一个数n，表示这列数共有n个数组成。第二行n个互不相同的整数(都是小于1000的正整数)，表示这列数。输入文件以n＝0结尾。【输出】对于每组输入数据，输出组号和排序所需的最小代价。【样例】sillysort.insillysort.out3Case1：4321Case2：174Case3：418124Case4：3451897668453270【知识准备】置换及其循环节的基本知识。【算法分析】本题要求我们对给定的序列按某种方法排序，使得交换的总代价最小。既然要求交换代价尽可能小，那么我们就应该尽量遵循两条原则：（1）尽量少交换(能不交换的不要交换)；（2）尽量选较小的数交换(减少交换的代价)。当然，这两条原则本身是有冲突的，不过我们不妨先按这两条原则分别来分析一下。任意一个序列，都可以在n次交换以内完成排序工作。因为题目保证n个数互不相同，所以不妨假设n个数分别为1，2，3，…，n，相当于作一个保序的映射。这样的序列可以看作一个置换。要将置换排序，只需对它的每一个循环节排序。而一个长度为L的循环节，可以通过L-1次交换完成排序，例如，循环节（134）可以通过1和4交换，然后1和3交换完成排序，交换次数为2。所以，总交换次数小于n。这里，我们可以看到，分离并处理每个循环节，可以大大减少排序过程中的交换次数。事实上，不难证明，这样的排序方法是可以保证最少的交换次数的。由于要使交换的代价尽可能小，所以交换时，选择哪些数去交换也是有讲究的。还是拿（134）这个循环节为例，有很多方法可以只用2次交换将它排序，例如：（1）1和3交换，然后1和4交换；（2）3和4交换，然后1和3交换。141 这两种方法的代价分别为9和11，显然第一种更好一些。我们看到，可以通过循环节中的某个元素和其他元素的依次交换来完成循环节的排序。第一种方法即是用1与3，4依次交换，而第二种方法则是用3与4，1交换，当然我们还可以用4依次与1，3交换。这其中代价最小的自然是用循环节中的最小元素依次与其他元素交换的方法，因为被用来和其他元素交换的元素需要多次计入交换代价，而其他元素只计一次。所以，如果要选择一个元素来调整其他元素的话，必然是选最小的一个。同时，我们还可以证明，单就循环节内部的调整而言，这样的方法已经是最优的了。因为循环节中每个元素都不在目标位置，必须被交换至少一次。由于循环节的特殊结构，至少要交换L-1次才能完成排序(L为循环节长度)。所以，就“循环节内部调整”而言，L-1次交换分别是最小元素与其他元素一次交换是一种最优的调整方案。那么，我们是否就应该对每个循环节用循环节中的最小元素去调整呢?答案是不一定，要看具体的情况。因为在本题中循环节的调整并没有局限在循环节内部，也就是说我们还可以通过循环节与循环节之间的交换来得到更优的调整方案。当然，循环节之间的交换应该是非经常性的，而且只局限于某几个元素之间。这几个元素是1和每个循环节的最小元素(把循环节中较大的元素换出去没有意义)。另需注意的，这里的“1”表示的是整个序列中的最小元素(保序映射后，置换中的1)，并非真实意义下的1。为什么要拿1和循环节中最小元素(如果1不是这个)交换呢?自然是想用1代替这个最小元素来和其他元素交换以减小交换的总代价。设最小元素为c，那么只要2*(c+“1”)<(L-“l”)*(c-“1”)，这样的交换就是合算的。所以，调整循环节的方法有两种：（1）拿最小元素依次和其他元素交换，使循环节中所有元素都被交换到目标位置；（2）先将最小元素与1交换，让1代替最小元素与其他元素交换，最后用1将最小元素交换回来。这两种方法究竟用哪种，就看哪种的代价更小一些。至此，总的调整策略已经设计完毕。现在就来总结一下：（1）找出所有循环节；（2）对每个循环节，有两种调整策略：(1)用最小元素调整；(2)用最小元素与元素1交换，然后用元素1来调整，最后用1将最小元素交换回来。两种策略取哪种就看哪种策略代价更小一些了。141 10.2木棍加工源程序名stick.???（pas,c,cpp）可执行文件名stick.exe输入文件名stick.in输出文件名stick.out【问题描述】一堆木头棍子共有n根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：第一根棍子的准备时间为1分钟；如果刚处理完长度为L，宽度为W的棍子，那么如果下一个棍子长度为Li，宽度为Wi，并且满足L>＝Li，W>＝Wi，这个棍子就不需要准备时间，否则需要1分钟的准备时间；计算处理完n根棍子所需要的最短准备时间。比如，你有5根棍子，长度和宽度分别为(4,9)，(5,2)，(2,1)，(3,5)，(1,4)，最短准备时间为2（按(4,9)、(3,5)、(1,4)、(5,2)、(2,1)的次序进行加工）。【输入】第一行是一个整数n(n<＝5000)，第2行是2n个整数，分别是L1，W1，L2，w2，…，Ln，Wn。L和W的值均不超过10000，相邻两数之间用空格分开。【输出】仅一行，一个整数，所需要的最短准备时间。【样例】stick.instick.out524952213514【知识准备】基本动态规划原理。【算法分析】本题的任务，概括来说是：对于给定的一些二元组(x1,y1)，(x2,y2)，(x3,y3)，…，(xn,yn)，确定一些序列的分割：……这里，要求对于任意的i,j,p（p>1），满足xijp-1≤xijp且yijp-1≤yijp，并且使得k尽可能小（即最小分割）。这其实就是著名的不下降序列的最小分割问题。一个著名的定理是这样的：最长上升序列的长度等于不上升序列的最小分划（即将平面上的点分划成尽可能少的不相交的不上升序列）。下面我们就来给出这个定理的证明，在证明的过程中，我们甚至可以得到求具体分割方案的方法。证明：一个显然的结论是最长上升序列的长度小于等于不上升序列的最小分划。因为上升序列中任意两点都不可能属于同一个不上升序列。也就是说，最长上升序列中的所有点分属不同的不上升序列。所以，不上升序列的分划数最少也不会少于最长上升序列的长度。141 关键的是要证明，最长上升序列的长度大于等于不上升序列的最小分划。我们来构造一个不上升序列的分划。首先在二维Euclid空间中取出所有的满足如下性质的点(x,y)：对于任意的点(x",y")，总满足x"≤x||y"≤y，即(x，y)的“右上方”没有别的点。可以证明，取出的点集{(x，y)}是一条不上升序列。因为点集中任意两点(x1,y1)和(x2,y2)总满足x1≤x2||y1≤y2且x2≤x1||y2≤y1，整理一下即得(x1≤x2)xor(y1≤y2)＝true。所以，把这些点按x升序排列后，得到的y相应的成降序。将上面取出的点从空间中去除后，重复上述过程，又可以得到一条新的不上升序列。如此反复……可以得到一个不上升序列的分划(现在还不能肯定这就是最小的分划)。由前面的结论知道，这个分划数必定大于等于最长上升序列的长度。我们对得到的不上升序列分划进行分级，先取出的等级最高，最后取出的等级最低。这样就得到k条分属level1，level2，…，levelk的不上升序列。这些链上的点满足这样的性质：对于一个属于leveli(ix1&&y2>y1，然后取level3的点（x3,y3）……最后必然能取到levelk上的点（xk,yk）。如此得到的序列（x1,y1），（x2,y2），…，（xk,yk），就是一条上升序列。所以，我们前面得到的不上升序列的分划数就不可能大于最长上升序列长度。这就证明了最长上升序列的长度大于等于不上升序列的最小分划。再加上“最长上升序列的长度小于等于不上升序列的最小分划”的结论，就证明了最长上升序列的长度等于不上升序列的最小分划。这个证明的优点在于，它是一个构造性的证明，并且揭示了最长上升序列与不上升序列最小分划之间的较为深刻的关系。根据前面的证明，我们可以很容易得到两种解决本题的方法：（1）在给出的二元组中求出最长下降序列的长度（具体实现比较简单，这里就从略了）；（2）用类似Topologic排序的方法，构造性的求出不下降序列的最小分割(详细过程见证明)。这两种方法的时间复杂度都是O(n2)的。实际上，本题还能优化到O(nlog2n)级，考虑到题目的规模以及本文的侧重点，这里就不详细展开了。此外，前面讲的方法（2），也是求最长双链问题的一个基础。141 10.3三角形源程序名tr.???（pas,c,cpp）可执行文件名tr.exe输入文件名tr.in输出文件名tr.out【问题描述】给出平面上的n个等腰直角三角形。每个三角形用3个整数描述x,y,m（m>0）。一个三角形的3个顶点分别是(x,y)，(x+m,y)and(x,y+m)。你的任务是计算这些三角形覆盖的总面积。【输入】输入文件tr.in第一行是整数n（n≤2000）。接下来n行每行描述一个三角形，包括3个整数xi，yi，mi(1≤i≤n，-107≤xi≤107，-107≤yi≤107，00)，R的整数部分为一个阿拉伯数字，小数部分最多有十位。【输出】输出文件仅一行，若解唯一则输出“分子/分母”（整数K写成K/1），否则输出“TOOMANY”。【样例】close.inclose.out360120355/1133.1415926536【问题分析】设分数为，枚举b，令a1=[b*R]，a2=[b*R]+1。取所有的、中的最优解。141 10.7切孔机源程序名cutter.???（pas,c,cpp）可执行文件名cutter.exe输入文件名cutter.in输出文件名cutter.out【问题描述】司令部的助理经常需要在大纸上切割各种形状的孔。他们刚刚购买了一台新的切孔机，该机比他们以前使用的要方便自由的多。他们想编写一个程序来求出经过一系列复杂的切孔后会发生什么情况，他们特别想知道纸上形成的孔的数量。下图列出了经过切割后形成的一些图样。TwoholesTwoholesoneholeonehole【输入】输入文件第一行是一个整数N，表示切纸操作的次数，1≤N≤100。接下来的N行中每行给出一个精确的切割操作，每次切割都给出了用空格隔开的四个整数，x1，y1，x2，y2，-1000≤x1，y1，x2，y2≤1000。x1和y1是切割线开始处的坐标值，x2和y2是切割线结束时的坐标值。你可以假设所有的切割点都在纸上，不会出界。每次切割都平行于纸上的x和y坐标轴。【输出】对于每次切割操作，要求输出纸上留下的单独的孔数。注意任何孔的最小面积不低于1平方单位。【样例】cutter.incutter.out410111111010000001【问题分析】按切线离散化x和y坐标，得到一n×m的矩形方格区域。从区域的边缘开始用floodfill对外区域染色。没有被染到的部分即是属于hole的部分。再用floodfill对尚未染色的部分染色，染多少个区域就有多少个hole。141 10.8栓狗方案源程序名dog.???（pas,c,cpp）可执行文件名dog.exe输入文件名dog.in输出文件名dog.out【问题描述】一个公园由2000000条垂直方向的道路与2000000条水平方向的道路围成栅格状，相邻两条平行道路间的距离为1，两个方向的道路均从1到2000000进行编号，每个栅格(面积为1平方)中都栽有一棵树。现在公园里有N只小狗在玩耍，它们的编号为1到N。每一只小狗都套着一根固定长度的链索，并且每一只狗都有一棵特别喜欢的树，小狗总是在路上散步，且链索总是拖在道路上，而不会拖到栅格中去。现在要把所有的小狗都栓到树上，一棵树上可以拴任意多条小狗，但拴狗方案必须满足以下条件：（1）每只小狗都能散步到达它最喜欢的树下。（2）无论编号小的小狗溜达到什么地方，编号大的小狗都能到达该地方，即任意一个编号小的小狗的活动范围必须包含在编号比它大的小狗的活动范围之内。请您编一程序为每一只小狗找一棵栓住它的树使得上述条件均能得到满足。【输入】输入文件的第一行包含一个整数N(1≤N≤100000)，表示小狗的数量。接下来的N行每行包含一只小狗的信息，第I+1行表示第I只小狗的信息，每行数据的格式如下：RSD表示这只小狗最喜欢的树位于第R行第S列，D为栓这只小狗的链索的长度，D不大于1000000。【输出】输出文件包含N行，第I行包含一对用空格隔开的整数表示用来栓第I只小狗的树的坐标。第一坐标表示行，第二坐标表示列，对每一组输入数据问题保证有解，但不一定唯一。【样例】dog.indog.out6202721271202723273192819275192921336192923296193026307【注释】小狗从栓它的树到喜欢的树之间的距离为两树横坐标之差的绝对值从加上纵坐标之差的绝对值。树的坐标用它的左下角的道路交叉点的坐标表示。【问题分析】首先要满足“小狗必须能够到达他最喜欢的树”这个条件，小狗被栓的位置必须在某一个正方形(矩形)区域内。一只小狗的活动区域要覆盖另一只，则这只小狗被栓的位置就是另一只小狗的区域的等比例扩张(仍为矩形)。而这只小狗本来要满足“小狗必须能够到达他最喜欢的树”这个条件，即它还被限制在另一个矩形内。所以，它实际的被栓的位置必须在两个矩形的交的区域内，这个交区域也是一个矩形。根据上述条件，反复作矩形的交，即得最后一只小狗的限制区域。任取区域内一点作为最后一只小狗的位置，再反向推到第一只，就能得到所有小狗的位置。141 10.9城市街道交通费系统源程序名erp.???（pas,c,cpp）可执行文件名erp.exe输入文件名erp.in输出文件名erp.out【问题描述】城市街道交费系统最近创立了。一辆汽车左转一次需付费$1，右转一次需付费$5。只有当前进、左转、右转都无路可走的时候，调头才是允许的，调头每次付费$10。给出一张城市地图，要求你求出从起始点到达终止点的花费最少的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。【样例1】如下图，符号‘#’代表街道，符号‘.’代表障碍区，符号‘E’表示起始站且汽车面朝东，符号‘F’表示汽车终止点。...............#####......#...#......#...#．．.#E######．．....#．．．．．．.##F#．．．．．．最便宜的路径花费$8：直走，然后左转3次，最后右转到终止点F。如果先直走然后右转2次，花费将是$10。【样例2】如图10-2，符号‘S’表示起始站且汽车面朝南。最便宜的路径花费$7：立刻左转，直走，在第一个岔路口左转，随后右转。......................#######..............#.....#.......#......###...#.......#........#...#.......#......###...#.......#......#.....#.......#......############F#####.........#..........#.........#..........#.....#...#...#####..#.....#...#...#.#.#..#....#S########.#.#..#.....#.......#.###..#.....#.......#......#.............########.......................城市地图高度最小为4，最大为30，城市地图宽度亦最小为4最大为30。只有一个起点、一个终点，他们之间总存在可通达的路径。同时由于地图周围一圈均是障碍区，所以汽车是没有可能开除城市的。【输入】输入文件erp.in如下：（1）第一行有2个整数，地图高度h和宽度w。（2）其后h行每行w个字母，将是以下字母中的一个：‘.’表示障碍区‘#’表示道路141 ‘E’表示起始点且汽车面朝东‘W’表示起始点且汽车面朝西‘N’表示起始点且汽车面朝北‘S’表示起始点且汽车面朝南‘F’表示终点【输出】输出文件erp.out仅包含一个整数，即为最便宜路径的费用。【样例】erp.inerp.out8118...............#####......#...#......#...#...#E######......#.......##F#.................【问题分析】求最短路径。首先是建图，将地图中的每个点拆成4个结点(每个方向一个)。然后根据题中的要求，前进时边长为0，左转为1，右转为5，调头为10(注意，调头是有条件限制的)。整个图共有4n2个结点。对整个图用Dijkstra算法求一个最短路径，即得最小的费用，时间复杂度是O(N2)，其中N=4n2。事实上，我们建的图是一个稀疏图，每个点扩展出去的边很少，整个图的边数和点数是同阶的。所以，如果用Dijkstra+Heap去求最短路径，时间复杂度就是O(Nlog2N)，N=4n2。141 10.10魔鬼之城源程序名pils.???（pas,c,cpp）可执行文件名pils.exe输入文件名pils.in输出文件名pils.out【问题描述】在一个被分割为N*M个正方形房间的矩形魔鬼之城中，一个探险者必须遵循下列规则才能跳跃行动。他必须从(1,1)进入，从(N,M)走出；在每一房间的墙壁上都写了一个魔法数字，是1～13之内的自然数；探险者可以想像出8个方向中的任何一个(水平或垂直或对角线方向)，随后他就可以作一次空间跳跃穿过这一方向上的连续的X个房间，其中X是他原来所在房间的魔法数字。但如果在这一方向上的房间数小于X，则他不作任何跳跃，而必须想像另一个方向。同时，探险者不能作连续两次相同方向的跳跃。123451336711232113332211421221例如在上图的5*4的魔鬼之城中，如果探险者现在所在的位置是(3,3)，那么通过依次空间跳跃他可以到达下列房间中的一个：(1,1)，(3,1)，(1,3)，(5,1)，或(5,3)。另外，如果他要用两次跳跃从(5,4)到达(3,2)，则他不能首先跳到(4,3)(因为这样他第二次跳跃的方向将和第一次相同，而这是不允许的)。所以他必须先跳跃到(2,1)。请你写一个程序，对给定的地图，算出探险者至少需要跳跃多少步才能离开魔鬼之城。【输入】一行给出N，M(都不超过100)；下来有M行，每行为N个自然数，表示对应房间中的魔法数字。【输出】出最小步数，如果探险者无法离开魔鬼之城，请输出“NEVER”。【样例】pils.inpils.out544336711321133221121221【问题分析】广度优先搜索。将地图中的每个格子(x,y)分离出8个状态，每个状态对应一个方向，即用(x,y,d)表示一个状态，其中，x和y表示位置，d表示上一次行动的方向。扩展的时候，(x,y,d)可以向除d以外的另七个方向扩展。时间复杂度是O(82×n2)，即O(n2)。141 10.11可见矩形源程序名squares.???（pas,c,cpp）可执行文件名squares.exe输入文件名squares.in输出文件名squares.out【问题描述】给定平面上n个互不相交(指公共面积为零)的正方形，它们的顶点坐标均为整数。设坐标原点为O(0,0)。对于任一正方形R，如果可以找到R的边上2个不同的点A和B，使三角形OAB的内部与其他正方形无公共点，则称正方形R是从O点可见的正方形。对于给定的n个互不相交的正方形，计算从坐标原点O可见的正方形个数。【输入】输入文件的第一行是正方形个数n(1≤n≤1000)。接下来n行中，每行有3个表示正方形的整数X，Y，L。其中，X和Y表示正方形的左下角顶点坐标，L表示边长，1≤X,Y,L≤10000。【输出】输出文件仅有一行包含一个整数，表示从坐标原点O可见的正方形个数。【样例】squares.insquares.out33264141241【问题分析】取所有正方形的4个顶点按极角离散化。每个离散化区间内能看到的正方形最多只可能是一个(可能没有)。枚举每个离散化区间，然后再枚举正方形，求正方形与区间的交，其中离原点最近的那个正方形就是在这个区间内能被看见的正方形。141'