首页 > 其他分享 >08.01

08.01

时间:2024-08-04 09:18:15浏览次数:12  
标签:dots 08.01 每个 cdot 维护 考虑 前缀

?

给定一个长度为 \(n\) 的字符串序列 \(S\),字符集为小写字母。\(m\) 次询问,每次给定含恰好一个通配符的串 \(T\),询问 \(T\) 能和多少 \(S_i\) 匹配。

\(\sum |S_i|+|T| \leq 3 \cdot 10^6\),\(n, m \leq 10^5\)。

对于每个串 \(s\) 和每个 \(i < |s|\),在 Trie 树的 \(s_{1 \dots i}\) 处打一个标签 \(s_{i+1\dots |s|}\),哈希维护之。

复杂度线性。

gym103409H

把串分成很多个形如 \([r \cdot 2^k, (r + 1)\cdot 2^k)\) 的样子。对询问串建 AC 自动机,我们需要求出模式串经过 AC 自动机的每个点多少次。

\(f_{u, k, 0/1}\):从 ACAM 的点 \(u\) 出发,走 \(s_{0 \sim 2^k-1}\) 或 \(s'_{0 \sim 2^k-1}\) 步会到达哪个节点。有 \(f_{u, k, 0} = f_{f_{u, k-1, 0}, k-1, 1}\)。

考虑 \(c_{u, k, 0/1}\) 为使用 \(f_{u, k, 0/1}\) 转移的次数,考虑用

\[g_{u, k-1, 0} = c_{u, k-1, 0} + g_{u, k, 0} + \sum_{f_{v, k, 1}=u} g_{v, k, 1} \]

更新 \(g_{u, k, 0/1}\),最后 \(g_{u, 0, 0} + g_{u, 0, 1}\) 即为经过的次数。

CF1801G

考虑 \(s_{1\dots r}\) 的匹配数减去 \(s_{1\dots l-1}\) 的匹配数,多余的部分跨越 \(l\)。

分解 \((A, B)\),\(A\) 是 \(s_{1 \dots l-1}\) 的后缀,\(B\) 是 \(s_{l \dots n}\) 的前缀,且 \(A+B \in \{s_i\}\)。

gym104090l

P4770

首先对每个 \(r\) 求一个最小的 \(l\) 使得 \(T[l, r] \in S\)。

寻找的方法是,增量,跳 fail 跳到有 \(T_r\) 的出边,走过去。(直接跳好像就是对的)

这样可以对一个 \(s\) 做,利用 SAM 遍历 \(T\) 的所有子串并通过 \(l\) 就行了。

接下来要拓展到 \(s[l, r]\) 的情况。

还是考虑维护所有 \(l\)。我们扫右端点并同时维护每个子串最靠右的出现,考虑动态更新每个点子树内 endpos 值最大且不超过 \(r\) 的数值 \(c_i\),则每次要把一个点 fail 树上到根的所有祖先一起赋值。设当前串的长度为 \(m\),枚举到的右端点为 \(r_0\),当前在询问 \(s[l, r]\),找到 \(s[l+m-1, r]\) 区间的 endpos 集合是否有 \(r_0\)。至于 \(T[1, r_0]\) 有几个前缀出现过,利用 \(c\) 求当前区间与 \(T[1, r_0]\) 的最长公共后缀就行了。

P6292

gym104901L

分段 dp:\(f_{i, j, 0/1}\) 表示前 \(i\) 段选 \(j\) 段且最后一段是否被选,有

\[f_{i, j, 1} = \max\{ f_{i', j-(i-i'), 0} + w(i', i) \} \\ f_{i, j, 0} = \max\{ f_{i-1, j, 1}, f_{i-1, j, 0} \} \]

考虑到第一种转移中 \(i-j\) 不变,以 \(i-j\) 为第一维做 dp,同时试图用数据结构维护最优的选择点。

考虑 \(w(i', i)\) 的变化,当 \(i\) 为某个集合的 \(r\) 时,所有 \(i'<l\) 的 \(w(i', i)\) 都会增加,也就是前缀加。

需要维护的是,后面插数,前缀加,全局最大值,线段树维护之,复杂度 \(O(n^2 \log n + nm)\)。

标签:dots,08.01,每个,cdot,维护,考虑,前缀
From: https://www.cnblogs.com/purplevine/p/18341457

相关文章

  • 不忘初心 Windows11 Insider Preview 25915.1000 Canary预览版 无更新 纯净精简 2023.
    此版不能更新补丁,并开启按流量计费,此版保留Hyper和linux,让人期待的任务栏图标从不合并功能此版已经回归,母版来自UUPWindows11InsiderPreview25915.1000Canary频道预览版,本版本自动跳过硬件检测,优化后台进程和服务,精简一些日常不常用的组件,速度和性能比原版更胜一筹,为了保证稳......