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

全国青少年信息学奥林匹克联赛培训习题与解答 （中学高级本） 目录 篇 1.1 马拦过河卒 1.2 出栈序列统计 1.3 算24点 1.4 冗余依赖 1.6 单向双轨道 1.7 组合的输出 1.8 售货员的难题 第二章 递规与递推 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.2 出栈序列统计 1.3 算24点 1.4 冗余依赖 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 单向双轨道 如图所示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(1n27)及由n个小写字母组成的字符串。 【输出】 可以调度则输出最短的调度序列，不可以调度时则输出‘NO’。 【样例】 track.in track.out 3 c A B cba b A C a A D b C D