NOIP2017普及组 解题报告(成绩|图书管理员|棋盘|跳房子)

感觉今年试卷比去年简单,不过数据比去年强(似乎一群dalao因为某题一个小小的失误而350)。

NOIP2017 Junior

T1.成绩(score.cpp/c/pas)

大水题,不多说。

T2.图书管理员(librarian.cpp/c/pas)

大水题,不多说。

T3.棋盘(chess.cpp/c/pas)

这题不难看出其实就是最短路。那么就很容易想到两种方法:SPFA或者DP。

解法一:SPFA

SPFA的算法不难想到,也就是从起点走到终点,判断几种情况:
①当前格子是无色的(即上次使用了魔法):如果下个格子有颜色就走,否则就没法走;
②下一格子与这个格子颜色相同:直接走过去,不花费金币;
③下个格子颜色不同并且有颜色:金币+1;
④下个格子没颜色:直接走过去(因为在处理这个点的时候会判断到)。
简单判断下这四种情况就可以了~~

解法二:动态规划

DP的算法也并不难理解。就是有点类似过河卒。麻烦就在这题上下左右都可以走。过河卒那题只能向右向下,所以直接根据左边、上面推出当前状态就可以,但是这题就需要从四个方向推过来。那么这样DP是有后效性的,所以我们需要刷4趟:从坐上到右下,从右下到左上,从左上到右下,从右下到左上……就行了。

T3.房子(jump.cpp/c/pas)

二分+DP+单调队列优化。

“现在小 R 希望获得至少 k 分,请问他至少要花多少金币来改造他的机器人。”显然,最大当中求最小,二分。因为题目里g不知道,二分肯定是枚举g(即改造花费的金币,也就是在d的基础上步数允许的变化量),枚举出来g以后很容易想到一个O(N²)的DP:F[i]表示跳到第i个格子获得的最大金币数量。但是数据范围是:1 ≤ n ≤ 500000, O(N²)显然要超时……我们可以发现这个F数组是单调递增的,所以我们可以用单调栈优化:维护一个单调降的队列(这里命名为数组que,存一个DP状态(就是F[x]的值)和位置),每次只要先修正队列头(就是如果队列头指向的格子跳不到当前的,就head++,直到队列头满足或者全删光了),取队列头修正当前状态F[i],再从队列尾把没有F[i]优秀的全删掉,再把F[i]入队。每次都这么维护下就好了,答案就是Max(F[1~n])。

本来这么简单的试卷并不想写解题报告……但是由于闲着实在没东西写,所以……

本文采用 BY-NC-SA 4.0 协议,欢迎转载。如有错误欢迎指出。
本文链接: https://skywt.cn/posts/noip2017pj/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。