UOJ Logo kangzzz的博客

博客

标签
暂无

AYITOJ ROUND #1题解

2018-12-07 19:13:03 By kangzzz
难度分布:

简单题: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扫一遍即可。

代码:https://acm.ayit.edu.cn/submission/17

共 1 篇博客