第三届全国青少年信息学（计算机）奥林匹克分区联赛高中复赛试题

1、第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （高中组（高中组 竞赛用时：竞赛用时：3 小时）小时）1在 N*N 的棋盘上（1N10） ，填入 1，2，N*N 共 N*N 个数，使得任意两个相邻的数之和为素数。 （30%） 例如：当 N=2 时，有： 当 N=4 时，一种可以填写的方案如下：121615131410 在这里我们约定：左上角的格子里必须填数字 1。 程序要求： 输入：N； 输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！” 。2代数表达式的定义如下： 例如，下面的式子是合法的代数

2、表达式： a；其相邻数的和为素数的有：1+2，1+4，4+3，2+3acb字母 a+b*(a+c); a*a/(b+c) 下面的式子是不合法的代数表达式：ab; a+a*/(b+c); 程序要求： 输入：输入一个字符串，以“；”结束， “；”本身不是代数表达式中字符，仅作为结束） ； 输出：若表达式正确，则输出“OK” ；若表达式不正确，则输出“ERROR” ，及错误类型。错误类型约定：1 式了中出现不允许的字符；2 括号不配对；3 其它错误。 例如：输入：a+(b); 输出：OK 例如：输入：a+(b+c*a; 输出：ERROR 23骑士游历： 设有一个 n*m 的棋盘（2n50，2m50）

3、 ，如下图，在棋盘上左下角有一个中国象棋马。 （n,m） (1,1)马走的规则为：（1）马走日字；（2）马只能向右走即如下图如示： 任务 1：当 n,m 输入之后，找出一条从左下角到右上角的路径。 例如，输入：n=4，m=4 输出：路径的格式：(1,1)(2,3)(4,4)。若不存在路径，则输出NO 任务 2：当 n，m 给出之后，同时给出马起点的位置和终点的位置，试找出从起点到终点的所有路径的数目。 例如：（n=10,m=10） ， （1，5） （起点） ， （3，5） （终点）马(4,4)(1,1) 输 出：2（即由（1，5）到（3，5）共有 2 条路径） 输入格式：n,m,x1,y1,x

4、2,y2 (分别表示 n,m,起点坐标，终点坐标) 输出格式：路径数目（若不存在从起点到终点的路径，输出 0）第三届全国青少年信息学（计算机）奥林匹克分区联赛第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛测试数据（高中组）复赛测试数据（高中组） 赛区 学校题号输入输出实际输出得分11N=1NO12N=2 1 2 4 313N=3NO14N=4 1 2 11 12 1 2 11 12 4 15 8 5 4 9 8 5 7 16 3 14 7 10 3 14 6 13 10 9 6 13 16 1515N=5 1 2 3 4 7 1 2 3 4 7 6 5 14 15 16 6 5 14 1

5、5 1613 24 23 8 21 13 24 23 8 2110 19 18 11 20 10 19 18 11 20 9 22 25 12 17 9 22 25 12 17总计=2+6+2+9+11=30 分题号输入输出实际输出得分21a+xError 122(b+c)Ok23a+b(c+a)Error 324(a+(b+c)Error 225a+)b+c(Error 2109876543211 2 3 4 5 6 7 8 9 10总计=5+5+7+7+6=30 分题号任 务 一 31N=9，M=5（1，1）-（3，2）-（5，1）（6，3）-（7，1）-（8，3）-（9，5）（答案不唯一

6、）32N=3，M=3NO 任 务 二 33N=30，M=30（1，15） ， （3，15）234N=30，M=30（1，15） ， （5，15）835N=30，M=30（1，15） ，（10，15）46036N=50，M=50（1，25） ，（40，25）3，323，759，302，857，476总计=8+3+6+6+7+10=40 分NOI 分区联赛分区联赛 - 1997 年第三届高中组试题年第三届高中组试题解析解析注意：解析和源程序均为 OIBH 站长刘汝佳所写，疏漏在所难免，但至少程序均通过了比赛时使用的测试数据，所以还是可以一看。一.在 N*N 的棋盘上(1=N=10)填入 1,2,.

7、N*N 共 N*N 个数,使得任意两个相邻的数之和为素数.(30%)例如,当 N=2 时,有1 24 3其相邻数的和为素数的有:1+2,1+4,4+3,2+3当 N=4 时,一种可以填写的方案如下:12 11 1216 15 8513 49 1467 10 3在这里我们约定:左上角的格子里必须放数字 1程序要求:输入:N输出:若有多种解,则需输出第一行,第一列之和均为最小的排列方案;若无解,则输出NO!分析本题的题意有一点不明确。第一行，第一列之和均为最小。这是不一定能够达到的要求。这里，我理解成，第一行之和最小的情况下第一列之和最小。典型的搜索问题，我就不多说了。自上而下，自左向右搜索，每次

8、仅检查与上方，左方（如果存在的话）之和是否为素数。利用数组 used 确定数字是否已经用过。二.代数表达式的定义如下:(30%)代数表达式: 项:因子:字母: 例如,下面式子是合法的代数表达式:a;a+b*(a+c);a*a/(b+c);下列式子是不合法的代数表达式:ab;a+b*(c+d); 因子中无字母 d程序要求:输入:输入一个字符串,以;结束,(;本身不是代数表达式中字符,仅作为结束符号)输出:若表达式正确,则输出:OK; 若表达式不正确,则输出ERROR,及错误类型错误类型约定:1.式子中出现不允许的字符;2.括号不配对;3.其他错误例如:输入 a+(b); 输出:OK例如:输入 a

9、+(b+c*a; 输出 error 2分析个人认为比较好的题目，不难，但是要考虑全面却不大容易。第一类错误好说，可以出现的字符只有(除了最后的;)：a,b,c,+,-.*./,(,)。注意，如果不在末尾的;也是非法的。第二类用栈来实现。自左向右看，遇到左括号就入栈（其实只修改指针就可以了）,右括号就出栈。出栈时栈空，或者最后栈非空都是 error 2第三类情况比较多。例如存在以下子字符串的都是此类错误：(紧跟运算符，如 a+(+b)，运算符紧跟)，如 (c/)*b两个运算符连在一起，如+,-/等。两个字母连在一起，如 ab字母以后紧跟(,如 a+b(c+d), )以后紧跟字母，如(c-d)a+b两个括号连在一起，如(),(,), 因为括号只能在作为因子时才能使用。三.骑士游历:设有一个 n*m 的棋盘(2=n=50,2=m(2,3)-(4,4) 若不存在路径,则输出no任务 2:当 N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目.例如:(N=10,M=10),(1,5)(起点),(3,5)(