haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

2013年宁波市鄞州区信息学竞赛复赛试题(小学组)

发布时间:2013-10-22 10:34:52  

鄞州区中小学生计算机程序设计竞赛(2013)

复赛试题(小学组)

比赛时间:2013年10月15日下午12:30—15:00

题目一览

注意:

一、 关于竞赛中编程语言使用的规定参照中国计算机学会公布的《关于NOI系列赛编程语言使用限制的规定》。

二、 评测环境为windows。

1.磁铁(magnets)

迈克是一个疯狂的游戏迷。有一天,迈克想玩多米诺骨牌,但他家里没有,于是他采用矩形磁体代替。每个矩形磁铁有两极:正极(”+”)和负极(“-”)。如果把两个磁铁水平方向靠近,就会出现“同极相斥、异极相吸”的现象。

(异极相吸)

(同极相斥)

一开始,迈克在桌子上水平地放上一块磁铁。

接下来,迈克会把磁铁一块接一块的放在原有磁铁的右端。

根据“同极相斥、异极相吸”的原理,迈克每放上一块新磁铁,就有可能出现相吸或者相斥的情况。

如果新磁铁和原磁铁相吸,它就加入到这个组(一个或多个磁铁连接在一起形成一组),如果新磁铁和原磁铁相斥,它就成为一个新组。

如下图,1、2、3块磁铁组成第一组,第4块磁铁单独成为一组,第5、6块磁铁组成一组,所以下图一共有三组:

为了描述方便,我们用1表示磁铁的正极(+),用0表示磁铁的负极(-),所以每个磁铁可以用“10”或者“01”来表示。

现在,迈克把他摆放磁铁的顺序告诉你,请帮忙统计出这些磁铁被分为几组?

输入(magnets.in)

第一行:一个整数 n (1≤? n?≤100000) 磁铁数量。

接下来n行:第i行(1≤? i?≤?n)中包含一个01串;“ 01 “表示迈克把第i个磁铁按照“-+”的位置摆放,“ 10 “则表示迈克把磁铁按照“+-“的位置水平摆放。

输出(magnets.out)

一行:输出磁铁组的数量。

样例1:

输入

6

10

10

10

01

10

10

输出

3

样例2:

输入

4

01

01

10

10

输出

2

注意

第一个测试样例对应于图中。测试样例有三组,分别包括三个,一个,两个磁铁。 第二个测试样例有两组,每组由两个磁铁组成。

数据范围

10%的数据:n<=10

50%的数据:n<=10000

100%的数据:n<=100000

2.差异和(differencerow)

小数学迷戴维最近在研究一个问题:对于一个由n个整数组成的序列:a1,?a2,?...,?an,把相邻的两个数之间的差:ax –ax+1 (1≤x<n)叫做差异值,把整个数列的所有差异值加在一起:(a1- a2) + (a2- a3)?

不同的差异和。

戴维的任务就是要找出一种排序方案,使得这个数列的差异和的值最大。但是他很快就发现,得到最大的差异和可以有很多种排序方法,于是戴维决定找出其中“序列最小”的方案(关于序列大小,,越靠前的数越小的序列越小。

例如:对于1 2 3 4四个数组成的序列,序列1 3 2 4 比序列 1 3 4 2小)。

现在,请你用编程的办法帮帮戴维,找出他要的这个排序方案吧! +?...?+?( an -1- an),叫做差异和,于是不同的排序方法可以得到

输入(differencerow.in)

输入的第一行包含整数n (2 ≤ n ≤ 500000)。

第二行包含n空间分隔的整数a1, a2, ..., an (|ai|?≤?1000).

输出(differencerow.out)

(a1- a2) + (a2- a3)?+?...?+?( an -1- an)= a1-an

按题目要求输出序列 a1,?a2,?... ,?ap

样例测试

输入

5

100 -100 50 0 -50

输出

100 -50 0 50 -100

数据范围

5%的数据:n<=10

30%的数据:n<=100

60%的数据:n<=5000

90%的数据:n<=100000

100%的数据:n<=500000

3.固定点(fixedpoints)

在数学中有这样一种定义,如果在一个长度为n的整数数列中,0到n-1分别都出现且仅出现一次,我们把这种序列叫做置换序列。

例如:序列[0,2,1]是一个长度为3的置换序列,而这两个[0,2,2]和[1,2,3]不是置换序列。

在一个置换序列中,如果一个整数 ai的和它所在的位置i存在这样的关系 ai?=?i,那么这个整数就是该置换序列的固定点,一个长度为n的置换序列最多可以有n个固定点。

例如,置换序列[0,2,1]有1个固定点和置换序列[0,1,2],有3个固定点。

现在有一个置换序列,你的任务是最大限度地提高固定点的数目,但你只能选两个元素进行一次交换位置的操作。

例如,置换序列[0,2,1],你可以交换2和1,这是你的固定点就有3个了。

请你用编程的方式完成这个任务,并且把交换后的置换序列的固定点个数输出来。 输入(fixedpoints.in)

第一行包含一个整数n(1≤? n ?≤10^5)。

第二行包含n整数由0,? 1,...,? n-1 组成长度为n的给定排列。

输出(fixedpoints.out)

一个整数 :最多一个交换操作可能的最大数量的固定点。

样例:

输入

5

0 1 3 4 2

输出

A[a[i]]=i

3

数据范围

10%的数据:n<=10

30%的数据:n<=300

60%的数据:n<=5000

100%的数据:n<=100000

4.瓶子涂色(print)

Description

小猪上小学的时候,一度对颜色非常感兴趣,虽然他的美术非常糟糕。 有一次他喝

完n瓶饮料把透明的瓶子排成一排,想把这些饮料瓶子都涂上颜色。他觉得如果所有相邻的两个瓶子颜色都不一样的话会比较有趣。他现在只有红色(Red)、绿色(Green)和蓝色(Blue)这三

种颜料。由于瓶子的大小和表面材质不同,在不同的瓶子上涂不同的颜色需要的花费都不一样。小猪统计了一下,把第i个瓶子染成红色需要Ri元钱,染成绿色需要Gi元钱,染成蓝色需要

Bi元钱。

现在请你帮他计算出要使相邻两个瓶子的颜色都不一样,他至少需要多少花费。

Input(print.in)

第一行只有一个整数n,表示共有n只瓶子。

第二行有n个正整数(以一个空格分隔),第i个数Ri表示把第i个瓶子染成红色需要Ri元钱。 第三行有n个正整数(以一个空格分隔),第i个数Gi表示把第i个瓶子染成绿色需要Gi元钱。 第四行有n个正整数(以一个空格分隔),第i个数Bi表示把第i个瓶子染成蓝色需要Bi元钱。 Output(print.out)

仅有一行,该行只有一个整数,表示最小花费。

Sample Input

5

1 3 1 2 2

1 2 3 4 3

4 2 1 5 3

Sample Output

9

HINT

30%的数据中,1 ≤ n ≤ 10;1 ≤ Ri, Gi, Bi ≤ 100。

60%的数据中,1 ≤ n ≤ 30;1 ≤ Ri, Gi, Bi ≤ 100。

100%的数据中,1 ≤ n ≤ 100000,1 ≤ Ri, Gi, Bi ≤ 100。

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com