后缀自动机 | SAM

概述

后缀自动机是处理字符串信息的有力工具。后缀自动机存储在 Trie 树上,配合 Link 指针就可以被认为是一张 DAG。任意一条从原点出发的路径都可以被认为是这个字符串的一个子串,且在后缀自动机上不会存在重复的子串信息(然而,我们可以进行一些扩展来维护子串位置信息)。

继续阅读后缀自动机 | SAM

「杂题集」- 2019年9月19日

方格取数

看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。

继续阅读「杂题集」- 2019年9月19日

[Fortuna OJ]4605 – 排序 sort 题解

主要思路

这道题好有意思啊,提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。

我们可以先二分出\(c\)位置的值,然后令所有大于等于\(c\)的值变成\(1\),小于的则变成\(0\)。然后排序的时候发现,其实就是重新组织零一的位置,所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。

继续阅读[Fortuna OJ]4605 – 排序 sort 题解

「2018泉州国庆集训#3」 – 解题报告

A – 人类基因组

这套题全都是暴力出奇迹系列。

我们枚举一个端点,然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\),然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。

然后用 sb 线段树搞下就行了,太特么傻逼了。

继续阅读「2018泉州国庆集训#3」 – 解题报告