数组练习题Word格式.docx

数组练习题Word格式.docx

《数组练习题Word格式.docx》由会员分享，可在线阅读，更多相关《数组练习题Word格式.docx（16页珍藏版）》请在冰点文库上搜索。

如:

10.找数字对:

输入N（2<

=N<

=100）个数字（在0与9之间）,然后统计出这组数中相邻两数字组成的链环数字对出现的次数.例如:

输入:

N=20

01598722232787879659

输出：

（7，8）=2（8，7）=3{指（7，8）、（8，7）数字对出现次数分别为2次、3次）

（7，2）=1（2，7）=1

（2，2）=2

（2，3）=1（3，2）=1

【提高篇】

（1995年普及组第四题）

第一题:

编码问题：

设有一个数组A:

ARRAY[0..N-1]OFINTEGER；

数组中存放的元素为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）

程序要求解决以下问题：

1给出数组A后，求出其编码；

给出数组A的编码后，求出A中的原数据。

（1995年普及组第二题）

第二题:

方阵填数：

在一个N

N的方阵中，填入1，2，……N

N个数，并要求构成如下的格式：

（2003普及组第一题）vijosp1217

第三题:

乒乓球（Table.pas）

【问题背景】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。

其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。

华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。

在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。

【问题描述】华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。

比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：

WWWWWWWWWWWWWWWWWWWWWWLW

在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。

而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。

如果一局比赛刚开始，则此时比分为0比0。

你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。

【输入格式】每个输入文件包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。

其中E表示比赛信息结束，程序应该忽略E之后的所有内容。

【输出格式】输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。

其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。

【输入样例】

WWWWWWWWWWWWWWWWWWWW

WWLWE

【输出样例】

11:

1:

21:

2:

（2004普及组第一题）vijosp1113

第四题:

不高兴的津津

【问题描述】

津津上初中了。

妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。

另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。

但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。

假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。

请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；

如果会的话，哪天最不高兴。

【输入文件】

输入文件unhappy.in包括七行数据，分别表示周一到周日的日程安排。

每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。

【输出文件】

输出文件unhappy.out包括一行，这一行只包含一个数字。

如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1,2,3,4,5,6,7分别表示周一，周二，周三，周四，周五，周六，周日）。

如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

【样例输入】

53

62

72

54

04

06

【样例输出】

3

第五题：

谁拿了最多奖学金Noip2005T-1（Vijos1001）

（scholar.pas/c/cpp）

某校的惯例是在每学期的期末考试之后发放奖学金。

发放的奖学金共有五种，获取的条件各自不同：

1） 

院士奖学金，每人8000元，期末平均成绩高于80分（>

80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；

2） 

五四奖学金，每人4000元，期末平均成绩高于85分（>

85），并且班级评议成绩高于80分（>

80）的学生均可获得；

3） 

成绩优秀奖，每人2000元，期末平均成绩高于90分（>

90）的学生均可获得；

4） 

西部奖学金，每人1000元，期末平均成绩高于85分（>

85）的西部省份学生均可获得；

5） 

班级贡献奖，每人850元，班级评议成绩高于80分（>

80）的学生干部均可获得；

只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。

例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。

现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。

输入文件scholar.in的第一行是一个整数N（1<

=N<

=100），表示学生的总数。

接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。

姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；

期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；

是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；

发表的论文数是0到10的整数（包括0和10）。

每两个相邻数据项之间用一个空格分隔。

输出文件scholar.out包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。

如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。

第三行是这N个学生获得的奖学金的总数。

4

YaoLin8782YN0

ChenRuiyi8878NY1

LiXin9288NN0

ZhangQin8387YN1

ChenRuiyi

9000

28700

（2005年普及组第二题）vijosp1103

第六题:

校门外的树

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。

我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；

数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。

这些区域用它们在数轴上的起始点和终止点表示。

已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。

现在要把这些区域中的树（包括区域端点处的两棵树）移走。

你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入文件tree.in的第一行有两个整数L（1<

=L<

=10000）和M（1<

=M<

=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。

接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

5003

150300

100200

470471

298

【数据规模】

对于20%的数据，区域之间没有重合的部分；

对于其它的数据，区域之间有重合的情况。

（2006普及组第一题）vijosp1316

第七题:

明明的随机数　

描述Description

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。

然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。

请你协助明明完成“去重”与“排序”的工作。

输入格式InputFormat

输入有2行，第1行为1个正整数，表示所生成的随机数的个数：

N

第2行有N个用空格隔开的正整数，为所产生的随机数。

输出格式OutputFormat

输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。

第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例输入SampleInput

10

2040326740208930040015

样例输出SampleOutput

8

152032406789300400

第八题:

隐形的翅膀（Vijos1237）

小杉终于进入了天堂。

他看到每个人都带着一双隐形翅膀，他也想要。

（小杉是怎么看到的？

……）,天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。

现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。

每组测试数据的

第一行有一个数N（2<

=30000）

第二行有N个不超过1e5的正整数，表示N只翅膀的长度。

20%的数据N<

=100

对每组测试数据输出两个整数，分两行，表示小杉挑选出来的一对翅膀。

注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。

2346

2

注释Hint

你可以认为黄金分割比就是0.6180339887498949

第九题：

砝码称重

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<

=1000），

要求：

输入方式：

a1a2a3a4a5a6

（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）

输出方式：

Total=N

（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

如输入：

1_1_0_0_0_0（注：

下划线表示空格）

输出：

TOTAL=3表示可以称出1g，2g，3g三种不同的重量。

第十题：

火星人（Vijos1115）

人类终于登上了火星的土地并且见到了神秘的火星人。

人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。

这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字——掰手指。

火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。

火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。

如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；

12354第二小，它表示2；

54321最大，它表示120。

下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字：

三进制数

123

132

213

231

312

321

代表的数字

5

6

现在你有幸成为了第一个和火星人交流的地球人。

一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。

你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。

输入数据保证这个结果不会超出火星人手指能表示的范围。

输入文件martian.in包括三行，第一行有一个正整数N，表示火星人手指的数目（1≤N≤10000）。

第二行是一个正整数M，表示要加上去的小整数（1≤M≤100）。

下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出文件martian.out只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。

每两个相邻的数中间用一个空格分开，不能有多余的空格。

12345

【样例输出】

12453

第十一题：

jam计算法（Vijos1318）

【选做篇】

1.CoVH之密码破解Vijos1181

话说一天，Dragon.Dai大菜和整个OIBHQQ群的超级大牛同心协力，终于进入了Vijos的系统，并设置了重重机关……

等到V某带着柯南来到服务器准备检查Log（即是日志文件）时，才发现Log文件被加了密，密码是一个数列中的指定一位……（数列见下）经过V某及柯南的思考，总算破解了密码，看到了Log。

输入格式InputFormat

数列：

12345678910111213...........

输入是一个数n，表示求数列的第n位

1<

=n<

=10^8

输出格式OutputFormat

输出第n位上的数

样例输入SampleInput

33

样例输出SampleOutput

1

2.上下车问题：

Noip1998第一题

火车从始发站（称为第1站）开出,在始发站上车的人数为a,然后到达第2站,在第2站有人上、下车,但上、下车

的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。

从第3站起（包括第3站）上、

下车的人数有一定的规律：

上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终

点站的前一站（第n-1站），都满足此规律。

现给出的条件是：

共有N个车站，始发站上车的人数为a,最后一站

下车的人数是m（全部下车）。

试问从x站开出时车上的人数是多少？

输入：

a,n,m和x

x站开出时车上的人数

3.回文数（25分）Noip1999T-2（Vijos1304）

　　若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回

文数。

例如：

给定一个10进制数56，将56加65（即把56从右向左读），得到121是

一个回文数。

又如，对于10进制数87，

STEPl：

87＋78=165STEP2：

165＋561=726

STEP3：

726＋627＝1353STEP4：

1353+3531=4884

　　在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

　　写一个程序，给定一个N（2＜n＜＝10，N=16）进制数M．求最少经过几步可以得到

如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible”

样例：

INPUT

N＝9M＝87

Output

STEP=6

4.儿子游戏机vijos1300

陈老奔的弟弟苏毛头最近迷上了一款游戏叫“儿子游戏机”，这款游戏乃是老奔制作的一个学龄前儿童的学习游戏，游戏的原理是做加减法并统计得分的程序。

得分为千分制，共有mt道题（0<

mt<

=1000）。

　　可是毛头很笨，2岁就会算100以内的加减法的老奔的弟弟居然6岁了只能算n（0<

n<

=100）以内的加减法，而且脑子一根筋地认为1+3=2，并且大于十的加数相加不会进位。

　　“n以内”表示的是：

加数、减数、被减数、和、差在任何时候都不超过n，超过了毛头必然做错（毛头的习惯是空着不做）。

　　毛头做题只要出现了1+3的环节就会出错：

　　1+3=２19+30=２９11+33+11+33=６６　11+30-21=０1+1+1+1=２

　　毛头大于十的加数相加不会进位：

　　6+4=１０19+9=１８24+56=７０99+1=９０

　　毛头的减法掌握很好，没有问题。

　　毛头的一张试卷如下：

n=20，mt=10

1+3=２×

6+5=１１√

10+10=２０√

14+6=１０×

5+9=１４√

10+11=×

32-31=×

1+2+3+4+5-6-7=２√

1+1+1+1-1-1=０×

3+9+6+5+8+7-5-6-7-8-6=×

　　这样，这个小笨蛋得了400分。

又要被老奔KTV了

（KTV：

K毛头一拳，T毛头一脚，把毛头折成V字型）

第一行为两个整数：

n,mt具体功用见“描述”

（mt可以被1000整除）

以下mt行为题目，格式为

a+b=

a+b-c=

a-b+c-d+e+f=

...

等式不会超过100位，加数减数不会超过50个，且不超过3位

第一行输出一个整数：

毛头的得分

2010

1+3=

6+5=

10+10=

14+6=

5+9=

10+11=

32-31=

1+2+3+4+5-6-7=

1+1+1+1-1-1=

3+9+6+5+8+7-5-6-7-8-6=

400

5.高精度乘法（Vijos1040）

高精度乘法

两行，每行表示一个非负整数（不超过10000位）

两数的乘积。

99

101

9999