NOIP2015普及组复赛试题讲解(c++版本).ppt

1、NOIP2015普及组复赛题解 NOIP2015普及组C 2 第1题 金币 简述 国王将金币作为工资 发放给忠诚的骑士 第一天骑士收到一枚金币 之后两天 第二天和第三天 每天收到两枚金币 之后三天 第四 五 六天 每天收到三枚金币 之后四天 每天收到四枚金币 以此类推 这种工资发放模式会一直延续下去 当连续N天收到N枚金币后 骑士会在之后的N 1天 每天收到N 1枚金币 请计算前K天里 骑士一共获得了多少金币 对于全部数据 1 K 10000 分析 K的规模比较少 直接用模拟 一天一天发金币 N天发N枚金币 N递增1 剩余天数K N预计时间15 25分钟 3 参考程序C includeusingnamespacestd intmain longk n 1 sum 0 cin k while n k sum n n N个金币发N天k k n 剩余天数n n 1 接下来发的金币数量和天数 sum k n 剩余不足N天的按实际天数发放cout sum return0 4 第2题 扫雷游戏 简述 扫雷游戏是一款十分经典的单机小游戏 在n行m列的雷区中有一些格子含有地雷 称之为地雷格 其他格子不

2、含地雷 称之为非地雷格 玩家翻开一个非地雷格时 该格将会出现一个数字 提示周围格子中有多少个是地雷格 游戏的目标是在不翻出任何地雷格的条件下 找出所有的非地雷格 现在给出n行m列的雷区中的地雷分布 要求计算出每个非地雷格周围的地雷格数 注 一个格子的周围格子包括其上 下 左 右 左上 左下 右上 右下八个方向上与之直接相邻的格子 5 确定解题思路 模拟题 对每个格子进行标记 如果是雷 标记为 1 并把对应八个格子中不是雷的格子的数值递增1 注意字符的读入二维数组存放数据 6 参考程序 includeusingnamespacestd intmain longd 102 102 longn m cin n m longi j charch for i 0 i ch 输入数据if ch d i j 1 用 1表示地雷longl1 l2 for l1 1 l1 1 l1 for l2 1 l2 1 l2 if d i l1 j l2 1 d i l1 j l2 边上八个位置的格子不是雷则数值加1 for i 1 i n i for j 1 j m j if d i j 1 cout else

3、cout d i j cout endl 输出return0 7 第3题 求和 简述 一条狭长的纸带被均匀划分出了n个格子 格子编号从1到n 每个格子上都染了一种颜色colori 用 1 m 当中的一个整数表示 并且写了一个数字numberi 定义一种特殊的三元组 x y z 其中x y z都代表纸带上格子的编号 这里的三元组要求满足以下两个条件 x y z都是整数 x y z y x z ycolorx colorz满足上述条件的三元组的分数规定为 x z numberx numberz 整个纸带的分数规定为所有满足条件的三元组的分数的和 这个分数可能会很大 你只要输出整个纸带的分数除以10 007所得的余数即可 8 暴力算法 预计分数40分 有点少 根据条件1 x y z都是整数 x 1 z n根据条件2colorx colorz判断是否要计算每次计算结束10007取模 9 参考程序 40分超时 includeusingnamespacestd intconstmaxn 100005 intmain inti y n m number maxn color maxn sum 0 c

4、in n m for i 1 i number i for i 1 i color i for y 1 y 1 y j n if color y j color y j sum 2 y number y j number y j sum 10007 j cout sum endl return0 10 确定解题思路 观察题意可以得知 如果第i位和第j位同色 那么就一定能够组成一个三元组 并且三元组的价值完全与中间那个数无关 那么 我们就用一个数组存储同奇偶性的同色方块 用n表示数值 i和j表示坐标 那么价值就是 ni nj i j 每组的数的下标用a1 an表示 数值用n1 nk表示 用sum表示数值之和 答案就是 n1 n2 a1 a2 如果这样做就是O n 2 m 的算法 估计能过60分 转换公式 a1 n1 a2 n2 ak nk n 2 a1 a2 ak n1 n2 nk O n 的时间复杂度 11 数据结构 SIZE 100005数组大小intcolor SIZE 格子的颜色值intnum SIZE 格子上的数值intsum 2 SIZE 相同颜色分奇偶求和intd 2 SI

5、ZE 相同颜色的数量 分奇偶统计数据输入量较多 使用scanf 12 参考程序 includeusingnamespacestd constintSIZE 100005 mod 10007 intn m intcolor SIZE intnum SIZE intsum 2 SIZE intd 2 SIZE intans 0 intmain scanf d d sum i 2 color i sum i 2 color i num i mod d i 2 color i for i 1 i n i ans ans sum i 2 color i i mod d i 2 color i 2 mod num i mod i mod mod printf d n ans return0 13 第4题 推销员 简述 阿明是一名推销员 他奉命到螺丝街推销他们公司的产品 螺丝街是一条死胡同 出口与入口是同一个 街道的一侧是围墙 另一侧是住户 螺丝街一共有N家住户 第i家住户到入口的距离为Si米 由于同一栋房子里可以有多家住户 所以可能有多家住户与入口的距离相等 阿明会从入口进入 依次向螺丝街的X家住

6、户推销产品 然后再原路走出去 阿明每走1米就会积累1点疲劳值 向第i家住户推销产品会积累Ai点疲劳值 阿明是工作狂 他想知道 对于不同的X 在不走多余的路的前提下 他最多可以积累多少点疲劳值 14 确定解题思路 每一次的最优解必然包含了上一次的最优解 也就是说只要知道这一轮的最大疲劳值就行了 而这一次的最大疲劳值也就是找最大能多消耗的疲劳值 贪心算法 分成两部分 一部分的距离小于已经到达的最远距离 另一部分大于可以到达的最远距离 15 数据结构 小于最远距离的部分 它们的疲劳增加值就是各个点的疲劳值 所以用最大堆存储 疲劳值最大的在最前 位置大于最远距离远的点的依次搜索找到最大值 距离两倍 疲劳值 与最大堆的堆顶比较 如果在左侧最大堆中 POP HEAP如果在右侧 将当前最远距离前的所有点PUSH HEAP 代码写得有点长 大家将就着看 可以复制到DEV C 中查看 16 参考程序 include include include includeusingnamespacestd intconstmaxn 100005 structdata intx s a 序号 距离 疲劳值 datadt maxn intn ans maxn lt rt now boolcmp datad1 datad2 returnd1 a sumt sumt t nowt j if sumt dt 0 a for intj rt j nowt j dt lt 1 dt j push heap dt dt lt cmp lt ans i ans i 1 sumt now nowt rt now 1 else ans i ans i 1 dt 0 a pop heap dt dt lt cmp lt else ans i ans i 1 dt 0 a pop heap dt dt lt cmp lt for inti 0 i w i cout dl i a cout endl for inti 0 i n w 1 i cout dr i a for inti 1 i n i cout ans i endl BYE TheEND 温馨提示 先理解题目在看题解

《NOIP2015普及组复赛试题讲解(c++版本).ppt》由会员自***分享，可在线阅读，更多相关《NOIP2015普及组复赛试题讲解(c++版本).ppt》请在金锄头文库上搜索。