20联赛集训day6 题解
A对点权取 $\ln$ 变成加法就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_b...
A对点权取 $\ln$ 变成加法就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_b...
A考虑对串的反串建后缀树，答案就是叶子节点个数。注意到这时的叶子节点一定是一段前缀，如果一个前缀 $s[1\ldots i]$ 是叶子节点当且仅当它不属于任何一个点的 border 集合，所以问题变成了求每个前缀的 border 集合的并的大小，用 kmp 解决即可。这里发现一个结论：每个前缀的 border 集合的并的大小等于 $\max{fail_i}$。证明要考虑这个命题等价于叶子节点...
A考虑 dp。设 $f_{i,0/1}$ 表示考虑到根是 $i$ 前缀，最后一次删除的串长度为 $2/3$ 的方案数。转移就判断一下两次长度相等是否子串相等即可。B这种最长的最短路链问题贪心超过两步都是错的。首先 $O(n^2)$ 预处理 $dis_{i,j}$ 表示 $i \to j$ 的最短路，注意到贪心一步是正确的，我们去枚举 $b,c$，预处理最远，次远，第三远的点即可（因为路径不...
题目链接题目描述题目大意：给你前 $alphabet$ 个小写字母组成的字符集，以及 $n$ 个单词，定义一个串 s 的禁忌值为 $\sum_{i} [s[i] == Taboo[i]]$，其中 $Taboo[i]$ 是第 $i$ 个单词（禁忌值也就是找到一种分割字符串的方法 使得出现这N个字符串的次数最多的次数）。现在给定一个长度 $len$，求随机一个用字符集生成的长度为 $len$ 的...
定义首先简要介绍一下 AC 自动机：Aho-Corasick automation，该算法在 1975 年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是给出 n 个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。要搞懂 AC 自动机，先得有模式树（字典树）Trie 和 KMP 模式匹配算法的基础知识。KMP 算法是单模式串的字符匹配算法，AC自动机是多...