后缀数组(SA)

T1 的 Hack 数据提醒我,尽管时间复杂度没有变化,但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。

T2 没有认真读题,忽略了“恰执行一次”的要求。

T3 里面没有使用自己熟悉的存边方式,时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。

简单题解

A – 跳棋

(x,y)(x,y) 跨步跳能够跳到 (x±2,y),(x,y±2)(x\pm 2,y),(x,y\pm 2),以及 (x+k,y+k),k=±2(x+k,y+k),k=\pm 2。可以发现 x,yx,y 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块,在这些连通块上 BFS 即可。

若采用 std::map 存储,时间复杂度为 O(7nlogn)\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)。需要采纳“避免遍历不存在的连通块”之类的优化。 (更多…)

More
  • 2022年11月23日

洛谷题库 P4770 [NOI2018] 你的名字

本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用,以及利用可持久化数据结构查询历史区间极值的方法。

也就是说,大体思路只花费一小时不到,去掉一个 log\log 却耗了我一天多……

@XZC__Bobby 花了 33 小时不到就用 SA 暴切了!!%%%

“双指针”扫描求串 TT 的每个前缀在 SS 中匹配的最长子串

在任何时刻,SAM 的状态转移函数会将某字符串引向串 SS 中的等价 endpos\mathrm{endpos} 状态。根据 endpos\mathrm{endpos} 和 parent tree 的性质,我们可以对前缀 T[1k],k{1,2,,T}T[1\cdots k], k \in \{1, 2,\cdots, |T|\} 依次求出其最长的作为 SS 的子串出现的后缀。 (更多…)

More
  • 2022年7月9日