wjyppm's Blog

怎么没有 SAM 版本的，我来补一发 www。 SAM 直接找回文串不太好找，考虑用 Manacher 找回文串，一旦有回文串我们就去 SAM 上查询。闲杂问题转化为查询 S[l,r]S[l,r]S[l,r] 在原串中出现多少次。首先我们得找到 s[l,r]s[l,r]s[l,r] 在 SAM 上对应的节点，这个问题是经典技巧，首先我们预处理 sss 每一个位置 sis_{i}si​ 对应的 SAM 节点，记为 posipos_{i}posi​，让后我们每一次查询 S[l,r]S[l,r]S[l,r] 从 posrpos_rposr​ 开始在 Link 树往上跳，直到跳到第一个位置 kkk 使得 lenk<r−l+1len_{k}< r-l+1lenk​<r−l+1，此时 kkk 代表的就是 s[l,r]s[l,r]s[l,r] 对应的节点。 我们得到节点了，还有一个问题出现多少次，我们在 SAM 插入字符的时候维护一个 cntcntcnt 表示当前节点是否是子串节点，让后在 Link 树上从下往上合并（加），让后答案就是 cntk×(r−l+1)cnt_{k}...

形式化题面如下： 多组测试数据 TTT，给出一个字符串 sss，求多少个相距为 ggg 的子串是相同的。 1≤T≤10,1≤g≤10,1≤s≤5×1041\le T \le 10,1\le g \le 10,1\le s \le 5\times 10^41≤T≤10,1≤g≤10,1≤s≤5×104 看到子串，并且要 O(nlog⁡n)O(n \log n)O(nlogn)，首先想到的就是 SA 和 SAM。 让后如果你做过 P1117 [NOI2016] 优秀的拆分的话，你会发现这个题和那个题很相似，都是在统计子串，不过这里有了距离限制。 我们考虑枚举子串长度 LLL，设第一段起始点为 lll，那么第一段范围为 [l,l+L−1][l,l+L-1][l,l+L−1]。第二段起始点 rrr 就是 r=l+L+gr=l+L+gr=l+L+g，同理 [r,r+L−1][r,r+L-1][r,r+L−1]。那么它们什么时候才能够作为子串相同呢，这里有一个结论就是它们两端的 LCS（最长公共后缀） 与 LCP（最长公共前缀）的长度和（注意算重两个端点要减一）大于等于我们枚举的长度，也...

可能更洛谷的阅读体验 0. 前言 后缀数组是信息学竞赛中解决字符串匹配的一大利器，其思想和实现非常简单。虽然倍增加排序的思想很简单，但是它的拓展 hththt 数组功能及其强大并且适用性广，在 OI 范围内广泛应用。 以下应用魏老师的一句话： 几乎所有字符串算法都存在一个共性：基于所求信息的特殊性质与已经求出的信息，使用增量法与势能分析求得所有信息。这体现了动态规划思想。—— Alex_Wei 希望读者也能好好利用这句话来理解字符串算法。 本文章包含后缀数组入门，以及应用，以及技巧及其好题选讲大礼包！ 但是作为本蒟蒻第一个写的算法全家桶，为了考虑到读者感受，写了一大堆没用的废话导致文章及其的长 ( •́ὤ•̀)，本文章共 2.1 万字，感谢管理员付出时间来进行审核。 一些基本约定： 本文章默认字符串下表从 111 开始。 我们用打字机字体表示字符串的内容，如：s=wjyppm1403s=\texttt{wjyppm1403}s=wjyppm1403。 拼接：s+ts+ts+t 表示将 ttt 拼接 sss 后。 字符集：即构成字符串中字符的集合。 空串：不含任何字符的字符...

可能更洛谷的阅读体验 题目很好，考察了 SA 中的并查集思想以及启发式合并，而且实现也不难，值得一做。 形式化题面如下： 给定一个长为 nnn 的字符串，询问次数为 qqq，多次询问区间 [l,r][l,r][l,r] 内最长重复子串的长度。 1≤n≤5×104,1≤q≤1051\le n \le 5\times 10^4,1\le q \le 10^51≤n≤5×104,1≤q≤105。 没有形式化题面感觉都想不出来怎么做 www。 肯定没有那么菜啦，首先考虑二分长度，问题转化为区间内是否存在一个长为 midmidmid 的最长重复子串。 接下来我们考虑这个最长重复子串怎么求，一个比较明显的想法就是后缀数组的 LCP 功能，原命题询问的实质就是是否存在 i,j∈[l,r−mid+1],LCP⁡(i,j)≥midi,j \in [l,r-mid+1],\operatorname{LCP}(i,j)\ge midi,j∈[l,r−mid+1],LCP(i,j)≥mid。看到后面这个式子，回忆起品酒大会的思路：从大到小将 Height 数组插入，若仅考虑 ≥L\ge L≥L 的 ...

0. 前言 记录做题中遇见的一些好玩的科技。 1. 含通用符的字符串匹配问题 在没有通用符的字符串匹配问题中，我们一般使用 O(n+m)O(n+m)O(n+m) 的 KMP，多模匹配下我们会考虑 AC 自动机。但是，我们还有令玩意中做法： 设 P(x)=∑i=0m−1(Ai−Bx+i)P(x)=\sum\limits_{i=0}^{m-1} (A_{i}-B_{x+i})P(x)=i=0∑m−1​(Ai​−Bx+i​)。 但是 Ai−Bx+iA_{i}-B_{x+i}Ai​−Bx+i​ 是没有正负性这一说的，所以我们要将其平方，有： P(x)=∑i=0m−1(Ai−Bx+i)2=∑i=0m−1(Ai2−2AiBx+i+Bx+i2)\begin{aligned} P(x) & =\sum\limits_{i=0}^{m-1} (A_{i}-B_{x+i})^2 \\ & =\sum\limits_{i=0}^{m-1} (A_{i}^2-2A_{i}B_{x+i}+B_{x+i}^2) \end{aligned} P(x)​=i=0∑m−1​(Ai​−Bx+i​...

0. 前言 你需要知道的芝士： AC 自动机基础； Trie 树； 这里是进阶使用，所以会结合一些例题来讲解，读者应有 AC 自动机的基础芝士即可。 1. 自动机与 AC 自动机本质 考虑到大多数都是先学 AC 自动机，而很久以后才学自动机，这里有必要先给出概念，这样才能更好的理解后面的芝士。 1.1 自动机 自动机，在 OI 中一般我们涉及的是有限状态自动机，它拥有有限数量的状态，每个状态代表不同的意义，每个状态可以通过输入自动机，让自动机切换到其他的状态。任意时刻状态机只能处在一个状态。 而有限状态机可以表示为一个有向图： 从图中看出来一个信息学竞赛一共包含 5 个状态：学信竟，学 whk，吃吃饭，睡睡觉，摸摸鱼。每种带有箭头的连线，表示可以从当前状态切换到其他的状态，以及切换的条件。 我们列个表格： 学信竟 学 whk 吃吃饭 睡睡觉 摸摸鱼 学信竟 去机房 摆烂时间到 学 whk 信竟时间到 回去午睡 吃吃饭 去食堂 去教室 睡睡觉 回教室 被吵醒 摸摸鱼 回家 表格中左侧第一列为当前状态。...

1. 定义 和哈希，又称集合哈希。 为什么叫集合哈希呢，集合与序列的不同点在于，集合是无序的，也就是说，序列要求每个位置一一相等，而集合只需要对应的元素出现次数相等即可。 我们引入一个问题： 给定一个长为 nnn 的序列 AAA，每次给出两个长度相等的区间 [l1,r1],[l2,r2][l_{1},r_{1}],[l_{2},r_{2}][l1​,r1​],[l2​,r2​] 里面的数排序后是否完全相等，我们就可以说 [2,3,1,4,5][2,3,1,4,5][2,3,1,4,5] 和 [5,4,3,2,1][5,4,3,2,1][5,4,3,2,1] 是相同的。 这种情况我们很难找到一个数据结构来支持这样的查询操作，我们发现如果称两个区间相同，那么这个区间里的每一个数的出现次数和另外一个区间中这个数的出现次数相同。 我们考虑，只需要次数相同就可以的话，那么也就是说，这哈希值之和我数值具体是多少，而和位置无关，那么两个区间相等的必要条件就是 h(l1,r1)=h(l2,r2)h(l_{1},r_{1})=h(l_{2},r_{2})h(l1​,r1​)=h(l2​,r2...

我不是来刷字符串的吗怎么给我干到这里来了 Trie 树神仙题。 形式化题意可以看其他题解的。 首先这个字典树的边权没有任何卵用，因为题目中已经给出边上的 did_{i}di​ 了。 其次这个题一眼最短时间，说人话就是最短路，考虑 Dijkstra 求最短路，因为这里 SPFA 显然已死（你真的要卡 O(nm)O(nm)O(nm)？）。问题转化为如何取去建图，根据题意，通过一条边的边权是如下构成的： w(u,v)=c(u,v)+LCP⁡(dnow,di)w_{(u,v)} = c_{(u,v)} + \operatorname{LCP}(d_{now}, d_{i}) w(u,v)​=c(u,v)​+LCP(dnow​,di​) 不难注意到题目中慷慨的给我们了字典树，根据字典树上的性质，任意两个点之间的 LCA 节点的深度大小就是这两点的所构成字符串的最长公共前缀长度，那么边权转化为： w(u,v)=c(u,v)+dep{LCA⁡(dnow,di}w_{(u,v)} = c_{(u,v)} + dep\left\{\operatorname{LCA}(d_{now}, d_{i}\...

可能更洛谷的阅读体验 2025.6.27 花了一上午增添了新内容，翻新了威佐夫博弈证明。大幅更新了自己理解下的 SG 函数，添加了自己 yy 的 trick。 0. 前言 对于在信息学竞赛中的博弈论，我们研究的是组合博弈问题。在实际考察中会结合其他知识点考察，例如动态规划或者贪心等，建立模型来解决问题。 本文建议读者看到模型后可以停下来思考思考，让后再看证明。 说半家桶是因为内容还不全，不能作为 OI 中的全家桶，但是足以应付一部分问题了。 而对于例题讲解来说，我更喜欢的方式就是在许多不同的题目中总结模型出来，并且会结合之前的知识点来进行讲解，所以建议是都研读 www。 有谁注意到标题其实有一个回文串了。 1. 组合博弈与博弈基础 对于组合博弈，我们用两种类型：公平组合游戏和非公平组合游戏来区别，定义如下： 1.1 公平组合与非公平组合 公平组合游戏： 由两名玩家交替行动； 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关； 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。 例如取数游戏，...

本题就是大名鼎鼎的最优比率环的问题。 我们不难注意到，平均值就是如下： x‾=∑cicnt\overline{x}=\frac{\sum c_i}{cnt} x=cnt∑ci​​ 其中 cntcntcnt 代表点个数，而 cic_{i}ci​ 代表权值和。 学过分数规划的想必已经秒了，没事我们一步一步推。 根据题意有： ans→∑cicnt≥x‾=∑ci≥x‾×cnt=∑ci−x‾×cnt≥0=∑(ci−x‾)≥0=∑(x‾−ci)≤0\begin{aligned} ans & \rightarrow \frac{\sum c_i}{cnt} \ge \overline{x} \\ & =\sum c_i \ge \overline{x} \times cnt \\ & =\sum c_{i} - \overline{x} \times cnt \ge 0 \\ & = \sum (c_{i} - \overline{x}) \ge 0 \\ & = \sum (\overline{x}- c_{i}) \le 0 \end{...