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

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=klkkvekle+e=kvvveklk

3、k依照 些 那么可推导出：l=0， k=1， v=2， e=3eeklkkkv同 能 确定 表表示的是4 制加法程序 入：n n9表示行数。以下 n 行，每行包括n 个字符串，每个字串 用空格隔开。字串 有一个 +号，其它都由大写字母 成程序 出：各个字母表示什么数，格式如：l=0， k=1，加法运确 是几 制的。假 不可能 成加法表，那么 出“error！”第四届全国青少年信息学计算机奥林匹克分区联赛复赛参考答案高中组 号 入 出分 得分1.157324135 分1.201040685 分1.310152378813810 分2.133211215 分1212132.247542241310

4、 分132475422.34371341133132110 分13411331321372.46407323212171351315 分32132407135132173.1n=3m=1l=05 分+ml二进制mmlmlml3.2n=4m=1l=2p=010 分+mnp三进制mnmpmnmpmmnpmnp3.3n=6m=1l=2k=0n=4h=310 分+mlknh五进制mlhmmknlhnlmmmkkmlknhnmkmmnmhmlhnmkhmlmm3.4n=8m=2n=6l=1p=3q=015 分+mnlpqrsr=5s=4msllprmlqn七进制nlllrlqlmnlslplplqmsl

5、nrprlmsnplllqqmnlpqrsrlqlsnllrlplmsnlprlqslmll总计 =20+40+40=100 分noi 分区联赛 -1998 年第四届高中组试题解析注意：解析和源程序均为 oibh站长刘汝佳所写，疏漏在所难免，但至少程序均通过了竞赛时使用的测试数据，因此依旧能够一看。1. 火车从始发站 ( 称为第 1 站 ) 开出 , 在始发站上车的人数为 a, 然后到达第 2 站 , 在第 2 站有人上、下车 , 但上、下车的人数相同，因此在第 2 站开出时即在到达第 3 站之前车上的人数保持为 a 人。从第 3 站起包括第 3 站上、下车的人数有一定的规律： 上车的人数基本

6、上前两站上车人数之和， 而下车人数等于上一站上车人数，一直到终点站的前一站第n-1 站，都满足此规律。现给出的条件是：共有始发站上车的人数为a, 最后一站下车的人数是 m全部下车。试问从x 站开出时车上的人数是多少？输入： a,n,m 和 x输出： x 站开出时车上的人数(20%) 分析 n 个车站，典型的数学题。为了找规律，我们建立一个表。站号 123456开车时人数 numaa2a2a+b3a+2b4a+4b上车人数 inaba+ba+2b2a+3b3a+5b下车人数 out0bba+ba+2b2a+3b规律出来了，设第k(k=3) 站时上车人数为 fk-2a+fk-1b(fk=1,1,2

7、,3,5,8,13,21.容易证明，自己试一下吧。为 fibonacci数列 )numk=a+in2-out2+in3-out3.+ink-outk而 in2=out3,in3=out4.故 numk=a-out2+ink=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

8、-3+1)*a)div(fn-2-1);程序就只有 10 行了。注意 f24 用 integer装不下了，故只递推到f23 。所以，你用枚举也能够，只是不如这种方法吸引人。2. 设有 n 个正整数 , 将他们连接成一排 , 组成一个最大的多位整数 .例如 :n=3 时,3 个整数 13,312,343, 连成的最大整数为 :34331213 又如 :n=4 时,4 个整数 7,13,4,246 连接成的最大整数为 7424613程序输入 :nn 个数程序输出 : 连接成的多位数(40%) 分析 这是一道比较成功的题目。极易想到的算法是贪心法 - 按整数对应的字符串大到小连接，因为题目的例子都符

9、合，然而不难找到反例：12121应该组成 12121 而非 12112, 那么是不是相互包含的时候就从小到大呢？也不一定，如：12123 确实是 12312 而非 12112, 那么情况就多了。事实上此题确实是用贪心法，然而贪心标准不是上述那种，而是：假如 a 后接 b 比 b 后接 a 大，就说“ ab”。直截了当输出排序结果。正确性容易证明 , 大伙自己试试。程序见附件。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同时 , 能够确定该表表示的