- 博客(70)
- 收藏
- 关注
RSS订阅原创 SAM详解3.2（关于2和3的题）
本文主要介绍了SAM（后缀自动机）在字符串处理中的应用，特别是用于解决最长公共子串问题。首先，文章通过Luogu P6640题为例，展示了如何利用SAM处理字符串匹配问题，并通过拆括号和二分优化查询效率。接着，文章讨论了CF653F题，展示了如何利用SAM和线段树结合处理本质不同的合法括号子串问题，并通过维护后缀和的方式实现高效的区间查询。文章还提供了详细的代码实现，帮助读者理解SAM的实际应用和优化技巧。
2025-05-10 15:33:41
682
原创 SAM详解3.1（关于2和3的习题）
本文介绍了如何使用后缀自动机（SAM）解决两个字符串问题。第一个问题是给定一个字符串和整数k，求出现k次的子串长度的最大出现次数。通过构建SAM的parent tree，并使用dfs和差分维护，可以高效解决该问题。第二个问题是给定一个字符串，求每个长度i的子串在字符串中的最大出现次数。同样利用SAM的parent tree和线段树进行区间取最大值操作，最终得到每个长度的最大出现次数。文章提供了详细的代码实现，并强调了SAM在处理字符串匹配问题中的高效性。
2025-05-09 21:43:50
855
原创 SAM详解3（SAM与AC自动机的相似性，SAM处理字符串匹配）
本文介绍了后缀自动机（SAM）及其在字符串匹配中的应用。首先，文章简要回顾了AC自动机的概念，并将其与SAM进行类比，指出SAM可以理解为将某个字符串的所有子串建立AC自动机。接着，文章通过例题详细讲解了SAM在解决最长公共子串问题中的应用，包括单串和多串的最长公共子串问题，并提供了相应的代码实现。最后，文章讨论了本质不同循环同构匹配问题，并给出了解决思路和代码参考。通过这些内容，读者可以更好地理解SAM的原理及其在字符串处理中的实际应用。
2025-05-09 15:19:19
1511
原创 SAM详解2.1（好题1）
所以，从某个节点(不一定要求是源点)出发的路径组成的串，都是互不相同的，如果相同的话，就违背了上述性质。最后说一点，统计路径条数时判断是否到达过要放在函数外面，即我的子节点到达过了，我也要算上它的贡献。注意需要分别处理两种情况，一种相同的字串只算一次，一种算多次。而且有一个显然的性质：SAM 中任意两个节点的表示集合没有交。于是我们可以在这个 DAG 上统计路径条数，也就是子串的数量。对于不同位置的相同子串算多次的情况，我们可以让。，那么答案就在这个转移边后的子DAG中。中已经讲过了，不会的可以去看。
2025-05-08 15:33:39
910
原创 二项式反演及其代数证明
第三个等号时交换求和顺序，是各种反演的常见技巧。，系数也和原来一样。所以两个式子显然等价。第四个等号即为上边组合数的性质，然后把。具体讲一下，第二个等号把。在看等号后的式子，每个。第五个等号是二项式定理。相关的项提到前面去。
2025-05-07 17:22:06
639
原创 SAM详解2(初级应用)
再在 parent tree 上做树形DP，我们惊讶的发现刚好符合标准。我们还是举这个串和其 parent tree 为例。然后对于没有新建节点的情况，我们只是加入了一条。在 parent tree 上，每个节点的。的 SAM 上跑匹配时，我们可以得到对于。证明也很简单，因为无法在这些前缀前面加东西。的串的长度乘上其出现次数的最大值。变化的时候,维护这个总和就好了。求本质不同子串出现次数的平方和。集合不同，即代表的子串不同。所表示的状态）不能匹配。求本质不同非空子串个数。的子串出现的最长后缀。
2025-05-06 18:35:11
1204
原创 SAM详解1
过于神秘的字符串，但是被同学怂恿，说学会 SAM 就学会了所有字符串算法，心动了过来学，果不其然被创飞了。但研究?天，故余虽愚，终有所获。由于作者学艺不精，文中可能会有疏漏，如发现错误欢迎指出，那么我们开始旅途吧。OI-WikiAlex_Wei的博客command_block的博客ZTer的博客我们定义一个子串的endposendpos是它在原串中结束位置的集合。例如原串为ababcababc，则endposab24endposc5。
2025-05-06 07:00:00
1137
原创 【题解】CF196D (哈希)
洛谷codeforces题意：给定长度为nnn的小写字母串sss和正整数ddd。定义一个串是好的当且仅当他没有长度大于等于ddd的回文子串。请你求出长度为nnn并且字典序比sss严格大的好串里，字典序最小的那个。没有输出Impossible。
2025-05-04 10:35:27
611
原创 0基础FWT详解2(巩固)
个州包含的所有城市组成的集合。定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为。座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。发现和第一题一样，那么一样的做法就行，但需要注意的是。的州，所有合法的划分方案的满意度之和是多少。定义一个划分的满意度为所有州的满意度的乘积。假设小 S 将这些城市划分成了。
2025-04-30 20:35:01
658
原创 【题解】CF2096F
的暴力，对于每组询问逐条便利语句，是。，可以直接暴力的搞一个线段树维护。注意到题目不强制在线，只要求出。单调不降，则可以用双指针维护。赋值完后将剩下的空位赋值为。语句前面最前的语句使得语句。的询问的左端点的最大值。，这样单次修改的均摊复杂度是。的维护可以开一颗线段树。可以线段树上二分维护。最终我们开两个线段树和。类型的语句是否合法。
2025-04-28 15:26:19
544
原创 线段树合并与线段树分裂
线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。线段树分裂实质上是线段树合并的逆过程。线段树分裂只适用于有序的序列，无序的序列是没有意义的，常用在动态开点的权值线段树。线段树分裂与线段树合并密不可分，一般来说没有只分裂不合并的题。的救灾粮，问所有操作结束后每个节点类型最多的救灾粮是那种。一棵树，点有点权，问每个节点的子树内有多少节点点权比它大。从这棵树的根节点开始递归分裂，当节点不存在时，递归结束。显然，对于两颗满的线段树，合并操作的复杂度是。
2025-04-27 10:28:06
685
原创 0基础FWT详解1
操作，即这个块的前半部分更新为前半部分和后半部分的和，后半部分更新为前半部分和后半部分的差。接下来是逆变换，可以和正变换一样做，但是是后半部分减去前半部分。对于逆变换也显然，这里不再推了，留给读者证明。一样做，但是换成后半部分向前半部分做贡献。的块，将每个块的前半部分累加到后半部分。因为初学，常数肯能稍大。可以用高维前缀和做，但这里不讲这个做法。有了之前的代码，发现正逆变换可以合并。根据前面的论证思路证得，这是对的。的递归构造相同，所以肯定是对的。按照之前的思路，容易得到应该是。两种答案，那么根据最初的。
2025-04-27 09:38:34
899
原创 【数据结构】李超线段树
我们用这条线段递归更新对应子树，用另一条线段作为懒标记更新整个区间，这就保证了递归下传的复杂度。不合法的点对就是原来的路径不经过环的，因为它们想走第二条路径就会经过环一次，会有点重复走。其中肯定有一个子区间被左区间或右区间完全包含，也就是说，在两条线段中，肯定有一条线段，只可能成为左区间的答案，或者只可能成为右区间的答案。如图，加入黄色线段后，只有红色节点的标记被更新，而绿色节点的标记还未被改变。这里我的写法是给李超线段树上的每个节点打个时间标记，记录它的线段是哪个时间段的，这样不用考虑删除的问题。
2025-04-23 14:37:01
912
原创 【笛卡尔树】
笛卡尔树是一种二叉树，每一个节点由一个键值二元组kw(k,w)kw构成。要求kkk满足二叉搜索树的性质，而www满足堆的性质。如果笛卡尔树的kwk,wkw键值确定，且kkk互不相同，www也互不相同，那么这棵笛卡尔树的结构是唯一的。通俗的讲，笛卡尔树是一个二叉树，中序遍历是原序列，同时满足堆性质。
2025-02-13 22:02:50
1011
原创 【平面图中欧拉公式】
平面图的一个重要性质是它可以将平面划分为多个区域，这些区域称为面（Face）。其中一个面是无限大的，称为外表面（Outer Face），其余的面是有限的，称为内表面（Inner Face）。即是原图本就存在一个没被删去的点，使得它上下左右都被删(边界也可以)。因为一定存在某个点，使得删去周围不超过两个点使得其与其上下左右不连通。换句话说，平面图可以在平面上画出，且其边不会相互交叉。，用并查集维护，因为删一个点最多影响四个面。删掉了一个点，四条边，合并了四个面。显然，再一个点都没删的情况下，
2025-01-22 11:14:25
1043
原创 【题解】AT_dp_t Permutation & UVA1650 数字串 Number String & AT_abc209_f [ABC209F] Deforestation
我们不需要考虑具体顺序，只需要先后，那就跟第一题一样了。注意如果两数相等，那就没有先后关系，和第二题一样。我们发现如果关系不确定那直接两种合并一起即可。证明显然，因为我们只需要考虑大小关系。根据性质可证，因为我们只考虑大小关系。个数，直接暴力枚举它是啥。但是反过来，你却发现一共有。求满足这样的性质的排列。我们发现，对于一个固定的。然后你就发现样例都过不了。两个数，什么时候先选。求有多少种方案，使得。
2024-09-22 13:12:44
845
原创 【网络流】——初识(最大流)
通俗地讲，回到引例，现在有一个问题需要我们去解决：水厂在单位时间内最多能发送多少水给小区？这就是网络流中的一个问题：最大流问题。
2024-07-25 09:22:53
1149
原创 【题解】UVA1564/SP2883 Widget Factory
组方程，所以判无数组解时判完未知数即可，而判无解时要判全部方程。如果不是在模意义下进行，这就是个裸的高斯消元。个方程，我们只用判断最右边那一列是否为。那求一下逆元即可，注意答案有范围。再说一下无解和无数组解的情况。
2024-07-24 15:00:00
1687
原创 【题解】P4003 无限之环
考虑拆点，将每一个点拆成上，下，左，右，中五个点，中点连向源点或汇点，其余四个点和异种颜色的这四类点匹配。然后看看这个图有什么用，考虑将源点连向所有黑点，所有白点连向汇点，然后直接跑最小费用最大流，如果。蓝边第一个数为流量，第二个数为费用，这样我们就可以模拟旋转操作了。点贡献，所以总贡献因为接口总数的一半，否则就有接口匹配不上，就漏水了。再深入一点，我们用红边限制流量，用蓝边模拟旋转。条边，且费用为什么为那些数，最好模拟一下。接口数，那么解即为最小费用，否则无解。，这是这个水管的基本数据。
2024-07-24 10:26:35
762
原创 【数据结构】Splay详解
二叉树的性质使得插入操作变得非常简易，具体而言，只要值比当前节点大，就往右子树找，小就往左子树找，一样就让计数器+1，如果找不到匹配的值就直接新建一个节点。这个跟插入差不多，从根节点不断往下找，每次向右子树找时加上左子树的size+1，因为左子树和根的值一定比查询值小(BST的性质)。本文将介绍Splay，虽然它并不能保证树一直是"平衡"的，但对于Splay的一系列操作，我们可以证明其每步操作的平摊复杂度都是。的后继旋转到根节点的右子树上，这样根节点的右子树的左儿子即为目标节点，直接断开联系即为删除。
2024-07-15 16:02:10
1450
原创 【数学笔记】一元n次不等式，分式不等式，绝对值不等式
这个采取分类讨论，类比一下。稍微理解一下，结合二次函数。的大小关系式，并使用。口诀为“奇穿偶不穿”。然后就跟上面一样了。
2024-01-25 21:15:58
1464
原创 【数学笔记】集合及简要逻辑
ABC......abc......{a是A中的元素：a属于A，记为a∈Ab不是A中的元素：b不属于A，记为b∈A}(1)确定性(2)互异性(3)无序性∅(1)N(2)Z(3)Q(4)R(5)N或N∗(6)C列举法11102357500123⋯500123⋯2⎩⎨⎧数集点集⋯有限集无限集注意⋯∅∅3(特殊性质描述法AIpx)AAx∈I∣。
2024-01-19 08:54:39
2094
原创 【题解】洛谷 CF11D A Simple Task
求无向图中的简单环个数，保证不存在重边和自环。简单环：除起点外，其余的点都只出现一次的回路。就为起点，那就是找到环了，直接统计即可。个节点走过的状态，起点为。
2023-11-29 13:51:09
1036
原创 【题解】P2622 关灯问题II
现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。一个整数，表示最少按按钮次数。的话，如果这盏灯是关的，那么把它打开，否则也不管；，那么当这盏灯开了的时候，把它关上，否则不管；然后暴力枚举当前状态按下第几个开关后的状态。个按钮，对于所有的灯都有一个效果。的大小并不确定，无法保证DP条件中的。考虑用宽搜，存的状态为当前灯的状态。其中，按下每个开关，对于其对第。，无论这灯是否开，都不管。，那按完后这个灯一定关着。，那按完后这个灯一定开着。串来表示灯的开关状态，
2023-11-29 13:08:35
2316
原创 【题解】P2627 [USACO11OPEN] Mowing the Lawn G 题解
在一年前赢得了小镇的最佳草坪比赛后，Farmer John 变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farmer John 希望能够再次夺冠。只连续的奶牛，那么，这些奶牛就会罢工去开派对 😃。因此，现在 Farmer John 需要你的帮助，计算 FJ 可以得到的最大效率，并且该方案中没有连续的超过。然而，Farmer John 的草坪非常脏乱，因此，Farmer John 只能够让他的奶牛来完成这项工作。第一行：一个值，表示 Farmer John 可以得到的最大的效率值。
2023-11-28 13:28:16
1107
原创 【算法】状压DP-2
状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种，0 或 1；当然如果有三种状态用三进制来表示也未尝不可。状态压缩DP：顾名思义，就是用状态压缩实现DP。不过呢，对于装压DP来说，不一定是二进制。状压DP主要分为集合式和棋盘式，本文只讨论棋盘式。集合式点这里。对于棋盘式的状压DP，有几种思考方式。每行每行考虑，逆推DP。每列每列考虑，逆推DP。
2023-11-28 13:03:13
435
原创 【题解】洛谷 P2704 [NOI2001] 炮兵阵地
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。从图上可见炮兵的攻击范围不受地形的影响。由于每一行都受上两行的状态的影响，所以我们需要开三维数组。一行一个整数，表示最多能摆放的炮兵部队的数量。的网格地图上部署他们的炮兵部队。
2023-11-27 14:07:12
2248
原创 【算法】状压DP-1
状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种，0 或 1；当然如果有三种状态用三进制来表示也未尝不可。状态压缩DP：顾名思义，就是用状态压缩实现DP状压DP主要分为集合式和棋盘式，本文只讨论集合式。
2023-11-27 13:33:51
1080
原创 【题解】洛谷 P1433 吃奶酪
一只小老鼠要把它们都吃掉，问至少要跑多少距离？处理完这些之后，就是裸的状压DP了，直接套模板即可。考虑状压DP，定义状态。点，走过的点的状态为。，然后枚举由哪个节点。两点之间的距离公式为。
2023-11-25 11:13:12
1088
原创 【题解】洛谷 CF788B Weird journey
而对于删除的第二条边，如果是非自环，那么图就有两个积点，存在欧拉路径，如果是自环，那么图所有点为偶点，存在欧拉回路。否则我们在分析：由于我们是将每条边当作两条边的，那么对于建的图来说，每个顶点的度数为偶数，及一定存在欧拉路。条路径仅走一遍，问不同的路径总数有多少，如果仅走一遍的两条边不同则将这两条路径视为不同。如果删除了一个自环，那剩下的所有点的度数仍然为偶数，所以可以随意删除下一条边。如果删除两条非自环，如果可行，那么它们一定共顶点，只有这样才会使共顶点的度数。，为积点，存在欧拉路径。
2023-11-25 08:43:54
1162
原创 【算法】FFT-1（递归实现）（不包括IFFT）
个数就可以了，问题缩小了一半，而缩小后还能继续缩小，所以我们用类似线段树的分治(递归)来解决它，时间复杂度。但是光有点值还是不够的，我们还要转换为数值，这就是 IFFT。没错，只有后面一坨是相反的，这说明我们可以。高中课本里讲过复数，不过不知道也没关系，这里会讲。但是，当我们把这个多项式看成一个函数时，我们将。接上文复数的知识，每个单位根在复平面上的坐标为。次单位根的每一个根，及方程的每一个解。的每一项相乘，最后累计，时间复杂度。个点的坐标，它们确定唯一的多项式。复数的运算其实跟实数的运算差不多。
2023-11-24 13:25:40
2467
1
原创 【题解】洛谷P6423 [COCI2008-2009#2] SVADA
肯定是二分了，于是我们在考虑怎么计算生产和开的椰子数。只第一种猴子的两个相关数据，具体解释请参照题目描述。只第二种猴子的两个相关数据，具体解释请参照题目描述。生产的椰子个数很容易得出为每个猴子生产的椰子个数总和。秒的椰子，找出一个分界点，使得分界点前生产的椰子。，表示猴子在花园中度过的总时间，以秒为单位。题目说的有点绕，但读懂题意后还是很简单的。只猴子能开椰子，一共生产/开了。最终看 cnt 是否大于。，表示第一种猴子的只数。，表示第二种猴子的只数。只猴子能生产椰子，有。
2023-11-24 13:00:03
826
原创 【题解】洛谷P3443 [POI2006] LIS-The Postman 题解
最后还有一个小技巧，及我们如果合并了边，在最后输出时还有点儿麻烦，所以=我们可以加几个数组，让程序在求欧拉回路时如果碰到了指定序列（合并后）中的边，就只能遍历完序列的边，这样输出也方便。那么在我们就来考虑怎么将边合成了，如果直接按照每条序列合并的话，会发现可能存在几条序列刚好有公共部分从而卡掉我们的程序。所以我们先给每条边编上一个编号，在维护指向这条边的上一条边和这条边指向的下一条边，及前驱和后继。而维护起来也是很容易的，用 map 存边的编号，开个数组记录后继，再用循环不断合并边。
2023-11-23 13:33:59
236
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人