您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 项目/工程管理 > 全国青少年信息学奥林匹克联赛培训习题与解答(中学高级本)
1全国青少年信息学奥林匹克联赛培训习题与解答(中学高级本)目录习题篇与解析篇第一章回溯法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取余运算24.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平板涂色38.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可见矩形4第一章回溯法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【算法分析】从起点开始往下走(只有两个方向可以走),如果某个方向可以走再继续下一步,直到终点,此时计数。最后输出所有的路径数。这种方法可以找出所有可能走法,如果要输出这些走法的话这种方法最合适了,但是本题只要求输出总的路径的条数,当棋盘比较大时,本程序执行会超时,此时最好能找出相应的递推公式更合适,详见后面的递推章节。51.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时就计数一次(这也是递归调用结束的条件)。61.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点主要应用四种运算.开始状态有四个操作数,一个运算符对应两个操作数,所以一开始选择两个操作数分别对四个操作符进行循环检测,每一次运算后产生了新的数,两个数运算变成一个数,整体是少了一个操作数,所以四个数最终是三次运算。由于操作的层数比较少(只有三层),所以可以用回溯的算法来进行检测,当找到一个解时便结束查找。如果所有的情况都找过后仍然没有,则输出无解的信息。71.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的依赖序列,选出其中长度最短的(最短的也可能并不惟一,因此本题答案有可能并不惟一),最短的证明序列中一定不存在多余的依赖,如果不是最短的证明序列,那么该证明序列中就有可能还有冗余依赖。81.5走迷宫源程序名maze.???(pas,c,cpp)可执行文件名maze.exe输入文件名maze.in输出文件名maze.out【问题描述】有一个m*n格的迷宫(表示有m行、n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的,分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输出相应信息(用-l表示无路)。【输入】第一行是两个数m,n(1m,n15),接下来是m行n列由1和0组成的数据,最后两行是起始点和结束点。【输出】所有可行的路径,描述一个点时用(x,y)的形式,除开始点外,其他的都要用“一”表示方向。如果没有一条可行的路则输出-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,
本文标题:全国青少年信息学奥林匹克联赛培训习题与解答(中学高级本)
链接地址:https://www.777doc.com/doc-5268057 .html