比赛链接

AC 9题，Rank 21th

这次还是犯了太急躁的毛病，没有想完全就直接上手了，结果发现问题重重。以后切记耐心。

以前鸽掉了$FFT$匹配字符串算法,导致C题卡在预处理上

读题水平还需要大力提升，一个模拟题怎么就能看这么久，大力贡献罚时。

题意:

有一个很大的螺旋矩阵，给出两个数值，求他们在矩阵中的坐标的曼哈顿距离。

题解:

可以先暴力枚举找到它在第几圈，然后找它在下边还是右边还是上边还是左边。

by MountVoom

也是不算很难的一道题，需要一些几何想象，但是一开始想法不完全就开打了。绕了很大弯路TAT。另外审题要仔细！没有注意到题面对于圆形的边界的描述。

其实考虑套住的圆形一个逐步放大和调整的过程，这个圆一般情况下调整过后会够到三个点（例如一般可以先缩小到触碰一个红点，再沿着这条半径反向移动圆心缩小到触碰另一个红点，再把圆心沿着红点中垂线平移，直到触碰一个蓝点，也有其他变化方法）。也就是说我们挑选不共线的三个点来做外接圆就可以了。特殊情况下，比如所有点共线的情况，可以变成以两个点为直径作圆。$n=1$特殊讨论下即可。

三点外接代码见个人页面。

题意:

给定定义一个新的真值取值$U(Uncertain)$,扩充$\land,\lor,\rightarrow,\equiv$运算符的真值表

然后每次询问给定一个二变量真值表,判断是否有*公式*满足该真值表

题解:

考虑实际公式可能有括号如$\mathscr{C}: \mathscr{A} \rightarrow \mathscr{B}$

可以利用第二数学归纳法思想进行扩展

我们得到了基础命题$\land,\lor,\rightarrow,\equiv$真值表,还需要扩展$x \rightarrow x, x \equiv x; x \land x, x \lor x$两种单变量命题

于是我们得到$\leq 1$个运算符的所有公式真值表,从而可以得到$\leq 2$所有公式真值表

一般的,有$\leq n$个运算符的所有公式,可以枚举得到$\leq 2n$的所有公式

当公式数量不再增加时即得到所有公式以及可能真值表(大概处理4次即可),再处理每次询问

by Hardict

题意:

题面描述诡异

但根据样例分析是给定$n$段$[l,r]$区间,将$[lmin,rmax]$划分成小区间,$[l,r]$可能会相同

然后需要找到一段递增的$l_{i_{1}}\leq r_{i_{1}} \leq l_{i_{2}} \leq r_{i_{3}} \leq \ldots$,使总长度最大

题解:

将区间变为$[l,r]=[l^{'},r^{'})$型,每段贡献就为$r^{'}-l^{'}$,且划分点为$r^{'}$

根据划分点$r^{'}$离散化后树状数组进行$dp$即可

by Hardict

首先将这个问题变成一个dp问题，dp值为到这一点的方案情况，如果多于1，则标记为2，否则为0或1,1的话还需要维护当前具体方案。我们观察$\le1000$间隔所组成的每一段，发现转移只能从段的最后一个元素进行，否则不可能。转移最多只有两种可能，$i-2$和$i-3$，并且要注意这连续的间隔不能$\ge 2000$才行，转移的时候，如果源头状态可能性多于1，则直接标记不用求方案，否则要求出新的方案值，为方案值去重合并，再看这一个点的dp值。

总体来说难度不大，注意思路要清晰。

by Max.D.

水题