NOIP2017普及组复赛-解题报告.pdfVIP

衢州市兴华中学 NOIP2017 普及组复赛 By 冯明浩 NOIP2017 普及组复赛-解题报告 衢州市兴华中学 By 冯明浩 Score 成绩 题目大意 给出三个整十数A,B,C，求A*20%+B*30%+C*50%的值 考察算法 模拟 算法一 直接粗暴地输出A*0.2+B*0.3+C*0.5 时间复杂度：O(1) 期望得分：100 算法二 由于分数均为整十数，先将分数各除以10，再直接输A*2+B*3+C*5。这样就避免了 精度问题 时间复杂度：O(1) 期望得分：100 librarian 图书管理员 题目大意 给出N 个数Ai，再进行Q 次询问，找后缀为给定数Bi 的最小的Ai 考察算法 模拟 算法一 将Ai 及Bi 都转化成字符串。每次询问都对N 个数进行后缀比较，挑出个最小的 时间复杂度：O(N*Q*len) 期望得分：80 算法二 n len 对算法一的比较进行优化——构造出 ，对于Ai，直接Ai Mod 10 ，判断是否 10 相等。这样每次比较的时间复杂度优至O(1) 同时先将Ai 排序，再每次从小到大查询，一旦找到就停 时间复杂度：小于O(N*Q)（一般情况）期望得分：100 算法三 读入Ai 时进行处理，构造ans[x]数组，记录询问X 的最小值。对于每个Ai，依次 取出其后1、2、3……len 位，修正其的最小值。这样每次查询，就可以O （1）出结 果了 时间复杂度：O(N*len) 空间复杂度：O(max(Bi)) 期望得分：100 Chess 棋盘 题目大意 给出一个N*N 的矩阵，其中部分格有颜色 每次可以从一个格向上下左右四个方向移动一格（不能越出矩阵且满足条件），根据 两个格子的颜色有不同的代价 求从左上角走至右下角的最小代价 考察算法 最短路（动态规划） 算法一 直接暴力地按照题意进行DFS 时间复杂度：O(2n*n ) 期望得分：30 算法二 以左上角为起点，右下角为终点，刷四个方向的SPFA 第1 页 / 共3 页 衢州市兴华中学 NOIP2017 普及组复赛 By 冯明浩 （也可预先对相邻格建好边，刷最短路SPFA 或DIJ 或进行记忆化DFS） 时间复杂度：O(k*n*n) 期望得分：100 Jump 跳房子 题目大意 给出N 个格子的位置Xi 与价值Pi，从起点0往右跳跃，初始跳跃的距离只能为d 同时可以花费金币来调整其跳跃距离，花了 t 个金币时可跳跃的距离为 max(1,d-t)~(d+k) 每遍历一个格子就会获得其代价Pi，求