第四届全国青少年信息学(计算机)奥林匹克分区联赛高中复赛试题汇总

1、第四届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组竞赛用时：3小时）1 .火车从始发站（称为第 1站）开出，在始发立上车的人数为a,然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前） 车上的人数保持为 a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车 的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a,最后一站下车的人数是 m （全部下车）。试问x站开出时车上的人数是多少？输入：a, n, m和x输出：从x站开

2、出时车上的人数。20%2 .设有n个正整数（n<20）,将它们联接成一排，组成一个最大的多位整数。例如：n=3时，3个整数13, 312, 343联接成的最大整数为：34331213又如：n=4时，4个整数7, 13, 4, 246联接成的最大整数为：7424613程序输入：nn个数程序输出：联接成的多位数40%3 .著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。例如：40%其含义为：+LKVEL+L=L L+K=K L+V=V, L+E=ELLKVEK+L=K K+K=V, K+V=E, K+E=KLKKVEKLVVEKLE+E=KV KKEE

3、KLKKKV根据这些规则可推导出：L=0, K=1, V=2, E=3同时可以确定该表表示的是4进制加法程序输入:n （nw9）表示行数。以下n行，每行包括n个字符串，每个字串间用空格隔开。（字串仅有一个为+'号,其它都由大写字母组成）程序输出: 各个字母表示什么数，格式如：L=0, K=1, 加法运算是几进制的。若不可能组成加法表，则应输出“ERROR”第四届全国青少年信息学（计算机）奥林匹克分区联赛复赛参考答案（高中组）题号输入输出分值得分1.15 7 32 4135分1.20 10 40 685分1.310 15 2378 813810分2.13121 21 33 2 1 1 2

4、 15分2.2413 24 75 427 5 4 2 2 4 1 310分2.341341 133 1321 373 7 1 3 4 1 1 3 3 1 3 2 110分2.46321 32 407 135 13 2174 0 7 3 2 3 2 1 2 1 7 1 3 5 1 315分3.1N=3 + M L M ML M L M LM=1 L=0二进制5分3.2N=4+ MNP M N MP M N MP MM N P MNPM=1 l=2 P=0三进制10分3.3N=6+ M L K N H M L H M MK N L H N L MM MK K M L K N H N MK MM N

5、 MH ML H N MK H ML MMM=1 l=2 k=0 n=4 h=3五进制10分3.4N=8+ M N L P Q RS M S LL P R M LQ N N LL LR LQ LM N LS LP L P LQ M S L N R P R LM S N P LL LQ Q M N L P Q R S R LQ LS N LL R LP LM S N LP R LQ S LM LLM=2 N=6 L=1 P=3 Q=0R=5 S=4七进制15分总计=20+40+40=100 分NOI 分区联赛- 199年第四届高中组试题解析注意：解析和源程序均为 OIBH站长刘汝佳所写，疏漏在所

6、难免，但至少程序均 通过了比赛时使用的测试数据，所以还是可以一看。1 . 火车从始发站（称为第1 站 ）开出, 在始发站上车的人数为a, 然后到达第2站 ,在第 2 站有人上、下车, 但上、下车的人数相同，因此在第2 站开出时（即在到达第3 站之前）车上的人数保持为a人。从第3 站起（包括第3 站）上、下车的人数有一定的规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a, 最后一站下车的人数是m （全部下车）。试问从x站开出时车上的人数是多少？输入：a,n,m 和 x输出：x

7、 站开出时车上的人数（20%） 分析 典型的数学题。为了找规律，我们建立一个表。站号1 2 3 4 56开车时人数num a a 2a 2a+b 3a+2b 4a+4b上车人数in a b a+b a+2b 2a+3b 3a+5b下车人数out 0 b b a+b a+2b 2a+3b规律出来了，设第k(k>=3) 站时上车人数为fk-2a+fk-1b (fk=1,1,2,3,5,8,13,21.为 fibonacci 数列)容易证明，自己试一下吧。numk=a+in2-out2+in3-out3.+ink-outk而 in2=out3,in3=out4.故 numk=a-out2+in

8、k=a-b+fk-2a+fk-1b=(fk-2+1)a + (fk-1-1)b (1)因为知道第n-1站开车时人数为m,容易求出b,再代入(1)求第x站开车时的人数 p。即：m=(fn-3+1)a + (fn-2-1)b (2)p=(fx-2+1)a + (fx-1-1)b (3)从(2)解得b,代入(3)计算知p=(fx-2+1)*a+(fx-1-1)*(m-(fn-3+1)*a) div (fn-2-1);程序就只有10行了。注意f24用integer装不下了，故只递推到f23 当然，你用枚举也可以，不过不如这种方法吸引人。2 .设有n个正整数，将他们连接成一排，组成一个最大的多位整数.例

9、如:n=3时,3个整数13,312,343,连成的最大整数为:34331213又如:n=4时,4个整数7,13,4,246 连接成的最大整数为7424613程序输入：NN个数程序输出：连接成的多位数(40%)分析这是一道比较成功的题目。极易想到的算法是贪心法-按整数对应的字符串大到小连接，因为题目的例子都符合，但是不难找到反例：12 121应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？ 也不一定，如：12 123就是12312而非12112，那么情况就多了。其实本题就是用贪心法，但是贪心标准不是上述那种，而是：如果a后接b比b后接a大，就说"a>b&q

10、uot;。直接输出排序结果。正确性容易证明 大家自己试试。程序见附件。3 .(40%)著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字.(40%)例如：+LKVELLKVEKKVEKLVVEKLKKEEKLKKKV其含义为：L+L=L,L+K=K,L+V=V,L+E=E,K+L=K,K+K=V,K+V=E,K+E=KL,E+E=KV根据这些规则可推导出：L=0,K=1,V=2,E=3同时，可以确定该表表示的是4进制加法程序输入：n(n<=9),表示行数，以下N行,每行N个字符串,每个字符串间用空格隔 开.(字用仅有一个为+'号，其他都由大写字

11、母组成)程序输出:(1)各个字母表示什么数，格式如:L=0,K=1,(2) 加法运算是几进制的(3) 若不可能组成加法表，则应输出"ERROR!" 分析 看起来很复杂，其实并不难。题目对“加法表”没有说清楚。虽然是取通常意义，题目也应该重新叙述。当年我就是把它理解的太宽，代码写了很多，虽然正确了，但浪费了不少时间。这道题说的“加法表”其实是狭义的，设为 k 进制，则第一行/第一列只能是0,1,2,3.k-1.（我当时考虑了二位甚至更多位的情况）, 那么程序的第一步应该是：把输入数据储存在T0.8,0.8 中 （最多 9行嘛！ ）, 删除相同行和列（我很懒，这一步就算了吧,作为是 k*k 的矩阵 . :-D ）来确定 k（ 剩下的不同的字母） 。如果出现二位以上的数或第一行/列的元素不同，则是"ERROR!"（我也懒彳导写了 ）然后匹配:若第一列为M的行有L