持续更新中……

CF504E. Misha and LCP on Tree

给出一棵 n(n\leq 3\times 10^5) 个点的树，m(m\leq 10^6) 次询问求树上两条链的 LCP 长度。

考虑和序列上的问题一样二分哈希。我们需要预处理从根到每个节点的子串和其反串的哈希值，还需要能快速求出 任意节点的 k 级祖先。后者可以长链剖分做到 O(n\log n)-O(1)。这题的数据单模哈希肯定不稳，要双模哈希，最好随机 BASE。复杂度为 O((n+m)\log n)，要注意常数。

正解是树剖转化为序列问题然后后缀数组，可是我已经快忘了 SA 板子了。。

CF505E. Mr. Kitayuta vs. Bamboos

有 n(n\leq 10^5) 棵竹子，每天可以选 k(k\leq 10) 棵竹子将其高度由 h_i 变成 \max(h_i-p,0)，这天结束后左右竹子都会长高 a_i。求 m(m\leq 5\times 10^3) 天后最高的竹子的最小高度。

看到求最大值的最小值，可以先考虑二分答案。

发现还是不很好做，于是就有了一个非常秒的操作就是 时 光 倒 流。

先把所有竹子的初始高度设为二分出来的 H。每次操作先将所有竹子高度减去 a_i，然后选 k 根竹子增高 p，使得最终所有竹子的高度不小于 h_i，且过程中没有一根竹子高度小于 0。这样做的正确性可以这样想：假设一根竹子的高度可以从 h_i 变成 h(h\leq H)，那么反过来也一定有一种方法可以把它从 H 变成 h'(h'\geq h_i)，且这两种是等价的。这样做的好处是省掉了处理负高度的问题。然后我们就可以愉快地用数据结构维护贪心了：每次选 k 个最快变得小于 0 的竹子来增高。用堆维护所有如果不增高就会最终小于 h_i 的竹子就可以了，最终判断堆是否为空。

总结一下，这种思路可以用于处理一类“每次减少 x 直到没有”的问题。类似套路的题目还有 NOI2017蔬菜。

CF506E. Mr. Kitayuta's Gift

求给定字符串 s(|s|\leq 200) 插入 n(n\leq 10^9) 个字母后形成的不同回文串数，字符集为小写字母。

这题比较神仙。题意可以转化为求长度为 |s|+n 的包含子序列 s 的回文串个数。

考虑从两边开始同时加入一个字符。先考虑 |s|+n 为偶数的情况，用区间 DP 的思想，设 f(i,j,k) 表示加了 k 个字符，|s| 的子串 [l,r] 还没有被匹配的方案数。转移分四种：

• s_i=s_j\wedge i-j\leq 1。此时再加入一个字符 s_i 会达到匹配完成状态 tar，否则只会使步数 +1。

  \begin{gathered}{c}tar(k+1)\gets f(i,j,k)\\f(i,j,k+1)\gets 25f(i,j,k)\end{gathered}

• s_i=s_j\wedge i-j>1。此时再加入一个字符 s_i 会使左右两边匹配进度都增加一个字符，否则只会使步数 +1。

  \begin{gathered}{c}f(i+1,j-1,k+1)\gets f(i,j,k)\\f(i,j,k+1)\gets 25f(i,j,k)\end{gathered}

• s_i\neq s_j。此时加入 s_i 和 s_j 分别会使左右两边匹配进度增加一个字符，否则只会使步数 +1。

  \begin{gathered}{c}f(i+1,j,k+1)\gets f(i,j,k)\\f(i,j-1,k+1)\gets f(i,j,k)\\f(i,j,k+1)\gets 24f(i,j,k)\end{gathered}
• tar。此时怎么转移都可以。 tar(k+1)\gets 26tar(k)

但这个 DP 的第三维是 10^9 级别的，我们无法承受。考虑把一层转移画成一个有限状态自动机，它的状态数是 O(|s|^2) 的。我们要求 (1,n) 到 tar 的长度为 |s|+n 的路径数，直接矩乘可以做到 O(|s|^6\log n)。但我们发现这张图去掉自环以后就是个 DAG 了，所以这些路径经过的点数是 O(|s|) 的。然后我们发现自环有 24,25,26 三种，如果两条路径上自环的数量分别相等的话，这两条路的贡献就是一样的，可以认为它们是同一类路径。26 的自环只会在所有路径的终点出现一次，可以无视。下面将带 24,25 自环的点分别称为红点和绿点。我们又发现一条路径有 a 个红点，那么这条路径上就会有恰好 \left\lfloor\dfrac{|s|-a}{2}\right\rfloor 个绿点，所以可以只枚举红点的个数。在 DAG 上可以 O(|s|^3) DP 预处理出从 (1,n) 出发到每个点经过 k 个红点的个数，也就是一类路径的总数。然后对每类路径分别矩乘可以做到 O(|s|^4\log n)。

实际上对于一条路径，它上面点的顺序其实是不重要的，我们可以把所有红点都安排在绿点前面。然后再造出来一条 |s| 个红点的链和一条 \left\lfloor\dfrac{|s|}{2}\right\rfloor 个绿点的链，然后对于 a 个红点的一类路径就从红链的第 a 个点向绿链的倒数第 \left\lfloor\dfrac{|s|-a}{2}\right\rfloor 个点连一条边权为这类路径总数的边。最后将绿链末端连到 26 自环的终点上，我们就把所有类型的路径体现在了一张 O(|s|) 规模的 DAG 上。在这张 DAG 上矩乘，就可以 O(|s|^3\log n) 得到答案了。

然而还有 |s|+n 为奇数的情况，这种情况的区别就是最后一次（第 \dfrac{|s|+n+1}{2} 次）加的字符是只能匹配到一边的，也就是最后一步不能由 (i,i+1) 这样的状态转移到终点。所以我们考虑先做指数为 \dfrac{|s|+n+1}{2} 矩乘，然后减掉不合法的状态。把原先的图终点的自环拆掉，让所有 (i,i+1) 的状态成为终点即可。直接用刚才 DAG 上 DP 的结果就可以得出每类路径的数量，以它们作为边权重新连红绿链之间的边。最后再一次指数为 \dfrac{|s|+n-1}{2} 的矩乘即可。

CF512D. Fox And Travelling

给出一张 n(n\leq 100) 个点的无向图，一个点可以被访问仅当它只有最多一个相邻节点没有被访问。对于所有 k\in[0,n]，求访问恰好 k 个节点的方案数。

发现在环上的点无论如何都是遍历不到的，因此我们可以用类似拓扑排序的方法把不在环上的点分成若干棵树。这些树中有些是无根树，有些是有根树；有根树的根是这棵树中唯一与环相邻的点。对于有根树，我们可以一次树形 DP 求出答案：f(i,j) 表示以 i 为根的子树中选 j 个的答案，树上背包即可。而对于无根树，可以发现任意一个选了 k 个点的情况，当且仅当以一个不在这 k 个点中的点为根时会被计入答案，也就是说答案会被算 s-k 次，s 是这棵树的大小。枚举每个点为根，最后除一下就可以了。

直接做是 O(n^4) 的，应该也能过。上下界优化背包可以做到 O(n^3)。

CF516D. Drazil and Morning Exercise

给出一个 n(n\leq 10^5) 个点的带边权树，令 f_v 表示离节点 v 最远的节点的节点与 v 的距离。q(n\leq 50) 次询问求 \{f_v\mid v\in S\} 极差不大于 l 的最大连通块大小 |S|。

首先由直径的性质可知，树中与任意一点距离最远的一点一定是直径的两端点之一。于是我们可以三次 DFS 把 f 数组求出来，然后拎起 f 最小的点也就是直径的带权中点，把它当作树的根。这样的一棵树满足小根堆性质，对于任意一个连通块，它的 f 最小值一定是这个连通块的根，最大值一定是它的叶子。考虑向上合并的过程，最小值会越来越小，那么就会删掉一些叶子，这是不影响连通性的。所以我们可以把这棵树上的点按 f 排成一列，从大到小双指针扫一遍，并用并查集维护连通块。删叶子时把并查集维护的连通块大小减 1 即可。

复杂度为 O(n\log n+qn\alpha(n))。然而直接在树上可并堆 / 启发式合并可以做到 O(qn\log(n)) ，也是可以过的。

这题启示我们满足堆性质的树可以考虑按权值排成一条链，然后用双指针之类的操作来处理。

CF559E. Gerald and Path

数轴上有 n(n\leq 100) 条线段，对于每条线段给出它的长度和其中一个端点，求所有线段能覆盖的最大长度。

首先对所有线段按给出的端点位置排序，然后考虑 DP。令状态 f(i,j,p) 表示处理了前 i 条线段，它们覆盖的最右边的一段由线段 j 贡献，且 j 的方向为 p（左 0 右 1）。如果正常的考虑加入一条线段转移，即由 i 转移到 i+1，应该考虑线段 i+1 的贡献。但这个贡献是不好处理的，如图：

黑色的表示已经计入贡献的线段，红色的表示新加入的线段。发现黑色中间的空隙是算不了的，所以这样会产生后效性。但是同时我们发现第二段黑色线段是没有任何用的，我们扔掉这种「没有用的线段」，加入时就只需要考虑 j 右端点后面的部分了。所以，我们从 i 转移到 k\in[i+1,n] 的所有线段，并不计线段 i+1\sim k-1 的贡献。但是注意，还是需要考虑一种贡献：

这里紫色的线段 x 超过了 k 的右端点，并成为最靠右的线段。假设 x 的方向为 y，那么 f(i,j,p) 应该转移到 f(k,x,y)，还要加上 k 后面一段的贡献。x 应该从 i+1\sim k-1 中取右端点的最大值，而从小到大顺次枚举 k 时可以直接维护。所以转移的复杂度是 O(n)，总复杂度就是 O(n^3)。

这道题还存在 O(n^2) 的做法，但我还没看懂。。

CF568E Longest Increasing Subsequence

给出一个长度为 n(n\leq 10^5) 的正整数序列 A，其中有 k(k\leq 1000) 个位置空缺。给出 m(k\leq m\leq 10^5) 个备选数字，要求在每个空缺位置填入一个备选数字，同一个数字不能重复使用。最大化最长上升子序列的长度，并输出方案。

因为要求严格递增，所以两个相同的数不会出现在同一个上升子序列中，因此我们可以暂时不考虑填数不能重复的限制。求 LIS 的长度可以常规做，考虑处理了一个前缀，记 f_i 表示长度为 i 的上升子序列的末尾元素的最小值。转移时，如果当前位置不是空缺就直接二分；如果是空缺就枚举 m 个备选数字，然后 O(n+m) 双指针扫描。为了输出方案，我们添加三个辅助数组：

• g_i 表示长度为 i 的上升子序列末尾元素取到 f_i 时它的位置；
• l_i 表示以 i 结尾的 LIS 长度；
• p_i 表示以 i 结尾的 LIS 中 i 的前一个元素。

这三个数组在转移的过程中都是可以轻易维护的。而构造方案就是要构造出一个 LIS，我们考虑从后往前做。首先我们通过 f_i 和 g_i 可以知道 LIS 最后一个元素的值和位置，然后假设已经构造到了 LIS 的第 i 个数，它在原序列中的位置是 j，它的值为 x，现在要求第 i-1 个数。如果 j 不是空缺，那么直接查 p_j 可以找到上一个位置；如果 j 是空缺那么先枚举 1\sim j-1 的所有非空位 k，如果 A_k<x 且 l_k=i-1，那么它就是上一个位置；否则找到上一个空位，二分出比 x 小的备选数即可。构造出 LIS 后剩下的空位随便填没选的数字就可以了。

CF582E. Boolean Function

有八个布尔变量 A,B,C,D,a,b,c,d，其中小写字母的值为对应大写字母取反。一个布尔表达式由上述布尔变量、& 和 | 两个运算符以及括号组成。给出一个合法的布尔表达式 s(|s|\leq 500)，其中有些位置为 ? 表示可以为任意变量或运算符。再给出 n(n\leq 16) 组 A,B,C,D 固定时 s 的取值，求补全 ? 的方案数。

发现整个表达式可以化成一棵二叉树，其中叶子节点是变量，而非叶子节点为运算符。考虑 DP，设 f(i,S) 表示节点 i 的子树代表队表达式在 A,B,C,D 的 n 种取值时的值为 S 的方案数。其中 S 是一个长度为 n 的序列，第 i 个位置表示取题目中给出的第 i 组自变量时表达式的值，那么 S 显然可以压缩成一个 n 位二进制数。对于叶子节点，初值应将 S 中该变量为真的状态设为 1；如果为 ? 则枚举所有情况相加。接下来考虑非叶子节点 i 节点的转移：

其中 \oplus 与 i 节点上的运算符相同，如果为 ? 则枚举两种情况加到一起。这个式子可以用 FWT 来快速转移，做到 O(n2^n)。所以总复杂度就是 |s|n2^n。

CF585F Digits of Number Pi

给出长度为 n(n\leq 1000) 的数字串 s 和长度为 d(d\leq 50) 的数字串 x,y，求包含一个长度至少为 \left\lfloor\dfrac{n}{2}\right\rfloor 的 s 的子串的数字串 t\in[x,y] 的个数。

这道题比较普遍的做法是对 s 所有长度为 \left\lfloor\dfrac{n}{2}\right\rfloor 的子串建立 AC 自动机，然后在上面跑数位 DP。但我首先想到的解法是下面的后缀自动机做法。

题意可以转化为求与 s 的最长公共子串长度不小于 \left\lfloor\dfrac{n}{2}\right\rfloor 的数字串个数。考虑 SAM 求 LCS 的方法，每加入一个字符往上跳 parent，直到有这个字符的出边为止，同时更新最长公共后缀长度。用数位 DP 模拟这个过程，除了当前确定了前几位、是否有上 / 下界限制这些必要的状态外，还需要记录当前串在 SAM 的哪个节点上，以及当前最长公共后缀长度。为了判断是否合法，再加一维 0/1 状态表示当前的最长公共子串是否在 \left\lfloor\dfrac{n}{2}\right\rfloor 以上。

现在考虑转移，即加入一个字符。可以尝试直接跳 parent，我交了一次居然过了，，但这样的复杂度可能没有保障。不过因为 n 比较小，可以 O(n^2) 预处理转移，所以问题也不大。总复杂度为 O(10(n^2+nd^2))。

CF587F. Duff is Mad

给出 n(n\leq 10^5) 个字符串 s_1,\cdots,s_n(m=\sum_{i=1}^{n}|s_i|\leq 10^5)，q(q\leq 10^5) 次询问 s_l,s_{l+1},\cdots,s_r 在 s_k 中的出现次数总和。

首先建出 AC 自动机。考虑每个询问都把 s_k 暴力放到自动机上跑并把经过的点打上标记，最后离线 DFS 算出每个节点 fail 树祖先的贡献。但这样标记数会过多，所以我们只把串长 \leq b 的询问暴力跑，b 是分治阈值。这样标记数量就是 O(qb) 的，DFS 的过程可以树状数组维护做到 O((n+qb)\log n) 或者分块做到 O(n\sqrt n+qb))。

接下来考虑长度 >b 的串，这些串最多有 \dfrac{m}{b} 个。对于每个这样的串，求出 s_1,\cdots,s_n 在它里面分别出现的次数（见这道题），然后前缀和处理每个询问即可。复杂度可以做到 O\left(\dfrac{m^2}{b}\right)。

关于 b 的选取，若短串使用树状数组维护，则 b=\sqrt{n\log n} 时总复杂度为 O(n\sqrt{n\log n}) 为最优；若用分块维护则 b=\sqrt{n} 时总复杂度为 O(n\sqrt{n}) 为最优（均视 n,m,q 同阶）。我选用了较好写的树状数组来维护。

CF590E. Birthday

给出 n(n\leq 750) 个只包含 a,b 的两两不同的字符串 s_1,\cdots,s_n(m=\sum_{i=1}^{n}|s_i|\leq 10^7)。你需要去掉一些字符串，使得在剩下的串中，没有一个串是另一个串的子串。使保留的串的个数尽可能多，并输出方案。

考虑建出一张图，i 到 j 有边表示 s_j 是 s_i 的子串。那么题目就是要我们构造一条这张图的最长反链。根据 Dilworth 定理和二分图有关定理，我们知道 最长反链 = 最小链覆盖 =n\;- 二分图最大匹配。然后直接跑 Dinic，构造解时在残量网络上 DFS，如果一个点的入点被访问而出点没有被访问，就说明这个串需要选。证明不会

但是总串长很大，如果直接 AC 自动机上暴力跳 fail 的话复杂度是 O(nm) 的，并过不去。然而我们发现如果 s_i 是 s_j 的子串，且 s_j 是 s_k 的子串，那么 s_i 也会是 s_k 的子串。也就是说这张图里有不少边都是没有意义的，建出去掉这些边后的图在 Floyd 传递闭包补全就可以得到原图。那么对于某个串的某个前缀，它只需要与 parent 上祖先中最近的终点状态连边即可。开个邻接表记录每个节点被哪些状态覆盖，然后从根往下搜索一遍即可。

总复杂度为 O(m+n^3)。注意 10^7 的递归内存肯定吃不消，要用 BFS。

CF594E. Cutting the Line

给出字符串 s(|s|\leq 5\times 10^6) 和一个正整数 k(k\leq |s|)，要求把 s 分为至多 k 段，每段翻转或不翻转，使得变换后 s 字典序最小。

这可能是我做过的思维难度最大的一道字符串了。。正确性需要证明的地方很多，请结合感性食用。

前置知识

• Lyndon 分解
• 最小表示法
• 扩展 KMP

符号约定

• n=|s|。
• s' 表示 s 的反串。
• s[i] 表示字符串 s 的第 i 个字符，s[:i],s[i:] 表示以 i 为端点的前缀或后缀。
• uv 表示 u 与 v 顺次拼接，s^k 表示 s 重复 k 次。

解题分以下几种情况讨论：

k=1

这种情况直接特判掉，s 与 s' 取个较小的即可。

k\geq 3

先考虑 k=n 的情况。此时相当于没有翻转次数的限制，而对于一个不翻转的段，我们可以将其分割成若干个单独字符，因为单独字符翻转是其本身，所以一定存在一个解每段都翻转。

• 引理：一个字符串最小后缀出现的位置不相交

  证明：假设最小后缀出现的位置相交，那么相交部分一定是 Border，所以它会是一个更小的后缀，矛盾。

因此我们可以每次从 s' 末尾取一个最小后缀放在当前字符串后面，这样答案肯定不会变劣。这个过程其实就是对 s' 做 Lyndon 分解，从后往前把每一段取出来。复杂度为 O(n)。

如果 k<n，我们需要保证答案与 k=n 的答案的 LCP 尽可能长。因此考虑沿用上面的贪心，同时还要节约划分次数。具体地，对于两个相邻的 Lyndon 串，有两种情况可以将其合并成一次划分：

• 两个 Lyndon 串相等。此时分别提取和同时提取这两个串都是一样的，不需要解释。
• 两个 Lyndon 串都是回文串。此时同时提取这两个串，然后翻转一次，与分别提取两个串是一样的。别忘了原问题中字符串还可以翻转。

可以证明其他情况都不能合并了，否则答案会变劣。实现其实很容易，第一种情况在做 Lyndon 分解时就可以把相同的串合并到一起，而第二种易知回文 Lyndon 串只可能是单个字符（否则最后一个字符才是最小后缀）。所以直接比一比长度就可以了，于是我们在线性时间内将问题转化为了 k=2 的问题。

k=2

设将 s' 分割后得到的两个串中后面的为 t_1，前面的为 t_2。这时的情况显然是与 k\geq 3 不同的，因为 t_1 之前不能分割了。有一种做法是枚举分割点，通过后缀数据结构来 O(1) 求任意子串 LCP。但这样实现起来非常暴力，我们考虑更优秀的做法。

对于分割出来的两个串，枚举它们翻转 / 不翻转，可以分为四种情况讨论：

1. t_1,t_2 都翻转

此时答案就是 s。

2. t_1,t_2 都不翻转

枚举分割点，答案就是 s' 的所有循环表示。而最优答案就是 s' 的最小循环表示法，这可以 O(n) 求出。

3. t_1 翻转，t_2 不翻转

从后往前枚举分割点，设 j 为之前的最优答案，i 为当前枚举的位置。

如图，红色有向线段表示之前的最优串，紫色有向线段表示当前串。我们要比较这两个串的字典序，需要询问两个绿色串间和两个蓝色串间的 LCP。随便推一下，发现绿色的 LCP 等于 \operatorname{lcp}(s[n-i+1:],s')，蓝色的 LCP 等于 \operatorname{lcp}(s',s'[j-i+1:])。发现这两部分都是关于 s' 的 LCP，所以可以令 ss=s'+s，并使用扩展 KMP 求出 ss 的 z 函数，复杂度也是线性的。

4. t_1 不翻转，t_2 翻转

设 s' 的 Lyndon 分解为 s'=a_1^{k_1}a_2^{k_2}\cdots a_m^{k_m}，满足 a_1>a_2>\cdots>a_m。记 b_i=a_i^{k_i},B_i=b_ib_{i+1}\cdots b_m。

• 定理 1：最终答案一定满足存在 i，使得 t_1=B_i。

  证明：若最优答案在 b_i 的内部，因为 b_i 由相等的 Lyndon 串组成，所以将分界线移到 b_i 前一定更优。

• 定理 2：B_i>B_{i+1}。

  证明：取 a_i 为 B_i 的第一个 Lyndon 串。假设 a_i\leq B_{i+1}，则 B_{i+1} 的每个前缀都不小于 a_i，也就是说不能划分出比 a_i 更小的 Lyndon 串了，矛盾。因此 B_i>a_{i+1}>B_{i+1}。

  由 定理 2 可知，除非 B_{i+1} 是 B_i 的前缀，否则 t_1=B_i 一定比 t_1=B_{i+1} 优。取最后一个 B_p 不是 B_{p-1} 前缀的 p，那么答案 t_1=B_i 一定满足 i\geq p。

• 定理 3：若 B_{i+1} 是 B_i 的前缀，则一定有 |b_i|< |B_{i+1}|。

  证明：假设 |b_i|\geq |B_{i+1}|，则 b_i 会在 B_{i+1} 的前缀中出现，而 b_i=a_i^k，矛盾。因此原命题得证。

  推论：|B_{i+1}|<\dfrac{1}{2}|B_i|(i\geq p)（显然）

  由推论可知 m-p=O(\log n)，因此可以枚举这些断点，然后二分哈希比较，这样就可以做到 O(\log^2 n) 的复杂度。

虽然好像做完了，但这个哈希的做法还是不够优美。我们可以继续分析性质。

假设 B_i 比 B_{i-1} 优秀，发现对于任意的 j(p\leq j\leq i-2)，因为 B_i 是 B_{i-1} 的后缀，且 B_{i-1} 又是 B_j 的后缀，所以 B_i 比 B_j 优。这里借 wucstdio 的一张图来解释，十分一目了然（j=i-2 的情况）：

于是，我们只需要找到最大的 i(i\geq p)，使得 B_i 比 B_{i-1} 优，然后令 t_1=B_i 即可得到答案。直接暴力比较相邻的 B_i 和 B_{i-1}，这样的复杂度为 O(\sum_{i=p}^{m-1}|B_i|)=O(n)，是一个完美的线性算法，并且没有用到哈希和任何高级字符串数据结构

CF611H. New Year and Forgotten Tree

有一棵 n(n\leq 2\times10^5) 个节点的数，给出它 n-1 条边的两个端点在十进制下的位数，要求复原每条边，或判断无解。

将节点编号按十进制下的位数分类，显然只有 m=\lfloor\lg n\rfloor+1 类。然后对于不同类之间连边的关系，我们注意到每一类点一定与其他类的点有边，也就是说它们之间至少构成了一棵树。而我们又希望能自由决定连边的点数尽可能多，因此可以考虑对每一类选出一个点作为“关键点”，这些关键点构成一个连通块，其它所有点各选一个关键点连边。

因为 m 很小，我们枚举这个连通块的 Prufer 序，然后判断是否可行。发现这是一个匹配的过程，对于每一条不在关键点连通块中的边，它要选一个 不在连通块里 且 类型与两端点中任意一个的相同 的点匹配。建立带权二分图，左部点是边，共 \dfrac{m(m+1)}{2} 类；右部点是节点，共 m 类。然后跑最大流配就可以了，解可以通过残量网络构造。

除了读入和输出，复杂度仅与 m 有关，大约是 O(m^{m+1})。网络流连边时注意减掉关键点连通块中的部分，然后流量等于 n-m 说明存在完美匹配。

CF613E. Puzzle Lover

给出一个 2\times n(n\leq 2000) 的小写字母矩阵 A 和长度为 m(m\leq 2000) 的模式串 s。求矩阵中有多少条路径满足：

• 起点和终点为矩阵中任意两个不同的位置；
• 只能向上下左右四个方向走，且不能多次经过同一个位置；
• 经过的字符顺次连接起来恰好是 s。

答案对 10^9+7 取模。

考虑使用 DP 处理字符串匹配问题。发现不好处理「折返」的情况，但这种情况只会出现在路径的起始和结尾部分，如图：

上图中紫色线段把红色的路径划分成了从左到右的三部分。设 f(i,j,k) 表示走到了 A_{i,j}，匹配到了 s_k 的方案数。第一部分是路径的起始部分，可以枚举这一段，使用 Hash 等方法判断它是不是 s 的前缀，如果是则把它赋到 DP 数组的初值里。第二部分不会折返，可以 DP 处理。第三部分是结尾部分，同样枚举这一段并计算贡献。当然这只是从左到右的路径的答案，反向的路径同样也会有贡献。只需要把 s 反转后用同样的方法计算即可。注意会重复统计起点和终点在同一列的情况，枚举并减掉这部分即可。

复杂度 O(n^2+nm)。有一些细节需要注意，比如没有起始部分或结尾部分的情况。

CF643F. Bears and Juice

有 n(n\leq 10^9) 只熊和若干个桶，有恰好一个桶里装酒。每天每只熊会选一些酒桶查看，如果选的桶里是酒那么这只熊就会睡觉并不会回来。通过这个信息，熊们想知道哪个桶里是酒。如果前 i 天睡觉的熊的数量不超过 p(p\leq 130)，且第 i 天至少有一只熊没有睡觉，它能根据前面的信息推算出藏酒的桶，那么就成功了，否则失败。对于所有的 i\in[1,q](q\leq 2\times 10^6)，求在确保能成功的情况下，最多可以放多少个桶。你只需输出每天的答案乘 i 模 2^{32} 后的异或和。

首先可以发现一只熊只有第一次喝某个桶的饮料是有意义的，因为如果这一桶是酒就醉了，不是的话再喝也没用，所以可以认为一只熊只会喝一桶饮料一次。我们来分析一下，熊们得到的所有「信息」就是：对于一只熊，它有没有睡觉，如果睡了是在第几天。假设有两个桶，喝它们的熊的集合都相同并且时间也相同，那么如果其中有一桶是酒，剩下的熊就无法分辨，于是会失败。我们对每个桶画一张表格，第 x 行 y 列表示第 x 天熊 y 有没有喝这一桶，那么所有桶的表格应该不同。于是答案就是不同的表格数量。这张表格有两个限制：

• 有 1 的列的数量不超过 \min\{p,n-1\}，即存在对喝这桶饮料的熊的数量限制。否则万一这桶是酒，就会失败。
• 每列最多只有一个 1。因为每只熊只能第一次喝这桶饮料一次。

枚举有 1 的列的数量 j，可以得出不同表格的数量为

组合数表示枚举有 1 的列的集合，后面的幂表示枚举每一列 1 的位置。这就是我们的答案了。枚举 i,j，复杂度为 O(pq)。

有一个小问题就是组合数的求法。这道题的模数是 2^{32}，所以不能直接求逆，但可以直接约分消质因子做到 O(p^3\log n)，或者提出质因子 2 然后欧几里得求逆做到更优的复杂度。

CF666E. Forensic Examination

给出字符串 s(|s|\leq 5\times 10^5) 和 m 个总长不超过 5\times 10^4 的字符串 t_1,\cdots,t_m。q(q\leq 5\times 10^5) 次询问，每次给出 L,R,l,r，求 s[l\cdots r] 在 t_L,t_{L+1},\cdots t_{R} 中哪个串里出现次数最多，并输出次数。如果有解输出最靠前的。

下面是一个在线做法。

对所有 t_i 建立一只广义后缀自动机。把 s 放到自动机里跑，求出 s 的每个前缀与整个 Trie 的最长公共后缀，以及它所在的节点编号。这样我们就可以倍增定位询问的子串 s[l,r] 了。然后对每个节点建一棵下标表示 t 串的编号，值表示出现次数的线段树，它可以在建立 SAM 时在表示前缀的节点打上标记，然后线段树合并得出。询问就区间查询即可。

思路不难，但我没怎么写过广义 SAM 线段树合并的板子，所以踩了一堆坑。在这里提示一下广义 SAM 和普通 SAM 的区别：

• 普通 SAM 转移数为线性（O(|s|)），而广义 SAM 的转移数则是 Trie 树大小再乘上一个字符集（O(|T|\cdot|A|)）。
• 广义 SAM 最标准的建立方式是 Trie 树 BFS，但用得比较多的是在线做法。思路是逐个插入串，但与普通 SAM 的插入方法略有不同（并不是直接把 last 设为 root）。其实就是多了两个特判，具体可以看 这篇博客。虽然该博客的做法还是可能会建出多余节点，但一般不会影响到正确性，所以我们在给出所有串的时候通常采用这种方法。
• 由于一些原因，广义 SAM 可能存在某节点与其 parent 树上父亲的 len 相等的情况。所以合并信息时不能直接基排，最好是把树建出来 DFS。

本题除了这种方法，xht 还有一篇后缀数组的题解，我觉得思路也不错，在这里写一下：

• 将 s 和 t_1,\cdots,t_m 用分隔符隔开后合并成一个字符串 s'，求出这个串的后缀数组以及 height 数组；
• 若 s[l\cdots r] 在 s' 的某个位置出现了，说明 s[l] 与这个位置的 LCP 不小于 r-l+1。这在后缀数组中体现为 sa_l 左右的 height 不小于 r-l+1 的一段区间。那么我们将 height 从大到小合并，建出 Kruskal 重构树（其实这里也就是笛卡尔树）。
• 询问时的一个区间就是一棵子树。可以倍增来定位这棵子树的根，然后就是要求子树中值在 [L,R] 内的众数。这也是可以用线段树合并来维护的。

以上两种做法其实是异曲同工的，视 n,m,q 同阶，则复杂度都在 O(n\log n) 左右。

CF671D. Roads in Yusland

给出一棵 n(n\leq 3\times 10^5) 个点以 1 为根的树，有 m(m\leq 3\times 10^5) 条路经 (x_i,y_i)，保证 y_i 是 x_i 的祖先。每条路径都有一个代价 c_i。要求选出若干条路径覆盖树上的每一条边，使总代价最小。

考虑 DP，设 f(u) 表示覆盖了子树 u 中所有边以及 u 的父边的最小代价，那么答案就是 \sum_{x\in son_1}f(x)。因为有路径都是直上直下的条件，所以对于一种覆盖的方案，除了代价只需记录「能覆盖到的最靠上的节点」。考虑钦定一条覆盖 u 的父边的路径 i，设 x_i 在 w 子树中。我们需要事先把 u 除 w 以外的子树都覆盖掉，所以这个方案的代价就是 c_i-f_w+\sum_{v\in son_u}f_v，它能覆盖的最靠上的节点是 y_i。把这两个信息存到 u 的小根堆里，转移时使用左偏树合并即可。

因为转移时总代价会变化，所以要支持左偏树上全局加法，可以用标记维护。查询根节点时，若 y_i 不足以覆盖 u，就直接把这个方案弹掉。每条路径只会对应一种方案，因此插入和删除的次数都是 O(m) 的，总复杂度为 O((n+m)\log m)。也可以用线段树合并代替可并堆，空间会多一个 \log。

这道题还有一个解法是利用线性规划的对偶性。可以证明这道题与下面的问题对偶（还不会证）：

给每条边标记一个权值，使得每条路径上的权值和不超过这条路径的权值，求树上所有边的最大总权值。

显然我们可以贪心地尽可能把权值赋给靠下的边，于是直接从下到上用可并堆维护 u 的父边最大可以被赋的权值即可。

CF698D. Limak and Shooting Points

平面上有 k(k\leq 7) 个石头发射点和 n(n\leq 1000) 个怪物，每块石头会击中它路径上第一个怪物并和这个怪物同时消失。求按某种方式打出所有石块后可能被击中的怪物数。

考虑枚举每个怪物，然后再枚举使用石头的顺序，判断这个怪物有没有可能被打到。具体地，设使用石头的顺序为 d_1,d_2,\cdots,d_k，其中表示第 i 个选用的石头的编号是 d_i。我们打算用 d_1 打掉目标怪物，但是 d_1 和目标之间可能有其他怪物，设为 x_1,x_2,\cdots,x_t。我们要达到目的，就要用其他的石头打掉这些怪物。这里钦定使用 d_2 打 x_1，d_3 打 x_2……但 d_2 和 x_1 之间可能还有别的怪物，那么继续进行下一层迭代，直到最后石头和目标之间没有别的怪物为止。不难发现这是一个 DFS 的过程，但每个石头只能打一个怪物，所以这部分的复杂度是 O(k)。再加上枚举顺序的部分，总复杂度为 O(nk!k)。

这个做法似乎可能有两个问题：

• 对于某一种使用石头的顺序，上面钦定的依次打不是最优的。

  确实可能会出现这种情况，但因为这个钦定的顺序实际上是对原顺序的一种置换，所以这时一定存在另一种顺序使得钦定的为最优。也就是说，这么枚举是补充不漏的。

• 目标的怪物成环。

  这种情况其实和上面一样，也肯定不是最优的（最优解当然每个怪物只会打一次）。换句话说，一定存在一组最优解使得目标怪物不成环。

所以这种做法的正确性得到了保障。

CF700E. Cool Slogans

给定一个字符串 S(|S|\leq 2\times 10^5)，要求构造 S 的子串 s_1,\cdots,s_k，使得 \forall i\in[2,n]，s_i 在 s_{i-1} 中出现了至少两次。求最大可能的 k 值。

这个题涉及到两个重要的结论，不是很好推。

• 一定存在一组最优解，满足 \forall i\in[2,k]，s_i 是 s_{i-1} 的后缀。

  假设 s_i 不是 s_{i-1} 的后缀。那么我们把 s_i 在 s_{i-1} 中最后一次出现位置后面的字符在 s_{i-1} 中都删掉，这样显然不会影响 s_i 在 s_{i-1} 中的匹配，而且 s_{i-1} 变短了有利于更前面的匹配，所以答案不会变劣。

• 对原串建出后缀自动机后，我们可以贪心地以一个状态中的最长子串来代表这个状态。

  感性理解一下，假设对于 right 集合里的某个位置，一个状态代表的两个子串中有一个可以与最长串匹配而另一个不能匹配，那么不能匹配的串就会出现在另一个状态里，矛盾。所以选最长子串表示这个状态是没有问题的。这个也可以当个结论记。

也就是说，一定有以组最优解可以表示成 parent 树上某个点的某些祖先节点。考虑树上 DP，设 f_i 表示考虑节点 i 的祖先的答案。f_i 应该从距 i 最近的在 i 中出现不少于两次的祖先处转移，我们可以通过倍增 + 线段树合并 right 集合判定，这样做是两个 \log 的；也可以利用决策单调性，记 g_i 表示深度最小的在 i 中出现少于两次的祖先，从父亲转移分两种情况：

• g_{fail_i} 在 i 中出现了不少于两次。此时 fail_i 也会在 i 中出现至少两次，f_i\gets f_{fail_i}+1,g_i\gets i。（这里我还没有搞清楚）
• g_{fail_i} 在 i 中出现了不到两次。此时保持和父亲相同即可，f_i\gets f_{fail_i},g_i\gets g_{fail_i}。

CF704B. Ant Man

• 有 n 个元素，第 i 个元素有五个参数 x_i,a_i,b_i,c_i,d_i。
• 你需要求出一个 1 \sim n 的排列 p，满足 p_1 = s, p_n = e，同时最小化这个排列的权值。
• 一个排列的权值为 \sum_{i=1}^{n-1} f(p_i, p_{i+1})，其中 f(i,j) 的值有两种情况：
  • 若 j < i，则 f(i,j) = |x_i - x_j| + c_i + b_j。
  • 若 j > i，则 f(i,j) = |x_i - x_j| + d_i + a_j。
• n \le 5 \times 10^3，1 \le x_i,a_i,b_i,c_i,d_i \le 10^9。

题意由 xht37 翻译。

考虑把一个点的贡献拆成左右两边，这个贡献与两边点权值的相对大小有关。我们从小到达插入每个点，那么每个点插入时的贡献是确定的，因为两边点都比它小。此外，它还会把一个点的某一侧由原来比这个点小修改成比它大。这和它插入的位置有关，而与它插入的时间无关。所以每次可以贪心找一个代价最小的位置插入，这里的代价是指答案的增量。可以暴力维护一条链表做到 O(n^2)，也可以用优先队列维护在每个位置插入的代价做到 O(n\log n)。

CF704C Black Widow

给出 m(m\leq 10^5) 个布尔变量 x_1,x_2,\cdots,x_m，令 x_{-i}=\neg x_i。再给出 n(n\leq 10^5) 个形如 x_i 或者 x_i\vee x_j 的表达式，保证每个变量在所有表达式中出现从次数不超过 2。求所有变量的 2^m 种取值中所有表达式的异或和为 1 的方案数，对 10^9+7 取模。

注意到「每个变量的出现次数不超过 2」的条件，考虑将表达式视为点，变量视为边建出一张图。那么每个点的度数都不超过 2，所以每个连通块都是孤立点、链或者环。我们要对每个连通块求出异或和为 0 和 1 的方案数 c_0,c_1，可以把这三种情况分开讨论：

• 孤立点。这个表达式 i 可以有四种形态：

  • 形如 x_i。此时 c_0=c_1=1。
  • 形如 x_i\vee x_j(i\neq j)。此时 c_0=1,c_1=3。
  • 形如 x_i\vee x_i。此时 c_0=c_1=1。
  • 形如 x_i\vee x_{-i}。此时 c_0=0,c_1=2。

• 链。因为链上的问题处理起来没有后效性，考虑 DP。设 f(i,0/1,0/1) 表示处理了这条链上前 i 个表达式，i 之前所有表达式的异或值，以及 i 前面变量的取值。转移考虑旧的异或值，以及 i-1 和 i 前的变量的取值，一共是 8 种情况，别忘了考虑下标正负的影响。

  但这并没有结束，我们还没设定起始状态和目标状态。这两者是和链首与链尾的情况相关的。具体地，链首节点有两种情况：

  • 形如 x_i\vee x_j(i\neq j)。此时链首表达式前的变量可以赋任意值，那么初始状态为 f(0,0,0)=f(0,0,1)=1。
  • 形如 x_i。此时链首表达式前没有变量，不过我们可以钦定它为 0。那么初始状态为 f(0,0,0)=1。

  对于链尾，可以同样处理。

• 环。考虑随便切开一个位置，这样环就变成了一条链。枚举切开位置变量的取值，分别钦定链首前和链尾后的变量同时为 0 或 1，然后跑两次链上 DP 即可。

最后要注意，如果一个变量在所有表达式中都没有出现，那么这个变量对答案有 \times 2 的贡献。

细节很多，实现很复杂的一道题。

CF704D. Captain America

平面上有 n(n\leq 10^5) 个点，要把每个点染成红色或蓝色，代价分别为 r,b。给出 m(m\leq 10^5) 个限制，每个限制要求在一条平行于 x 轴或 y 轴的直线上的蓝点与红点数量差的绝对值不小于 d_i。求染色的最小代价以及方案。

将行和列看成点，对于每个点，在其离散化后的横纵坐标之间连边，这样就建出了一个二分图。不妨设 r\leq b，这样尽可能多染蓝色是最优的。发现对于每一行（或每一列），蓝点的数量范围是一个与该行（列）的总点数以及 d_i 最小的限制有关的一个区间。考虑上下界网络流，源点向行、列向汇点分别连容量为这个区间范围的边，中间的边的容量设为 [0,1]，表示它对应的点选或不选。在这张图上跑有源汇上下界最大流即可。

因为二分图上的 Dinic 算法复杂度为 O(\sqrt VE)，所以总复杂度是 O(n\sqrt n +m)，可以通过。

CF708D. Incorrect Flow

给出一个 n(n\leq 100) 个点 m(m\leq 100) 条边的可能错误的网络流，即可能会出现流量不守恒或流量大于容量的情况。每次操作可以把 c 或 f 加一或减一，求使这个流正确的最小操作次数。

这道题可以转化为一个有源汇上下界最小费用可行流问题。

建图考虑原图的每一条边 (u,v,c,f)。首先连一条边 (u,v,f,f,0)，表示先让这条边上有 f 的流，然后分两种情况考虑：

• c\geq f：连边 (v,u,0,f,1),(u,v,0,c-f,1),(u,v,0,\infty,2) 分别表示减小 f、增大 f 但不超过 c，同时增大 c,f 这三种情况。
• c<f：先把答案加上 f-c，因为这是必然会产生的代价。然后连边 (v,u,0,c,1),(v,u,0,f-c,0),(u,v,0,\infty,2)，分别表示同时减小 c,f，减小 f 但不低于 c，同时增大 c,f 三种情况。

这个建图符合费用递增模型，所以它有正确性保证。然后跑板子就可以了。