全国大学生程序设计竞赛训练题.doc

1、(2) 联集读入 2 个正整数 a,b，请输出介于 a,b 之间（包含 a,b）2,3,5 倍数的联集大小。Input（输入可能包含了好几列测试资料，每一列有 2 个整数 a,b。a=0 b=0 代表输入结束。）Output（对每一列输入，请输出联集的大小。请参考 Sample Output ）Sample Input（1 10 ；10 20；0 0；）Sample Output（8；7）（3）Q100: The 3n + 1 problem考虑以下的演算法：1. 输入 n2. 印出 n3. 如果 n = 1 结束4. 如果 n 是奇数 那么 n=3*n+15. 否则 n=n/26. GOTO

2、 2例如输入 22, 得到的数列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 据推测此演算法对任何整数而言会终止 (当列印出 1 的时候)。虽然此演算法很简单，但以上的推测是否真实却无法知道。然而对所有的 n ( 0 0.01）。如果有不止一种转换可以获取超过 1%的利益，请输出转换次数最少的。如果转换次数最少的不止一种，那么任何一种都可以。请注意：在这里只要求转换次数最少，并没有要求获利要最大，只要能大于 1% 就可以了。另外，国税局还规定最多只能转换 n 次（n 是币种的数目）。像 1, 2, 1 这样的转换次数为 2。 如果在 n 次的转换内都

3、无法获利超过 1%，请输出 no arbitrage sequence exists。Sample Input Sample Output31.2 .89.88 5.11.1 0.1543.1 0.0023 0.350.21 0.00353 8.13 200 180.559 10.3392.11 0.089 0.0611122.00.451 2 11 2 4 1no arbitrage sequence exists（8）Q105: The Skyline Problem由于高速绘图电脑工作站的出现，CAD（computer-aided design）和其他领域（CAM,VLSI 设计）都充分

4、使用这些电脑的长处。而在本问题中，你必须帮助建筑师，根据他所提供给你都市中建筑物的位置，你得帮他找出这些建筑物的空中轮廓（skyline）。为了使问题容易处理一些，所有的建筑物都是矩形的，并且都建筑在同一个平面上。你可以把这城市看成一个二度平面空间。每一栋建筑物都以(L i Hi Ri)这样的序列来表示。其中 Li 和 R i分别是该建筑物左边和右边的位置，H i则是建筑物的高度。下方左图就是(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)这八栋建筑物的位置图。而你的任务就是

5、画出这些建筑物所构成的轮廓，并且以(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)这样的序列来表示如下方右图的轮廓。Input 只有一组测试资料。每列有一栋建筑物的资料。建筑物不会超过 50 栋。所有的数字都小于 10000。并且建筑物已按照 Li排好序。Output 输出为描述建筑物轮廓的向量。在轮廓向量（v 1,v2,v3,.,vn-1,vn）中，在 i 为奇数的情形下，v i表示一条垂直线（x 座标），在 i 为偶数的情形下，v i表示一条水平线（高度）。轮廓向量就像一只虫从最左边建筑物走起，沿著轮廓路径水平

6、及垂直的行走的路径。所以最后轮廓向量的最后一个数一定为 0。Sample Input1 11 52 6 73 13 912 7 1614 3 2519 18 2223 13 2924 4 28Sample Output1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0（9）Q107: The Cat in the Hat一只神奇聪明猫走进了一间乱七八糟的房间，他不想自己动手收拾，他决定要找帮手来工作。于是他从他的帽子中变出了 N 只小猫来帮他（变出来的猫，高度为原来猫的 1/(N+1) ）。这些小猫也有帽子，所以每一只小猫又从他的帽子中变出 N 只小小猫

7、来帮他。如此一直下去，直到这些小小小.猫小到不能再小（高度1），他们的帽子无法再变出更小的猫来帮忙，而这些最小的猫只得动手打扫房间。注意：所有猫的高度都是正整数。在这个问题中，给你一开始那只猫的高度，以及最后动手工作的猫的数目（也就是高度为 1 的猫的数目）。要请你求出有多少只猫是没有在工作的，以及所有猫的高度的总和。Input 每组测试资料一列，有 2 个正整数分别代表一开始那只猫的高度，以及最后动手工作的猫的数目。0 0 代表输入结束。Output 每组测试资料输出一列，包含 2 个正整数分别代表有多少只猫是没有在工作的，以及所有猫的高度的总和。Sample Input216 125576

8、4801 167961664 10 0Sample Output31 671335923 302759116 127（10）Q108: Maximum Sum给你一个 NxN 的阵列，请你找出有最大和的子区域（sub-rectangle）其和为多少。一个区域的和指的是该区域中所有元素值的和。一个区域是指相连的任意大小的子阵列。例如，对以下的二维阵列：其最大和的子区域位于左下角，并且其和为 15。如下所示：Input 只有一组测试资料，第一列有一个正整数 N（N = 100），代表此二维阵列大小为 NxN。从第二列起有 N2个整数，代表此阵列的内容。每个整数都介于-127 到 127 之间，且以

9、列为主（row-major）的顺序排列。Sample Input 即为上图所示的阵列。Output 输出有最大和的子区域其和是多少。Sample Input40 -2 -7 0 9 2 -6 2-4 1 -4 1 -18 0 -2Sample Output15（11）Q111: History Grading在资讯科学中有一些是关于在某些条件限制下，找出一些计算的最大值。以历史考试来说好了，学生被要求对一些历史事件根据其发生的年代顺序来排列。所有事件顺序都正确的学生无疑的可以得满分。但是那些没有全对的人又该如何给分呢？以下有 2 种可能的给分方式：每个与标准答案的顺序相同的事件得1 分 1。每

10、个在最长（但不一定要连续）的序列事件中，其相对的顺序亦可以在标准答案发现者，每个事件得 1 分。 举例说明：如果有 4 个事件其发生时间的顺序依次是 1 2 3 4（就是标准答案啦，意思是第 1 个事件发生顺序为 1，第 2 个事件发生的顺序为 2，.）。所以如果学生回答此 4 个事件发生的顺序依次是 1 3 2 4 的话，根据上面第 1种方法可以得 2 分（第 1 个及第 4 个事件）。但是如果以上面第 2 种方法可以得 3 分（1 2 4 或者 1 3 4 其相对的顺序可以在标准答案发现）在本问题中，请你写一个程式以第 2 个方法算出学生该得多少分。Input 只考一次试，所以输入的第 1

11、 列有一个整数 n（2 = n = 20）代表此次历史考试有多少个事件要排序。第 2 列为标准答案，有 n 个正整数c1,c2,.cn，（其内容为 1 到 n 的某种排列），c 1代表第 1 个事件发生的顺序，c 2代表第 2 个事件发生的顺序，依此类推。 从第 3 列开始每列为一学生的答案，每列有 n 个正整数 r1,r2,.rn，（其内容亦为 1 到 n 的某种排列），r 1代表学生回答第 1 个事件发生的顺序，r 2代表学生回答第 2 个事件发生的顺序，依此类推。Output 对每一学生的答案，输出其所得的分数。Sample Input103 1 2 4 9 5 10 6 8 71 2 3 4 5 6 7 8 9 104 7 2 3 10 6 9 1 5 83 1 2 4 9 5 10 6 8 72 10 1 3 8 4 9 5 7 6Sample Output6 5 10 9