Day 1

A.特工

若两个特工 \(i,j\) 成功匹配，当且仅当 \(x_i+y_j=x_j+y_i\)，移项可得 \(x_i-y_i=x_j-y_j\)，所以只需要用一个 map 存一下每个值的数量，统计即可。

B.提克塔可头

考虑游戏的局面不会很多，最多只有 \(3^9\) 种情况，且这些情况组成了一个 DAG。我们爆搜所有进程（共有 \(9!\) 种），建图。建图后拓扑排序即可预处理出所有的答案。

C.相似的回忆

考虑维护 \(pre\) 数组，\(pre_i\) 表示上一个和第 \(i\) 个位置的字符相同的位置，特别地，若该字符是第一次出现就赋值为 \(0\)。不难发现，若两个数组匹配，那么这两个数组的 \(pre\) 数组一定相同。

所以维护 \(a,b\) 数组的 hash 值，每次对于一个长度为 \(|b|\) 的 \(a\) 的子串判断和 \(b\) 的 hash 值是否相同即可。注意需要动态维护 \(a\) 的 hash 值，所以要用线段树来进行单点修改的操作。