宁波市32届中小学生计算机解题报告

　　1.最佳交换

　　（change.pas/c/cpp）

　　【问题描述】

　　星星小朋友和 N-1 个小伙伴一起玩了一上午的纸牌游戏，星星总是能赢，气焰嚣张，

　　小伙伴们决定出道纸牌问题难倒星星，让他别再狂妄自大了，问题是这样的：每人摸一张牌，

　　每张牌上写着某一个数字，然后规定若干对伙伴间交换纸牌（每个小伙伴只允许交换一次），

　　交换得分就是大的纸牌值减去小的纸牌值，若干次得分加起来和最大是多少？

　　可是小伙伴们忘记了星星学过编程，请你和他一起来用程序解决这个问题吧。

　　【输入】

　　第一行两个用空格隔开的正整数 M，N，分别表示交换次数和总人数（星星也算在内）

　　第二行 N 个用空格隔开的正整数 ai

　　【输出】

　　一个正整数，表示最大得分值

　　【样例输入 1】

　　1 5

　　3 7 2 1 6

　　【样例输出 1】

　　6

　　【样例输入 2】

　　2 5

　　3 7 2 1 6

　　【样例输出 2】

　　10

　　【数据范围】

　　60%的数据中 M=1

　　80%的数据中 M≤2

　　100%的数据 M≤3，N≤100，ai≤1000

　　本次比赛今天刚刚结束，解题报告第一时间现在给出

　　第一题模拟 ，排序 从大到小 桶排，然后做m次减法，最大减最小，次大减次小。。。。。。

　　时间复杂度n 线性

　　2.买玩具

　　(buy.pas/c/cpp)

　　【问题描述】

　　玩具店有个活动，买2个送1个：3个玩具只要付较贵的2个玩具的钱就可以了。举个例子：

　　10 3 2 4 6 4 9，如果这样组合(10, 3, 2), (4, 6, 4), (9),就在第一个括号中省下2元，第二个括号

　　中省下4元，但第三个括号不能省了，因为只有一个玩具。

　　小星星是个懂事的孩子，他想尽可能的为家里省钱，他能成功吗？

　　（注意：玩具组合的数量可以是1或者2或者3 ）

　　【输入】

　　输入的第一行一个整数N(1 ≤N ≤ 100000),表示玩具的数量。

　　50%的数据中N≤ 2000

　　接下来的N行，每行包含一个整数Ci(1 ≤Ci≤ 100000), 表示每个玩具的价格

　　【输出】

　　一个数，表示最终要为这些玩具付出的最小价格

　　【样例输入1】

　　4

　　3

　　2

　　3

　　2

　　【样例输出1】

　　8

　　【样例输入2】

　　6

　　6

　　4

　　5

　　5

　　5

　　5

　　【样例输出2】

　　21

　　【样例 1 解释】

　　分组（3,2,2）（3）

　　【样例 2 解释】

　　分组（6,4,5）（5,5,5）

　　贪心加桶排

　　从大到小，线性扫描，如果余数是1或者2 则 累加

　　最后一个陷阱 累加器要int64 或者 long long 类型。

　　3.炸僵尸

　　（boom.pas/c/cpp）

　　【问题描述】

　　妈妈得知小星星成功地解决了买玩具难题，奖励他去看电影《生化危机 6》，小星星看

　　着看着就替女主角担心起来了，因为她要对付那么多的僵尸怪物，小星星恨不得扔颗炸弹消

　　除可恶的僵尸们，他脑袋里开始构思出这样的场景：

　　在一个 N 行 M 列单元格构成的地图中，去放置一个炸弹，这种炸弹威力巨大，以放置

　　点为中心进行行列延伸炸到同行同列的僵尸，但不能穿墙。上图中可以把炸弹放置在第 3

　　行第 4 列，最多可以炸到 4 个僵尸，如果对地图稍加改动（如下图），在第 5 行第 4 列处加

　　入一个墙体，又如何呢？答案还是最多炸到 4 个僵尸，只不过最佳炸弹放置点发生了变化，

　　应该放到第 6 行第 6 列的位置。

　　宁波市第 32 届中小学生程序设计竞赛复赛试题小学组

　　第 5 页 共 7 页

　　当然炸弹要靠勇敢的小星星去放，他只能在地图中朝上下左右四个方向行进（不能斜对

　　角移动），他不能穿墙，也不能穿越僵尸，要保证他的安全，如下图，告诉你小星星起始位

　　置是第 2 行第 2 列，那么他的最佳放置炸弹位置应该是第 3 行第 2 列，最多炸到 2 个僵尸。

　　现在请聪明的你也一起加入到消除僵尸的队伍来。

　　【输入】

　　第一行四个用空格隔开的正整数表示 N,M,X,Y，分别表示 N 行 M 列的地图，小星星起

　　始位置第 X 行，第 Y 列。

　　接下来 N 行 M 列用来描述地图上每个单元格，‘G’表示僵尸，‘#’表示墙体，只有‘.’

　　表示的单元格才是小星星能够正常行走，能够放置炸弹的单元格。（数据保证四面都是墙体，

　　也就是第 1 行、第 N 行、第 1 列、第 M 列肯定都是墙体）。

　　【输出】

　　一个整数，最多能炸掉的僵尸数量。

　　【样例输入】

　　13 13 4 2

　　#############

　　###..GG#GGG.#

　　###.#G#G#G#G#

　　#.......#..G#

　　#G#.###.#G#G#

　　#GG.GGG.#.GG#

　　#G#.#G#.#.#.#

　　##G...G.....#

　　#G#.#G###.#G#

　　#...G#GGG.GG#

　　#G#.#G#G#.#G#

　　#GG.GGG#G.GG#

　　#############

　　【样例输出】 宁波市第 32 届中小学生程序设计竞赛复赛试题小学组

　　第 6 页 共 7 页

　　10

　　【数据范围】

　　30%的数据，保证 N,M<14，并且小星星一定能够抵达最佳炸弹放置点

　　40%的数据，保证 N,M<14

　　70%的数据，保证 N,M<101

　　100%的数据，保证 N,M<2001

　　100%的数据，保证 X<N

　　100%的数据，保证 Y<M

　　宽搜加预处理 深搜用灌水法2000的数据否则是要超时的。宽搜做个小小变形。在宽搜的时候每次记录当前点位的最大僵尸值，因为有可能最后走不到那个最多僵尸的点位。预处理要处理每个点位能够炸到的最大僵尸值。

　　4.梦里的难题

　　(dream.pas/c/cpp)

　　【问题描述】?

　　生化危机血腥暴力的场面对小星星的冲击很大，晚上频繁地做起了梦，梦里他担负起拯

　　救世人消灭僵尸的重任，眼看就能拿到消除 T 病毒的解药还世界清静，但 T病毒人工智能

　　电脑挡住了星星的去路，它声称研制出 T 病毒的目的是因为察觉人类智力退化，只有聪明

　　的人才能存活下来，如果想要拿到解药，必须回答出下面这个难题：

　　有 N(1≤N≤100000)个数字（由 1 到 K 组成，1≤K≤10000），排成一列形成数字串，例如

　　1,5,3,2,5,1,3,4,4,2,5,1,2,3 它包含了很多的子序列，比如(5)、(1,3,2)、(1,5,3)、(3,4,1,3)，请思

　　考该列数字串不包含的最短的由1 到 K 组成的的子序列长度是多少？

　　【输入】

　　第一行输入两个整数 N 和 K，接下来 N 行分别输入这 N 个数字

　　【输出】

　　一个整数表示原数字串中不包含的最短子序列长度

　　【样例输入】

　　14 5

　　1

　　5

　　3

　　2

　　5

　　1

　　3

　　4

　　4

　　2

　　5

　　1

　　2

　　3

　　【样例输出】

　　3

　　【样例解释】 宁波市第 32 届中小学生程序设计竞赛复赛试题小学组

　　第 7 页 共 7 页

　　所有的长度为 1 和为 2 的子序列都存在。

　　长度为 1 的子序列有：（1）、（2）、（3）、（4）、（5）

　　长度为 2 的子序列有：（1,1）、（1,2）、（1,3）、（1,4）、（1,5）、（2,1）、（2,2）、（2,3）、（2,4）、（2,5）、

　　（3,1）、（3,2）、（3,3）、（3,4）、（3,5）、（4,1）、（4,2）、（4,3）、（4,4）、（4,5）、（5,1）、（5,2）、

　　（5,3）、（5,4）、（5,5）

　　长度为 3 的序列不全都有，例如：(2,2,4)

　　桶记数，加线性扫描。要生成高1位的长度，那么就要保证k个数字都要出现过。例如要生成2位长度，则至少要在输入数据中查找到有2个k位数字都出现的循环节。举个例子 k=3

　　2 13 1 1 2 3 1 2他只能生成连续的长度2为2个长度，因为1 2 3 11 12 13 21 22 23 31 32 33 111 112 113 121122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323331 332 独缺333. 原因是蓝3 淡蓝3后面没有需要的第三个 紫3。