2001年青少年信息学奥赛复赛试题
题一：数的计数 (20分)<br><br>[问题描述]<br>我们要求找出具有下列性质数的个数(包含输入的自然数n):<br>先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理：<br>1、不作任何处理:<br>2、茬它的左边加上一个自然数，但该自然数不能超过原数的一半;<br>3、加上数后，继续按此规则进行处理，直到不能再而 自然数为止。<br>[样例] 输入：6<br>满足条件的数为 6 (此部分不必输出)<br>6<br>26<br>126<br>36<br>136<br>输出：6<br><br><br>题二 最大公约数与最小公倍数问题 (20分)<br><br>[问题描述]<br>输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。<br>条件:1、P、Q是正整数<br>2、要求P、Q以xO为最大公约数，以yO为最小公倍数。<br>试求，满足条件的所有可能的两个正整数的个数。<br>[样例]<br>输入：x0=3 y0=60<br>输出：4<br>说明：(不用输出)此时的 P Q 分别为，<br>3 60<br>15 12<br>12 15<br>60 3<br>所以，满足条件的所有可能的两个正整数的个数共4种。<br><br><br>题三 求先序排列 (30分)<br><br>[问题描述]<br>给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。<br>[样例]<br>输入：BADC BDCA<br>输出：ABCD<br><br><br>题四 装箱问题 (30分)<br><br>[问题描述]<br>有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从m个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。<br>[样例]<br>输入： 24 --个整数，表示箱子容量<br>6 一个整数，表示有n个物品<br>8 接下来n行，分别表示这n个物品的各自体积。<br>3<br>12<br>7<br>9<br>7<br>输出： 0 一个整数，表示箱子剩余空间。<br><br>NOI\'2001年第七届全国青少年信息学（计算机）<br>奥林匹克分区联赛复赛试题<br>提 高 组<br><br>题一 一元三次方程求解 (20分)<br><br>[问题描述]<br> 有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出改方程中各项的系数（a,b,c,d 均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），且根于根之差的绝对值>=1。<br> 要求由小到大依次在同一行输出这三个实根（根于根之间留有空格），并精确到小数点后2位。 <br><br>提示：记方程f(x)=0，若2个数x1和x2，且x1<x2，f(x1)*f(x2)<0,则在（x1,x2）之间一定有一个根。<br>[样例]<br> 输入：1 -5 -4 20 输出：-2.00 2.00 5.00<br><br><br>题二 数的划分 (20分)<br><br>[问题描述] <br> 将整数n分成k份，且每份不能为空，任意两分不能相同（不考虑顺序）。<br> 例如：n=7,k=3,下面三种分法被认为是相同的。<br> 1，1，5； 1，5，1； 5，1，1；<br> 问有多少种不同的分法。<br>输入：n,k (6<n≤200,2≤k≤6)<br>输出：一个整数，即不同的分法。<br>[样例]：<br> 输入：7 3<br> 输出：4<br>[说明]：（此部分不用输出）<br> 样例中的4种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3;<br><br><br>题三 统计单词个数 （30分）<br><br>[问题描述]<br> 给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字串分成k份（1<k≤40），且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，选用this之后就不能包含th）。<br> 单词在给出的一个不超过6个单词的字典中。<br> 要求输出最大的个数。<br>[输入格式]<br> 全部输入数据存放在文本文件input3.dat中，其格式如下：<br> 第一行为一个正整数(0<n≤5)表示有n组测试数据<br> 每组的第一行有二个正整数：（p,k)<br> p表示字串的行数；<br> k表示分为k个部分。<br> 接下来的p行，每行均有20个字符。<br> 再接下来有一个正整数s，表示字典中单词个数。（1≤s≤6）<br> 接下来的s行，每行均有一个单词。<br>[输出格式]<br> 结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。<br>[样例]<br>输入：1<br> 1 3<br> thisisabookyouareaoh<br> 4<br> is<br> a<br> ok<br> sab<br>输出： //说明：（不必输出）<br> 7 // this/isabookyoua/reaoh<br> sab<br><br><br>题四 Car的旅行路线 （30分）<br><br>[问题描述]<br> 又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市有四个机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。<br><br><br><br> 那么Car应如何安排到城市B的路线才能尽可能的节省花费呢？她发现这并不是一个简单的问题，于是她来向你请教。<br>[任务]<br> 找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。<br> 输入文件：键盘输入文件名<br> 输 出：到屏幕（输出最小费用，小数点后保留2位。）<br>输入格式：<br> 第一行为一个正整数n（0≤n≤10），表示有n组测试数据。<br> 每组的第一行有四个正整数S，t，A，B。<br> S（0<S≤100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1≤A，B≤S）。<br> 接下来有S行，其中第i行均有7个正整数xi1,yi1,xi2,yi2,xi3,yi3,Ti，这当中的(xi1,yi1),(xi2,yi2),(xi3,yi3)分别是第i个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。<br>输出格式：<br> 共有n行，每行一个数据对应测试数据。<br>[样例]：<br>输入<br>1<br>3 10 1 3<br>1 1 1 3 3 1 30<br>2 5 7 4 5 2 1<br>8 6 8 8 11 6 3<br>输出： 47.55 <br><br>测试数据：up/1091196126.rar<br>解题报告：up/1091196098.rar<br>页:
[1]