难度分布:
简单题:DF
中等题:BEG
难题:AC
A.VN的五杀
经分析得只有敌方周围的最多5*8个点为有效点,我们可以在这最多40个点的范围内进行搜索。
可以将这些点分为5个集合,我们先得出一个攻击序列,然后每次找一个集合中的两个点,入点和出点。
可以发现入点可以取集合中距离上一个出点最近的点,并且vn在每一个集合中停留的时间一定恰好为5。
这样我们只需要在每个集合中搜索一个出点即可。
代码:https://acm.ayit.edu.cn/submission/7
B.化简方程式
可以定义一个结构体表示含x的标准项。重定义运算符。用栈先处理出乘法运算,加法运算可以直接用一个数组记录x对应次幂下的系数,减法运算可以转化为加法。
代码:https://acm.ayit.edu.cn/submission/6
C.取数游戏
可以用dpa[i]表示当前数为i时,轮到Alice取数时,Alice最终能取到的最大值。
dpb[i]表示当前数为i时,轮到Bob取数时,Alice最终能取到的最小值。
转移方程:
dpa[i]=max( dpb[i/k]+k , max( dpb[p]+p | i-m<=p<=i-1 ) , dpb[i] ); k为i的素因子
dpb[i]=min( dpa[i/k] , min( dpa[p] | i-m<=p<=i-1 ), dpa[i]);
操作一我们可以对当前数进行分解,直接暴力枚举质因子会超时。
操作二我们可以用两个单调队列维护[i-m,i-1]区间内的最小dpa和最大dpb。
更新dpa,维护que2的时候需要考虑下标的影响,下标的影响为负。
代码:https://acm.ayit.edu.cn/submission/10
D.贪吃鱼
从后往前扫,维护最大值。
代码:https://acm.ayit.edu.cn/submission/11
E.挑战数独
可以先用错位排列构造出一个全空的数独的解(错位排列的结果可以参考maze1矩阵)。可以观察到1~9每一个数字在九宫格的每一个相对位置都恰好出现一次。那么我们就可以以九宫格为单位,对每一行九宫格或每一列九宫格进行交换。可以发现这样一定可以构造出合法解。
代码:https://acm.ayit.edu.cn/submission/15
F.亵渎
判断是否连续。
代码:https://acm.ayit.edu.cn/submission/16
G.字母
对26个字母二分最小间隔。
check时可以用vector存字母出现的位置,然后lower_bound扫一遍即可。