鄞州区中小学生计算机程序设计竞赛（2013）
复赛试题（小学组）
比赛时间：2013年10月15日下午12:30—15:00
题目一览
试题名称 | 磁铁 | 差异和 | 固定点 | 瓶子涂色 |
英文代号 | magnets | differencerow | fixedpoints | print |
程序名 | magnets.cpp/pas/c | differencerow.cpp/pas/c | fixedpoints.cpp/pas/c | print.cpp/pas/c |
输入文件名 | magnets.in | differencerow.in | fixedpoints.in | print.in |
输出文件名男人的心思 | magnets.out | differencerow.out | fixedpoints.out | print.out |
内存限制 | 256MB | 256MB | 256MB | 256MB 一衣带水什么意思 |
单点时限 | 1S | 1S | 1S | 1S |
| | | | |
注意：
一、 关于竞赛中编程语言使用的规定参照中国计算机学会公布的《关于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) + ... + ( a士兵军衔n -1- an)，叫做差异和，于是不同的排序方法可以得到不同的差异和。
戴维的任务就是要找出一种排序方案，使得这个数列的差异和的值最大。但是他很快就发现，得到最大的差异和可以有很多种排序方法，于是戴维决定找出其中“序列最小”的方案（关于序列大小，，越靠前的数越小的序列越小。
例如：对于1 2 3 4四个数组成的序列，序列1 3 2 4 比序列 1 3 4 2小）。
现在，请你用编程的办法帮帮戴维，找出他要的这个排序方案吧！
输入(differencerow.in)
输入的第一行包含整数n （2 ≤ n ≤ 500000）。
第二行包含n空间分隔的整数a1, a2, ..., an (|ai| ≤ 1000).
