日记

模拟赛。

T1 # Link to T1

赛格门特吹神力！

T2 # Link to T2

我们发现，如果把每个字符到前面与它相同的字符的距离处理出来当作串，那么就可以当作普通的字符串匹配了。比如 $\texttt{aab}$ 和 $\texttt{bba}$，处理出来都是 $\{0,1,0\}$，所以可以匹配。就可以直接拿字符串哈希做了。

但是我们发现一个问题：$\texttt{abab}$ 的后缀显然是和 $\texttt{aba}$ 匹配的，但是我们发现这个后缀对应的数组是 $\{0,2,2\}$，而 $\texttt{aba}$ 对应的数组是 $\{0,0,2\}$。究其原因是最前面的一个 $\texttt{a}$ 影响到了中间那个 $\texttt{a}$。所以我们在从哈希里删除的时候还得消除它对后面的影响。

T3 # Link to T3

我们发现答案上界是 $dis_t$。（$dis_i$ 表示 $s \to i$ 的最短路）。因为我们如果填的数种类多于 $dis_t$，那么一定有 $i$ 使得删除所有 $i$ 的边后这条最短路连通。

然而这个上界是可以达到的。对于一条 $u \leftrightarrow v$ 的边，我们将其边权设置为 $\max(dis_u,dis_v)$。就相当于把整个图按照 $dis$ 分层。每层之间一定是一个割。

T4 # Link to T4

其实不难。

有这么一个 trick：$\min(x \oplus y,y \oplus z) \le x \oplus z(x \le y \le z)$。所以我们如果想判一个集合 $\{a_1,a_2,\dots,a_n\}$ 是否合法，我们只需要将 $a$ 排序，然后判断 $\forall i \in [1,n)$ 是不是都有 $a_i \oplus a_{i + 1} \ge x$ 就行。

证明：
我们考虑 $x,z$ 在二进制下第一位不同的。显然，只能是 $x$ 的是 $0$，$z$ 的是 $1$。自然，$y$ 也只能是 $0,1$。如果 $y$ 那一位是 $0$，显然 $x \oplus y \le x \oplus z$。$y \oplus z$ 继续考虑就行。反之亦然。

因为题目让我们选一个集合出来，我们不需要管顺序，所以我们就可以将 $a$ 排序，然后就有 $O(n^2)$ dp：

显然，我们需要优化。我们考虑在什么区间内 $a_i \oplus a_j \ge x$。我们记录一个 $tmp$。从高到低枚举每一位。

• $a_i$ 这一位是 $0$，$x$ 这一位是 $0$：
  这个区间里的数这一位可以是 $1$，于是加入一个区间：$[tmp + 2^j,tmp + 2^j + (2^j - 1)]$。然后继续考虑 $tmp$ 这一位是 $0$ 的情况。
• $a_i$ 这一位是 $0$，$x$ 这一位是 $1$：
  显然 $tmp$ 这一位只能是 $1$。
• $a_i$ 这一位是 $1$，$x$ 这一位是 $0$：
  这个区间里的数这一位可以是 $0$，于是加入一个区间：$[tmp,tmp + (2^j - 1)]$。然后继续考虑 $tmp$ 这一位是 $1$ 的情况。
• $a_i$ 这一位是 $1$，$x$ 这一位是 $1$：
  显然 $tmp$ 这一位只能是 $0$。

然后我们就获得了 $O(\log V)$ 个区间。我们枚举每个区间，二分它在 $a$ 上所对应的区间。于是我们就可以用前缀和 $O(1)$ 转移了。

时间复杂度 $O(n \log n \log V)$。

后日谈 # Link to 后日谈

被做局了。发现自己的数论和图论烂的一批，晚上回家还是刷题吧。