后缀自动机

介绍 首先后缀自动机 可以包括给定字符串的所有子串 O(n) 是自动机 一些定义 endpos 字符串s的一个子串t，endpos(t)为s中t的所有结束位置构成的集合 SAM是一个最小的DFA 有向无环图 节点是状态，边是转移 转移是一些字母 从源点出发到终止状态所有转移连起来的字 ...
2021-11-20 00算法 > 字符串

维护区间众数

首先先把我之前的复制一手啊 绝对众数问题 就是出现个数超过n/2的众数 这个我们可以用一个摩尔投票的方法来写捏 摩尔投票 首先考虑一个序列，里面两两取数，如果一样就留下，不一样就两个数都消掉，那么最后留下的数肯定就是数量超过n/2的数 实现的话，用两个变量cur和cnt，如果当前的数和cur ...
2021-11-10 00算法 > 数据结构

单调队列优化多重背包

思路 首先我们考虑一下朴素的多重背包写法： 对于当前物品i，枚举选的个数n[i]，用于更新dp数组 然后我们能够发现这样一个神必规律： dp[i]用于维护代价为i的最大价值，且当前考虑选的物品代价为v 则dp[i]只能够从dp[j]，当且仅当j mod v == i mod v 且选的个数 ...
2021-11-05 00算法 > DP