NOIP2016普及组复赛试题讲解c++版本ppt课件.ppt

NOIP2016普及组复赛题解 NOIP2016普及组C 1 第1题 买铅笔 简述 P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物 她发现商店一共有3种包装的铅笔 不同包装内的铅笔数量有可能不同 价格也有可能不同 为了公平起见 P老师决定只买同一种包装的铅笔 商店不允许将铅笔的包装拆开 因此P老师可能需要购买超过n支铅笔才够给小朋友们发礼物 现在P老师想知道 在商店每种包装的数量都足够的情况下 要买够至少n支铅笔最少需要花费多少钱 分析 送分题 数据量少 直接模拟即可 当然 小心撑得万年船 大意失荆州 2 例程C includeusingnamespacestd intmain longn i s mins 100000000 n铅笔数量 i循环变量 s费用 mins最小费用longc 4 p 4 三种铅笔的数量和价格cin n for i 1 i c i p i if n c i 0 s n c i p i 正好整包elses n c i 1 p i 有多余 再来一包if mins s mins s 判断那种买法最省钱 cout mins return0 3 第2题 回文日期 简述 牛牛习惯用8位数字表示一个日期 其中 前4位代表年份 接下来2位代表月份 最后2位代表日期 显然 一个日期只有一种表示方法 而两个不同的日期的表示方法不会相同 牛牛认为 一个日期是回文的 当且仅当表示这个日期的8位数字是回文的 现在 牛牛想知道 在他指定的两个日期之间 包含这两个日期本身 有多少个真实存在的日期是回文的 一个8位数字是回文的 当且仅当从左向右读和从右向左是相同的例如 2016年11月19日 表示为20161119 它不是回文的2010年1月2日 表示为20100102 它是回文的 求 在他指定的两个日期之间包含这两个日期本身 有多少个真实存在的日期是回文的 4 确定解题思路 一年是365天 如果闰年是366天 月日构成的数字最多只有366个 第一步 构造出所有的日期 后四位 第二步 利用回文的规则 构造出相应的年份第三步 判断这个年份和日期在不在区间内例如 8月15日 日期写成0815对应回文的年份是 5180年判断51800815这一天在不在 指定的起始日期 到 指定的终止日期 之间程序时间复杂度为O 366 5 主程序 includeusingnamespacestd intmain longi j y m d t date1 date2 sum 0 i j循环变量 y对应日期 m月倒置的数值 d日倒置的数值longms 13 0 31 29 31 30 31 30 31 31 30 31 30 31 cin date1 date2 输入起始结束日期for i 1 i 12 i m i 10 10 i 10 1 12月份倒置之后的值t ms i for j 1 j t j 6 主程序 d j 10 10 j 10 1 t日倒置之后的值y d 100 m 10000 i 100 j 对应回文的日期if y date1 7 确定解题思路 解法2 如果从日期入手 一天一天往上加 每一天都要判断是不是合法的日期 是不是回文 容易出错 遇到极限数据还会超时题目里还有更重要的一点是 回文 位数是确定的 八位 很容易 组合 例如 2014 可以组成20144102我们只要判断20144102是不是合法的日期就可以了就算年份的范围是1000 9999 也只要计算9000次就可以了 8 程序框架 输入数据fori day startdiv10000 取年份 day enddiv10000 循环起始到结束年份if check i 判断i年对应的日期是否符合要求特别注意 还要判断这个日期是否在范围内 9 第3题 海港 简述 小K按照时间记录下了到达海港的每一艘船只情况 对于第i艘到达的船 他记录了这艘船到达的时间ti 单位 秒 船上的乘客数量ki 以及每名乘客的国籍x i 1 x i 2 x i k 小K统计了n艘船的信息 希望你帮忙计算出以每一艘船到达时间为止的24小时 24小时 86400秒 内所有乘船到达的乘客来自多少个不同的国家 形式化地讲 你需要计算n条信息 对于输出的第i条信息 你需要统计满足ti 86400 tp ti的船只p 在所有的x p j 中 总共有多少个不同的数输出n行 第i行输出一个整数表示第i艘船到达后的统计信息 10 暴力算法 预计分数70分 h 100001 h x 表示国籍为x的乘客到港的最新时间 初始值为 86400 sum 100001 sum 1 n 表示1 n个艘船到达海港对应的国籍数量 每一艘船到达海港 更新对应国籍乘客的到港时间数组h统计所有国籍的到港时间是否在24小时内 t为当前时间 t h x 86400 表示X国籍满足条件 时间复杂度 O kt n x 11 确定解题思路 题目明确告诉我们 要计算的是中间的一段时间的统计结果 从数据结构的角度看 是 队列 先进先出所有ki之和 300000 也就是总人数少于30万队列中记录时间和国籍 到达的入队 超过86400秒的出队 时间复杂度O kt 如何统计 总共有多少个不同的数 呢 1 Xi j 100000 当然用Hash 桶 12 数据结构 队列 用数组qt 时间 qx 国籍intqt 300005 qx 300005 头指针 head 尾指针 tailHash表 inths 100005 13 参考程序 include includeusingnamespacestd intconstmaxn 300005 intqt maxn qx maxn inths 100005 inthead 1 tail 1 n i j ti tic ki xi cnt 0 intmain memset hs 0 sizeof hs cin n for i 1 i ti ki for j 1 j ki j for j 1 j xi qt tail ti qx tail xi if hs xi 0 cnt hs xi tail tic ti 86400 while qt head tic xi qx head hs xi if hs xi 0 cnt head cout cnt endl return0 14 第4题 魔法阵 简述 大魔法师认为 当且仅当四个编号为a b c d的魔法物品满足Xa Xb Xc Xd Xb Xa 2 Xd Xc 并且Xb Xa Xc Xb 3时 这四个魔法物品形成了一个魔法阵 他称这四个魔法物品分别为这个魔法阵的A物品 B物品 C物品 D物品 现在 大魔法师想要知道 对于每个魔法物品 作为某个魔法阵的A物品出现的次数 作为B物品的次数 作为C物品的次数 和作为D物品的次数 15 确定解题思路 分析 压轴题 当然要难这题几乎是个数学题首先要会画 线段图 其次 加法原理 乘法原理 要熟练最后 是 胆大心细 编程能力 16 确定解题思路1 画 线段图 Xa6xAD AB BC CD 9xx ndiv9也就是说 CD的长度不会超过全长的九分之一 17 确定解题思路2 乘法原理 如果魔法值为A的物品有Ya个 B的有Yb个 C的有Yc个 那么 D中的一个物品作为D物品的次数是多少呢 根据乘法原理 次数 Ya Yb Yc对于A B C D的做法是一样的 18 确定解题思路3 数据范围 1 n 150001 m 40000直接求解 连O n2 的算法都不能用极限的情况下n 15000 m 40000 说明有很多数据是重复的 可以合并采用 桶 来处理 把数据范围降到n 15000加上x ndiv9 可以枚举xn n 9 15000 15000 9 2 5 107也就是说 可以采用O n2 9 的算法来做 19 数据结构 s ints 40005 存放原数据f intf 15005 桶 下标为魔法值fa fb fc fd int 15005 次数 20 参考程序 include includeusingnamespacestd intconstmaxn 40005 ints maxn f maxn fa maxn fb maxn fc maxn fd maxn intn m i j ad ac y intmain cin n m for i 1 i s i f s i for i 1 i n 9 i ad 9 i 1 y 0 for j ad 1 j n j y f j ad f j ad 2 i fd j fd j y f j i fc j i fc j i y f j ac 8 i 1 y 0 for j n 9