目前应该是打算要先VP以下上一年的区域赛。
暂时就只VP了一场杭州，题目几乎全是队友想得思路，我几乎0作用，随手记录一下题目。

场上出题

M

签到题，很显然，要删的话肯定是要把一边全删完。然后就没了。

J

交互题

这一题在今年的不知道是浙江省赛还是武汉邀请赛的时候热身赛打过一次了，所以看到了队友就直接出了。

大致就是判断图是否是菊花比较简单，因为菊花图的，就代表着存在那么一个点连接着其他所有点，而其他点之间是没有边的。

那么我们只要想办法找到图中一条存在的边，再看看这条边连接的两个点中是否有一个与超过2个点有边即可。

然后多画几下，可以发现，对于$(1,2)(3,4)…(n-1,n)$这样子查询的话，如果是菊花图，一定能查到一条边。（因为菊花图有一个点与其他点都有边）。然后就很简单了。

D

构造题，队友ov_vo秒出。

可以发现上面的式子是加法连接的，下面的式子是乘法连接的。

乘法一直乘不是0也不是1的值的话会变得很大，这样的话上面的式子和下面就不可能相等了。

题目又说不能等于0,所以我们想办法让下面的式子括号里的乘法值为1（随便构造相邻两项和为1即可），然后就可以解方程把$a_1,a_n$求出来了，构造就结束了。

G

图论（最短路）

这一题一样也是队友ov_vo 一眼出。

注意到题目有一个缩身体的操作，也就是说当蛇头在$x$点想要往身体在的地方$y$走的时候，蛇头可以选择在$x$等待一段时间（进行蛇身的缩短操作），再往$y$走。这样子到达$y$点时的路径一定是最短的。

那就直接结束了。用dij求最短路即可，开一个$g$二维数组，存一下每个点什么时候开始才能走（如果是障碍，设成无限大即可，如果是蛇身，则是它到蛇尾的距离），然后走dij求最短路的时候，将点放入队列的时候，到这个点的最短路长度与$g$取$max$即可。

上面求$g$的过程，我们只需要考虑刚开始时图里的蛇身部位即可。因为如果一个点刚开始不是蛇身的话，我们在到达这个点的时候，如果蛇身又在这个点了，很显然这个点就已经被到达过了，那我们就没必要再进行操作了。

所以就这么结束了。

H

求期望（我感觉就是一点点组合数学加上记忆化搜索就可以了）

我们假设该事件发生的概率为$P$

随便讨论一下可以发现
$$a_{i}=a_{b_{i}}+w_{b_{i}}时P_{i}=0$$
那么我们就只需要考虑$a_{b_{i}} \leq a_i < a_{b_{i}}+w_{b_{i}}$的情况就可以了。

可以发现，对于$i$而言，只有当$i$排在$b_{i}$前才有成功的可能，所以，
$$i成功的概率=i在b_{i}前并且b_{i}成功的概率$$

同时呢，如果把上面的条件看成一条边的话，就可以构造出一颗基环树出来。

然后可以发现，计算上面的概率的过程是可以不断的往下递归的，并且未知的部分最后一定不会形成环。（很显然的，因为这是通过小于号连接的）。递归的过程中要注意这个顺序的要求是要对于几个点同时满足的，也就是这个点到最后一个未知点的中间的几个点的顺序要求是固定的。

例如：
假如有五个数，然后在树上未知的点构成的边是这样。
$$2 \rightarrow 4 \rightarrow 3 \rightarrow 1$$
那么2431这几个数的顺序就是固定的，也就是说2成功的概率就是$\frac{1}{4!} \times P_{1}$。

然后这题就结束了。

E

场上没写出来。

我用了单调栈和二分

这一题感觉写起来很麻烦，VP的时候感觉F题没什么思路。后来看看感觉还是F题简单一点（虽然我应该不看题解还是想不出来思路。）

注意到如果$S_1$已经定好，那么实际上，就已经可以把所有的字符串都处理出来了。

那么就是怎么把$S_1$构造好。

注意到$S_{i-1}$是$S_{i}$的周期，随便画几下就可以发现，$S_{i}$会限制$S_{i-1}$的前多少位必须存在数量为多少的什么字母。

然后这个信息是可以不断往上传递的。如果上一个长度比现在的限制的长度要长，那么限制就没改变（合不合法可以最后再判断）。如果上一个长度比现在的限制短，就执行一边上面的操作。

可以发现限制的长度改变最多只会改变$log_2(|S|)$次，因为每一次长度都是取模，而每一次取模最多剩下一半，所以最多只会改$log_2(|S|)$次。那么就可以把每一个字符串的限制都传到第一个。过程就是可以开个类似单调栈，然后在上面二分就可以了。

然后就结束了。时间复杂度$O(nlog|S|(log n+26))$

场后感觉能补的题

A

纯纯的模拟

F

注意到mex是可以二分求的。至于怎么二分，我们可以预处理出$1$到$n$的前缀形成的直径的两个端点。那我们只需要二分后询问直径的两个端点到该点的距离即可。

K