NOIP2017普及组复赛-解题报告

衢州市兴华中学NOIP2017普及组复赛By冯明浩第1页/共3页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)期望得分：100librarian图书管理员题目大意给出N个数Ai，再进行Q次询问，找后缀为给定数Bi的最小的Ai考察算法模拟算法一将Ai及Bi都转化成字符串。每次询问都对N个数进行后缀比较，挑出个最小的时间复杂度：O(N*Q*len)期望得分：80算法二对算法一的比较进行优化——构造出n10，对于Ai，直接AiMod10len，判断是否相等。这样每次比较的时间复杂度优至O(1)同时先将Ai排序，再每次从小到大查询，一旦找到就停时间复杂度：小于O(N*Q)（一般情况）期望得分：100算法三读入Ai时进行处理，构造ans[x]数组，记录询问X的最小值。对于每个Ai，依次取出其后1、2、3……len位，修正其的最小值。这样每次查询，就可以O（1）出结果了时间复杂度：O(N*len)空间复杂度：O(max(Bi))期望得分：100Chess棋盘题目大意给出一个N*N的矩阵，其中部分格有颜色每次可以从一个格向上下左右四个方向移动一格（不能越出矩阵且满足条件），根据两个格子的颜色有不同的代价求从左上角走至右下角的最小代价考察算法最短路（动态规划）算法一直接暴力地按照题意进行DFS时间复杂度：O(nn*2)期望得分：30算法二以左上角为起点，右下角为终点，刷四个方向的SPFA衢州市兴华中学NOIP2017普及组复赛By冯明浩第2页/共3页（也可预先对相邻格建好边，刷最短路SPFA或DIJ或进行记忆化DFS）时间复杂度：O(k*n*n)期望得分：100Jump跳房子题目大意给出N个格子的位置Xi与价值Pi，从起点0往右跳跃，初始跳跃的距离只能为d同时可以花费金币来调整其跳跃距离，花了t个金币时可跳跃的距离为max(1,d-t)~(d+k)每遍历一个格子就会获得其代价Pi，求要获得总价值为K所需最少的金币数考察算法二分、动态规划、单调序列（堆）算法一从小到大枚举所需金币数，用O(N*N)的DP进行check，一旦发现可行就为答案时间复杂度：O(max(Ai)*N*N)期望得分：20算法二分析发现，枚举的金币数越多，跳跃范围越大，总价值一定越多——满足二分答案的单调性，于是将算法一的枚举答案变为二分枚举时间复杂度：O()max(2logXi*N*N)期望得分：50算法三分析一下DP的转移方程：F[i]=max(F[j])+P[i](max(1,d-t)≤a[i]-a[j]≤d+k)就会发现DP的j这次循环是为了找F[1~i-1]中的最大值，自然而然就想到了用堆优化——堆中存放F[1~i-1]，若堆顶距当前X[i]大于d+k，就丢掉该元素（再也没用）否则若堆顶距当前X[i]小于max(1,d-t)，就暂存在临时数组中，最后在当前解更新好后记得塞回去则F[i]=F[heap[1]]+P[i]时间复杂度：O()max(2logXi*N*k*N2log)期望得分：80算法四继续优化算法三的DP：那些离当前X[i]太近的实际上完全没有必要塞入堆中，那么再另开一个变量j记录当前往堆中塞入的最后一个元素。每次将与当前X[i]的距离大于等于max(1,d-t)的塞入堆中，只要检查一下堆顶是否太远即可，就保证了每个节点当且仅当入堆一次，时间复杂度中k就消去了时间复杂度：O()max(2logXi*N*N2log)期望得分：100算法五在算法四的基础上再思考一下，其实也没有必要用堆了。因为X[i]是在不断增大，那么对于F[x]=F[y]，显然距离起点远的更有用，即一旦F[y]进堆，F[x]就没有存在的意义了（X[x]X[y]）；若远的更大，则更不必说；小的话，就要暂留着，以备做前后的“中转站”。这样的话，维护一个单调下降的单调序列来代替堆，每次将序列前面距离太远的干掉，后面再如上进行维护，每次抓序列的头就是前面的最优解：F[i]=F[que[hed]]+P[i]于是连堆的N2log也成功去掉了衢州市兴华中学NOIP2017普及组复赛By冯明浩第3页/共3页时间复杂度：O()max(2logXi*N)期望得分：100另：除了上面的算法外，不排除还有其他更优的解法。