原题传送门：>Here<

我们先考虑只求一个点时怎么做。

设$f_i$为$i$到叶结点的最短距离。

假设我们在处理$root$的答案。可以发现，

当$dis_{root,i}\ge f_i$时，$i$的子树只需要放一个人就可以“封锁”。

可以发现满足这个条件的点构成很多棵子树，而我们的答案就是子树的个数。

现在我们考虑怎么得到子树个数。

设$val_i=2-d_i$，其中$d_i$表示点$i$的度数。

我们可以发现，一棵子树的权值和正好等于$1$。

考虑为什么是这样。

设一棵子树中有$x$个点，那么有$x-1$条在子树内的边。所以贡献即为$2*x-2(x-1)=2$。因为我们求的是“子树”权值和，所以必有一条连出去的边。这样贡献即为$2-1=1$。

所以我们只要对于$dis_{i,j}\ge f_j$，将$ans_i$加上$2-d_j$即可。

这样复杂度是$O(n^2)$的。

考虑点分治。则对于$i$，满足条件的$j$满足$dis_i+dis_j\ge f_j$。

移项一下，得到$dis_i\ge f_j-dis_j$。后面那个东西用树状数组维护一下即可。

原题传送门：>Here< and >There<

我们首先考虑对给出的字符串建$AC$自动机。

考虑$AC$自动机上找子串的过程，我们发现一个点可以被达到当且仅当该点沿着$fail$向上走没有一个点是一个字符串的终点，且沿着$fa$向上走也没有。

我们把这些点挑出来，从$1$开始跑最长路。如果发现存在正环即必定有解，否则判断最长路是否$\ge L$。

原题传送门：>Here<

答案可以看作是

其中$\tau$表示排列$p$的逆序对个数。

我们（考后）发现这个东西等价于求一个$n*n$矩阵$M$的行列式，其中$M$满足$M_{i,j}=[j\in [l_i,r_i]]$

这个行列式显然不能直接求，我们又发现查到几个性质：

• 一个单位矩阵（只有主对角线上是$1​$，其他地方均为$0​$的矩阵，即$M_{i,j}=[i=j]​$）的行列式为$1​$；（性质1）
• 交换矩阵的两行（列），矩阵的行列式变为相反数；（性质2）
• 把矩阵的某一列(行)的各元素乘以同一数然后加到另一列(行)对应的元素上去，行列式不变。（性质3）

原题传送门：>Here<

（考场上居然没写出来。。。心态爆炸）

我们发现，对于每轮冒泡排序，

• 如果一个数前面有比它大的数，则该数向前移动一位；
• 否则该数一直往后移，直到碰到一个$\ge$该数的数。

设$w_i$为$i$前面大于$a_i$的数的个数。

我们发现对于每个数，第一种移动会进行$min(w_i,k)$次。所以对于$w_i\ge k$的点，我们知道它会移动到$i-k$。

对于其他点，他们最后的值必定是有序的，所以拖出来排序，并插入原来的空当中即可。

前言

原题传送门：>Here<

网络流神仙题。。。我服了。

建模

我们发现一对联通的接头可以看做一条从一个格子到相邻格子的路径。我们考虑按奇偶分开，奇数点连源点，偶数点连汇点。

把每个格子拆成上下左右中五个点，对于有接头的方向，从中间点到对应点连边。

接下来我们考虑如何表示旋转。

原题传送门：>Here<

首先对题意进行一些转换：

• 我们发现枚举格子肯定不可行，考虑枚举颜色；

• 直接做无标号排列也不可行，考虑先对卡牌进行编号，最后再将答案除以本质相同的排列数，即$n!\prod_{i=1}^{m}a_i!$

• 恰好$K$的魔术对也不能处理，考虑先做出$\ge K$的方案数，再容斥出答案，即$\sum_{i=K}^{n}(-1)^{i-K}\binom{i}{K}f_i$。

原题传送门：>Here<

我们发现两个前缀的$LCS$等价于这两个前缀在后缀自动机上的$LCA$的$len$。

我们可以发现字符串的一个前缀可以被后缀自动机上加入该点后的$last$表示。

在下文中，一个点的编号被定义为它代表的前缀的结束位置。对于一个在建自动机时新建的点，其编号为$0$。

这样我们可以想到一个暴力的算法：

像HH的项链一样，把询问对右端点排序。

枚举到$i$时，设$val_j$为$j$的前缀与$[1,i]$的前缀的最大$LCS$，即

考虑更新$1\cdots i-1$与$i$的答案，举个例子：

原题传送门：>Here<

考虑使用后缀自动机。

首先对主串建后缀自动机。

对于每个询问，首先倍长询问串，然后对于每个前缀找到对应的节点。

我们现在想知道每个前缀长度为`n`的后缀的出现次数，其中`n`为询问串长度。

我们发现答案就是从`x`到根的链上第一个len`\ge n`的节点的size，于是倍增即可。

现在还有一个问题，就是有一些循环同构串是相同的，我们可以用哈希判掉。

CF数据真的水，用单哈希就可以水过了

原题传送门：>Here<

（这题后缀排序以后基本就是莫队裸题了。。。）

把所有姓名串和询问串连在一起（中间要隔特殊字符）进行后缀排序。

设一个询问串的开始位置为$start_i$，长度为$length_i$，这样姓名串中满足条件的位置`j`都满足

可以发现满足条件的点都是$rank$数组上连续的一段区间，这样问题便可转化为区间查询。

考虑使用莫队，第一问可以轻松解决。

对于第二问，显然一个人被点到的次数即为这个人的姓名串出现在询问区间的次数。我们只要在一个人的姓名串进入询问区间时将这个人的答案减去当前时间戳，出询问区间时将这个人的答案加上当前时间戳即可。

原题传送门：>Here<

我的实现在有些地方可能有点复杂，但是应该是比较直观的。

首先对原图建圆方树。

设`f_i`为`i`的子树中的点到`i`的最长距离。特殊的，对于一个方点，`f_i`表示子树中的点到`fa_i`的最长距离`-1`（这样比较好处理）。

`f`值的转移是比较简单的，现在我们考虑每个点子树之间的贡献。

在圆点上时和树上一样，直接处理即可。

在方点上时有点复杂：

设方点的子节点共有`S`个，按顺序编号为`p_0,p_1,\cdots,p_S-1`。这样两个点`p_i,p_j (i>j)`之间的距离`dis(i,j)=min(i-j,S+1-(i-j))`。

可以发现，对于`j\ge i-\lfloor \frac{S+1}{2} \rfloor`，`dis(i,j)=i-j`；

对于`j < i-\lfloor \frac{S+1}{2} \rfloor`，`dis(i,j)=S+1-(i-j)`。

可以对于两种情况分别开两个树状数组，分别查询即可。（当然前一问暴力存，后一问用单调队列也珂以，但是我懒）