当前位置：文档之家 › NOIP2008复赛普及组试题

NOIP2008复赛普及组试题

  • 格式：doc
  • 大小：640.00 KB
  • 文档页数：6

全国信息学奥林匹克竞赛（NOIP2008）复赛
普及组
注意事项：
1、文件名（程序名和输入输出文件名）必须使用小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。

各省在自测时可根据具体配置调整时限。

1. ISBN号码
(isbn.pas/c/cpp)
【问题描述】
每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”就是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。

ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。

识别码的计算方法如下：
首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。

例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，...,9,再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。

你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。

【输入】
输入文件isbn.in只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。

【输出】
输出文件isbn.out共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。

【输入输出样例2】
2. 排座椅
(seat.pas/c/cpp)
【问题描述】
上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。

不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。

同学们在教室中坐成了M行N列，坐在第i行第j列的
同学的位置是（i,j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。

在该方案下，上课时交头接耳的学生的对数最少。

【输入】
输入文件seat.in的第一行，有5个用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。

接下来的D行，每行有4个用空格隔开的整数。

第i行的4个整数X i，Y i，P i，Q i，表示坐在位置(X i，Y i)与(P i，Q i)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

【输出】
输出文件seat.out共两行。

第一行包含K个整数，a1，a2……a K，表示第a1行和a1+1行之间、第a2行和a2+1行之间、…、第a K行和第a K+1行之间要开辟通道，其中a i< a i+1，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含L个整数，b1，b2……b L，表示第b1列和b1+1列之间、第b2列和b2+1列之间、…、第b L列和第b L+1列之间要开辟通道，其中b i< b i+1，每两个整数之间用空格隔开（列尾没有空格）。

【输入输出样例】
上图中用符号*、※、+标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

3. 传球游戏
(ball.pas/c/cpp)
【问题描述】
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。

这次，老师带着同学们一起做传球游戏。

游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师在此吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。

聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。

两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。

比如有三个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。

【输入】
输入文件ball.in共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。

【输出】
输出文件ball.out共一行，有一个整数，表示符合题意的方法数。

【输入输出样例】
【限制】
40%的数据满足：3<=n<=30，1<=m<=20
100%的数据满足：3<=n<=30，1<=m<=30
4. 立体图
(drawing.pas/c/cpp)
【问题描述】
小渊是个聪明的孩子，他经常会给周围的小朋友们将写自己认为有趣的内容。

最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。

小渊有一块面积为m*n的矩形区域，上面有m*n个边长为1的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是1），小渊想请你打印出这些格子的立体图。

我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放：
每个顶点用1个加号’+’表示，长用3个”-”表示，宽用1个”/”，高用两个”|”表示。

字符’+’,”-”,”/”,”|”的ASCII码分别为43，45，47，124。

字符’.’(ASCII码46)需要作为背景输出，即立体图里的空白部分需要用’.’来代替。

立体图的画法如下面的规则：若两块积木左右相邻，图示为：
若两块积木上下相邻，图示为：
若两块积木前后相邻，图示为：
立体图中，定义位于第(m,1)的格子（即第m行第1列的格子）上面自底向上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。

【输入】
输入文件drawing.in第一行有用空格隔开的2个整数m和n，表示有m*n个格子（1<=m,n<=50）。

接下来的m行，是一个m*n的矩阵，每行有n个用空格隔开的整数，其中第i行第j 列上的整数表示第i行第j列的个子上摞有多少个积木（1<=每个格子上的积木数<=100）。

【输出】
输出文件drawing.out中包含题目要求的立体图，是一个K行L列的字符串矩阵，其中K和L表示最少需要K行L列才能按规定输出立体图。

合集下载

2008noip普及组复赛--排座位--代码C++

2008noip普及组复赛--排座位--代码C++

2.排座椅（seat.pas/c/cpp）【问题描述】上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。

不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。

同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。

在该方案下，上课时交头接耳的学生对数最少。

【输入】输入文件seat.in的第一行，有5各用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。

接下来D行，每行有4个用空格隔开的整数，第i行的4个整数X i，Y i，P i，Q i，表示坐在位置(X i,Y i)与(P i,Q i)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

【输出】输出文件seat.out共两行。

第一行包含K个整数，a1a2……a K，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第a K行和第a K+1行之间要开辟通道，其中a i< a i+1，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含L个整数，b1b2……b k，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第b L列和第b L+1列之间要开辟通道，其中b i< b i+1，每两个整数之间用空格隔开（行尾没有空格）。

【输入输出样例解释】1 2 3 4 5上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

noip普及组复赛模拟试题12答案

noip普及组复赛模拟试题12答案

【试题描述】读入二行整数，然后程序要完成如下的操作：第一步将2行数合并在一起，第二步将合并好的数由大到小排序，第三步重新排列，从第一个数起开始编号，然后将奇数号上的数（样例中的13，9，5）从前向后排，偶数号上的数（样例中的12，7，4）从后往前排。

第四步计算，将排好的数，第一个+第二个数的2倍+第三个数的3倍+…第五步：输出计算的结果。

【输入描述】第一行是一个整数 n(1≤n≤10)，第二行有n个整数，整数范围在1~100之间，数与数之间空格隔开。

第三行是一个整数 m(1≤m≤10)，第四行有m个整数，整数范围在1~100之间，数与数之间空格隔开。

【输出描述】一个整数（最后计算的结果）。

【输入样例】412 4 5 9213 7【输出样例】 169【解题提示】样例说明：第一步合并后为：12 4 5 9 13 7第二步上例中的数成为：13 12 9 7 5 4第三步得到：13 9 5 4 7 12第四步计算后为：13+2×9+3×5+4×4+5×7+6×12=169最后输出 169【试题来源】 2008年江苏省小学生信息学（计算机）奥赛program ex1731;var m,n,i,j,s,t,b1,b2:integer;a,b,c:array[1..20] of integer;sum:longint;beginreadln(n);for i:=1 to n do read(a[i]);readln(m);for i:=1 to m do read(a[i+n]);s:=m+n;for i:=1 to s-1 dofor j:=i+1 to s doif a[i]<a[j] then begint:=a[i];a[i]:=a[j];a[j]:=t;end;b1:=0;b2:=0;for i:=1 to s doif i mod 2=1 then begin inc(b1); b[b1]:=a[i];endelse begin inc(b2); c[b2]:=a[i];end;for i:=1 to b1 do a[i]:=b[i];for i:=1 to b2 do a[b1+i]:=c[b2-i+1];sum:=0;for i:=1 to s dosum:=sum+i*a[i];writeln(sum);end.输入 615 34 25 9 22 39423 17 46 57输出1496输入1015 34 25 9 22 39 47 12 33 99823 17 46 57 51 8 38 64输出5687SHLQSH数问题描述：我们把t1 , t2 (包括t1 , t2 (1<=t1<t2<=10000000))之间的所有数的约数个数和n称为t1 , t2的shlqsh数;问题是给出数据t1 , t2后,求t1 , t2的shlqsh数；输入输入文件shlqsh.in 仅包含一行，共有两个整数，表示t1 t2 (用空格分开)输出输出文件shlqsh.out 仅有一个整数，表示t1 , t2之间的shlqsh数。

NOIP普及组历届试题分析

NOIP普及组历届试题分析


对于100%的数据，3 ≤ n ≤ 100 测验题给出的正整数大小不超过10,000。
试题分析

题意大意：给你n个数，在这n个数中，找 到满足A+B=C的C的个数，注意不是这个 等式的个数。
样例中，1,2,3,4有1+2=3，1+3=4两个。

由于本题数据规模n<=100，我们可以直接
枚举C, A, B，三层循环解决问题。
扫雷游戏 (noip2015普及组第二题)
输入样例 1 33 *?? ??? ?*? 输入样例 2 23 ?*? *??
输出样例 1 mine.out *10 221 1*1 输出样例 2 mine.out 2*1 *21
对于 100%的数据，1≤n≤100，1≤m≤100
问题分析：
本题也是简单的枚举类试题。 我们从雷区的第一行第一列(1,1)开始，判断它周围 有多少个地雷。 由于本题读入的是字符，读入时需要注意： readln(n,m); for i=1 to n do begin for j=1 to m do read(a[i][j]); readln; end;
比例简化 (noip2014普及组第二题)



在社交媒体上，经常会看到针对某一个观点同意与 否的民意调查以及结果。例如，对某 一观点表示 支持的有 1498 人，反对的有 902 人，那么赞同与 反对的比例可以简单的记为1498:902。 不过，如果把调查结果就以这种方式呈现出来，大 多数人肯定不会满意。因为这个比例的数值太大， 难以一眼看出它们的关系。对于上面这个例子，如 果把比例记为 5:3，虽然与 真实结果有一定的误差， 但依然能够较为准确地反映调查结果，同时也显得 比较直观。 现给出支持人数 A，反对人数 B，以及一个上限 L， 请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均 不大于 L 且 A’和 B’互质（两个整数的最大公约数 是 1）的前提下，A’/B’ ≥ A/B 且 A’/B’ - A/B 的值 尽可能小。
1995-2008复赛试题及解析

1995-2008复赛试题及解析

NOIP1995年复赛试题1. 设有下列的算式：求出□中的数字，并打印出完整的算式来。

8 0 9 ------------- □□) □□□□ □□------------- □□□ □□□ ------------- 12. 方阵填数：在一个N ⨯N 的方阵中，填入1，2，……N ⨯N 个数，并要求构成如下的格式： 例：3. 若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A 类数，否则就称其为B 类数。

例如：（13）10=（1101）2 其中1的个数为3，0的个数为1，则称此数为A 类数； （10）10=（1010）2 其中1的个数为2，0的个数也为2，称此数为B 类数； （24）10=（11000）2 其中1的个数为2，0的个数为3，则称此数为B 类数； 程序要求：求出1～1000之中（包括1与1000），全部A 、B 两类数的个数。

4.编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER ；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i ≠j 时）。

例如：N=6时，有： A=（4，3，0，5，1，2） 此时，数组A 的编码定义如下： A[0]的编码为0；A[i]的编码为：在A[0]，A[1]，……A[i-1]中比A[i]的值小的个数（i=1，2……N-1） ∴上面数组A 的编码为：B=（0，0，0，3，1，2）程序要求解决以下问题：给出数组A 后，求出其编码；给出数组A 的编码后，求出A 中的原数据。

5. 灯的排列问题：设在一排上有N 个格子（N ≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N 1，N 2，……N k （k 表示不同颜色灯的个数）。

放灯时要遵守下列规则：同一种颜色的灯不能分开；不同颜色的灯之间至少要有一个空位置。

例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有：N=513 14 15 16 1 12 23 24 17 2 11 22 25 18 3 10 21 20 19 4 9 8 7 6 5N=616 17 18 19 20 1 153****221214 29 36 33 22 3 132****423412 27 26 25 24 5 11 10 9 8 7 6B-R 顺序放置的总数为12种。