第五届全国青少年信息学奥林匹克分区联赛提高组复赛试题解析(1999年）
[第一题]
拦截导弹（28分）
一．
问题描述：
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例：
INPUT
OUTPUT
389
207 155
300 299
170 158
65
6（最多能拦截的导弹数）
2（要拦截所有导弹最少要配备的系统数）
二．算法分析：
第一部分是要求输入数据串中的一个最长不上升序列的长度，可使用递推的方法，具体做法是从序列的第一个元素开始，依次求出以第i个元素为最后一个元素时的最长不上升序列的长度len(i)，递推公式为len(1)=1，len(i)=max(len(j)+1)，其中i>1，j=1,2,…i-1，且j同时要满足条件：序列中第j个元素大于等于第i个元素。
第二部分比较有意思。由于它紧接着第一问，所以比赛时很容易受前面的影响，采取多次求最长不上升序列的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度序列“7
5 4 1 6 3 2”，用多次求最长不上升序列（“7
5 4 3 2”）的结果为3套系统；但其实只要2套，分别击落“7
5 4 1”与“6
3 2”。那么，正确的做法又是什么呢？
我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要；上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种贪心算法。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，从拦截某个导弹所选的系统入手。
题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？当前瞄准高度较高的系统的“潜力”较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。
解题时，用一个数组记下已有系统的当前瞄准高度，数据个数就是系统数目。
[第二题]
回文数（25分）
一．
问题描述：
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。
又如：对于10进制数87：
STEP1：87+78
= 165
STEP2：165+561
= 726
STEP3：726+627
= 1353
STEP4：1353+3531
= 4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个N（2<=N<=10或N=16）进制数M，求最少经过几步可以得到回文数。
如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”
样例：
INPUT
OUTPUT
N
= 9 M= 87
STEP=6
二．算法分析：
本题的难度较低，主要是考察选手对数据结构的掌握与运用。问题可以分为三个部分。
第一，是对读入数据的处理。本题中，数据的进制是可变的，所以用整型数（即十进制数）不是很方便，考虑一般情况，我们可以采用字符串读入，再对数据作后期加工，把它的每一位都分离开来，存入一个数组里。数组的零下标段记录了数据的位数，便于进行运算和比较。在转化过程中要注意到16进制的特殊性，我们对于字母A
B C D E F要单独处理。
第二，进行判断与运算。有的选手在比赛时是用字符串作运算的，我个人没有采用这种方法。因为我觉得存储时用什么形式表示其实无所谓，关键是做加法运算的时候要符合n进制的规律。所以，我的运算一律以10进制形式存储，A用10，F用15表示。判断是否构成回文数时也一样用10进制，逐对比较对称的两个数位上的数字，看它们是否相等。做加法的次数以30次为限。
第三，输出结果。如果当前的数是回文数，则输出步数；否则按“Impossible”输出。
[第三题]
旅行家的预算（27分）
一．
问题描述：
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。
计算结果四舍五入至小数点后两位。
如果无法到达目的地，则输出“No
Solution”。
样例：
INPUT
D1=275.6
C=11.9 D2=27.4
P=2.8 N=2
|
油站号I
|
离出发点的距离Di
|
每升汽油价格Pi
|
|
1
|
102.0
|
2.9
|
|
2
|
220.0
|
2.2
|
OUTPUT
26.95（该数据表示最小费用）
二．算法分析：
看到这道题，许多人都马上判断出穷举是不可行的，因为数据都是以实数的形式给出的。但是，不用穷举，有什么方法是更好的呢？递推是另一条常见的思路，但是具体方法不甚明朗。
既然没有现成的思路可循，那么先分析一下问题不失为一个好办法。由于汽车是由始向终单向开的，我们最大的麻烦就是无法预知汽车以后对汽油的需求及油价变动；换句话说，前面所买的多余的油只有开到后面才会被发觉。
提出问题是解决的开始。为了着手解决遇到的困难，取得最优方案，那就必须做到两点，即只为用过的汽油付钱；并且只买最便宜的油。如果在以后的行程中发现先前的某些油是不必要的，或是买贵了，我们就会说：“还不如当初不买。”由这一个想法，我们可以得到某种启示：假设我们在每个站都买了足够多的油，然后在行程中逐步发现哪些油是不必要的，以此修改我们先前的购买计划，节省资金；进一步说，如果把在各个站加上的油标记为不同的类别，我们只要在用时用那些最便宜的油并为它们付钱，其余的油要么是太贵，要么是多余的，在最终的计划中会被排除。要注意的是，这里的便宜是对于某一段路程而言的，而不是全程。
由此，我们得到如下算法：从起点起，每到一个站都把油箱加满（终点除外）；每经过两站之间的距离，都按照从便宜到贵的顺序使用油箱中的油，并计算花费，因为这是在最优方案下不得不用的油；如果当前的油价低于油箱中仍保存的油价，则说明以前的购买是不够明智的，其效果一定不如购买当前加油站的油，所以，明智的选择是用本站的油代替以前购买的高价油，留待以后使用，由于我们不是真的开车，也没有为备用的油付过钱，因而这样的反悔是可行的；当我们开到终点时，意味着路上的费用已经得到，此时剩余的油就没有用了，可以忽略。
数据结构采用一个队列：存放由便宜到贵的各种油，一个头指针指向当前应当使用的油（最便宜的油），尾指针指向当前可能被替换的油（最贵的油）。在一路用一路补充的过程中同步修改数据，求得最优方案。
注意：每到一站都要将油加满，以确保在有解的情况下能走完全程。
本题的一个难点在于认识到油箱中油的可更换性，在这里，突破现实生活中的思维模式显得十分重要。
[第四题]
邮票面值设计（40分）
一．
问题描述：
给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1~MAX之间的每一个邮资值都能得到。
例如，N=3，K=2，如果面值分别为1分、4分，则在1分~6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分~7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
样例：