This blog post is only available in Simplified Chinse.
感觉今年试卷比去年简单，不过数据比去年强（似乎一群dalao因为某题一个小小的失误而350）。
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])。