宁波
宁波奥数网

宁波站
奥数网

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

家长帮宁波站 2017-03-28 09:59:23

  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。
 

相关推荐

点击查看更多
重点初中
首页 导航