全国青少年信息学奥林匹克联赛培训习题与解答（中学高级本）
第一章 回溯法
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 求方程的根
电子版目录
习 题 篇
- 1 -
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 盒子与球
- 2 -
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可见矩形
- 3 -
第一章 回溯法
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 6 6 3 3
knight.out 6
- 4 -
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 3
stack1.out 5
- 5 -