日记

考试一定不能犯唐。

T1 # Link to T1

纯唐。

T2 # Link to T2

头一次在 OI 赛里看到防 AK 题。

T3 # Link to T3

首先有结论：若 $[i,j]$ 这个区间是个合法的括号串，且 $i,j$ 被删了，那么肯定 $[i,j]$ 这个区间也全被删掉是最优的，口胡一下就能证明。

那么考虑 dp。设 $dp_i$ 表示只考虑 $[i,n]$ 这个区间内的，字典序最小的字符串。注意 $dp_i$ 是个字符串。设 $to_i$ 表示 $[i,to_i)$ 这个区间合法且 $to_i$ 最小，那么有显然的转移：

时间复杂度 $O(n^2)$，瓶颈在于 $O(n)$ 的字典序比较。

考虑优化字典序比较。这里先定义几个东西：

• $nxt_i$
  我们把题意转化一下。题目要求删去几个括号，我们改成留下几个括号，$nxt_i$ 表示从 $i$ 开始第一个留下的位置（包括 $i$）。
• $pos_{i,j}$
  表示 $i$ 之后第 $2^j$ 个留下来的位置（不包括 $i$）。
• $hsh_{i,j}$
  表示 $i$ 之后 $2^j$ 留下来的字符组成的字符串的哈希值（包括 $i$）

我们考虑字典序比较的过程。应该是先找到一段极长的相同前缀然后比较第一个不同的位置。我们可以通过 $hsh$ 和 $pos$ 数组倍增找到第一个不同的位置，比较一下，进行转移。因为我们没有 $dp$ 数组了，$dp_i = dp_{to_i}$ 表现为 $nxt_i = nxt_{to_i}$。可以把 $nxt$ 当成新的 dp 数组。时间复杂度 $O(n \log n)$。

T4 # Link to T4

我们发现这玩意很像多模字符串匹配。考虑建出 AC 自动机。我们发现每个字典树上的点都必定对应一个原图里的点，对于字典树里有的和原图里也有的，我们就加入新图。然后跑 dijkstra。

但是我们发现字符集大小是 $n$，那样时空都是 $O(n^2)$ 的，立即发生爆炸。我们发现可以通过可持久化数组优化，因为每个点都是从 $fail$ 迭代而来。

后日谈 # Link to 后日谈

这模拟赛是人啊？在 OI 赛制里放防 AK 题目，你安的什么心？

今天晚上看到桌子上放着一盒牛奶，我以为是今天开的，没想到是昨天开的，已经变成酸奶了。而我的嗓子反应比脑子快，咽下去了。

我就等着拉肚子吧。