菜王的 blog

题单

题意

link

你有一个可重集 $s$，其中只包含 $[1, n]$ 内的元素，元素 $i$ 有 $a_i$ 个。

有两种操作：

1. 选择区间 $[l, r]$，从可重集里移除一个 $l$，一个 $l + 1$……一个 $r$，此操作需满足 $\forall i \in [l, r] (i \in s)$。
2. 选择 $i$ 与 $x$，从可重集里移除 $x$ 个 $i$，此操作需满足 $s$ 内至少有 $x$ 个 $i$。

请求出将 $s$ 删空的最小操作次数。

题解

可以证明，删除 $s$ 里 $[l, r]$ 之间的数，要么做第一种操作直到不能做为止，再对被 $0$ 划分开的各个区间分别删除；要么做 $r - l + 1$ 次第二次操作。

递归解决问题即可。

题意

link

有 $5$ 种重量的包裹，重量为 $i$ 的包裹有 $a_i$ 个。

有一些人，这些人有一个力量值，有 $5$ 种力量值的包裹，力量值为 $i$ 的人有 $b_i$ 个。

每一个人都可以扛一些重量和不超过自己力量值的包裹，请问是否可以把包裹全部扛完？

题解

好题。

按照贪心角度思考，首先应该让每个人剩下能扛的重量尽量小，然后让每个人装的个数尽量多。

定义“剩余力量值”为一个人还能扛的重量。

设函数 $\operatorname{pack}(x, y)$ 会让每一个剩余力量值为 $y$ 的人去扛一个重量为 $x$ 的物品（然后他的剩余力量值变为 $y - x$），直到没有剩余力量值为 $y$ 的人或重量为 $x$ 的物品都被扛完为止。

设 $c$ 为现在要全部扛走的物品重量。

对于 $c = 5$ 的情况，执行 $\operatorname{pack}(5, 5)$ 即可。

对于 $c = 4$ 的情况，先执行 $\operatorname{pack}(4, 4)$，再执行 $\operatorname{pack}(4, 5)$。

对于 $c = 3$ 的情况，按顺序执行 $\operatorname{pack}(3, 3)$，$\operatorname{pack}(3, 5)$，$\operatorname{pack}(3, 4)$。

为什么这样是对的呢？因为我们不用考虑重量为 $1$ 的物品，它不管被谁扛都一样。而执行 $\operatorname{pack}(3, 5)$ 会让一些人的剩余力量值变为 $2$，可以扛更多的重量为 $2$ 的物品.

对于 $c = 2$ 和 $c = 1$ 的情况，直接对于每一个 $i \ (c \le i \le 5)$ 倒序执行 $\operatorname{pack}(c, i)$ 即可。

为什么要倒序执行呢？因为只有倒序执行才能让一些人扛多个物品。

执行完以上步骤以后，查看是否有物品剩余即可判定。

题意

link

给出一个长度为 $n$，且没有 $0$ 的数列 $a$，请你构造一个长度为 $n$，且没有 $0$ 的数列 $b$，满足 $\sum_{i = 1}^n a_ib_i = 0$。

题解

有趣的题。

核心思想是让 $a_i$ 和 $a_{i + 1}$ 互相抵消，只需要令 $b_i = a_{i + 1}$，$b_{i + 1} = -a_i$ 即可。

如果 $n$ 是奇数，让前三个数抵消。在 $1, 2, 3$ 中找到两个满足 $a_x + a_y \not= 0$ 的 $x$ 和 $y$（这样的 $x$ 和 $y$ 一定存在），剩下的数为 $z$，则 $b_x = b_y = -a_z$，$b_z = a_x + a_y$。

题意

link

给定一个长度为奇数的排列 $a_1, a_2, \dots, a_n$，你需要构造一组长度不超过 $\dfrac52 n$ 的操作序列 $s_1, s_2, \dots, s_k$，使得：

• $1 \le s_i \le n$，$s_i$ 为奇数；

• 按从前往后的顺序，对于每个 $s_i$，反转排列的前 $s_i$ 项，最后得到的排列中 $a_i = i$。

题解

妙妙构造题。

设 $\operatorname{do}(p)$ 为翻转 $a_{1 \sim p}$。

首先是无解。由于交换位置只能是奇数，所以无论如何交换，每个元素所在位置的奇偶性不变。如果 $a_i$ 与 $i$ 的奇偶性不一致则无解。

然后根据 $\dfrac{5n}{2}$ 来猜想每一次使用五个操作置位两个元素。

考虑从 $1$ 开始两两置位，为了不被破坏，我们将已置位的数放在最后，就像这样：

$\dots, 2i - 2, 2i - 3, \dots, 1$。

假设现在置位 $2i - 1$ 和 $2i$。

1. 记录 $2i - 1$ 的位置为 $p1$。执行 $\operatorname{do}(p1)$，把 $2i - 1$ 移到位置 $1$。

2. 记录 $2i$ 的位置为 $p2$。执行 $\operatorname{do}(p2 - 1)$，把 $2i - 1$ 移到位置 $p2 - 1$。这样，$2i - 1$ 和 $2i$ 就相邻了。

3. 因为之前提到过的奇偶性问题，$p2$ 是偶数。所以先执行一次 $\operatorname{do}(p2 + 1)$，序列会变成这样：$x, 2i, 2i - 1, \dots, 2i - 2, 2i - 3, \dots, 1$，其中的 $x$ 是原先的 $a_{p2 + 1}$。

4. 再执行一次 $\operatorname{do}(3)$，序列就变成这样：$2i - 1, 2i, \dots, 2i - 2, 2i - 3, \dots, 1$。

5. 执行一次 $\operatorname{do}(n - 2i + 2)$，序列就变成了这样：$\dots, 2i, 2i - 1, 2i - 2, 2i - 3, \dots, 1$。

这样，我们用 $5$ 次操作成功置位了两个数。

但是，置位完成的序列是 $n, n - 1, \dots, 2, 1$，还要执行一下 $\operatorname{do}(n)$。

计算一下：

匹配 $\dfrac{n - 1}2$ 个数，每个数 $5$ 次操作，再加上最后一次操作，总共 $5 \times \dfrac{n - 1}2 + 1$ 次操作。

$\left\lfloor\dfrac{5n}2\right\rfloor = \left\lfloor2.5n\right\rfloor = 2n + \left\lfloor\dfrac n 2\right\rfloor = 2n + \dfrac{n - 1}2$

同时乘上 $2$，则分别变为 $5n - 3$ 和 $5n - 1$。

$5n - 3 < 5n - 1$，构造成立。

题意

link

有一个长度为 $l$，只包含 $\texttt{"Y"}$ 和 $\texttt{"."}$ 的字符串 $s$，定义一次操作为交换 $s$ 中相邻两个字符，至多执行 $k$ 次操作，最大化 $s$ 中连续 $\texttt{"Y"}$ 的个数。

题解

令序列 $b$ 为按照递增顺序记录所有 $\texttt{"Y"}$ 的位置的序列，序列 $a$ 与序列 $b$ 等长，对于所有的 $i \in [1, |b|]$，$a_i = b_i - i$。

设一次操作使 $a$ 中一个元素 $+1$ 或 $-1$，然后，问题转化成了这样：

（问题一）至多执行 $k$ 次操作，最大化 $a$ 中相等数字个数。

由于上述问题答案有单调性，我们可以使用二分搜索。

考虑判断可行性：

（问题二）是否可能至多执行 $k$ 次操作，使 $s$ 中至少 $x$ 个字符串连续。

为了解决问题二，我们需要考虑这个问题：

（问题三）最小需要多少次操作，使得 $a_l, a_{l + 1}, a_{l + 2}, \dots, a_r$ 全都相等。

这个问题等同于：

（问题四）求出 $\min_{x \in \mathbb{R}^+}\{\sum_{i = l}^r |a_i - x|\}$。

问题四是一个经典的问题，取 $x \in \left[a_{\left\lfloor\frac{l + r}{2}\right\rfloor}, a_{\left\lceil\frac{l + r}{2}\right\rceil}\right]$ 都可以最优。

问题四（也就是问题三）可以 $O(1)$ 解决，于是问题二可以 $O(n)$ 解决，问题一（也就是原问题）可以 $O(n \log n)$ 解决。

题意

link

你有一个 $n \times m$ 的棋盘，还有一个国王。

定义 $(i, j)$ 为第 $i$ 行第 $j$ 列的格子（$1 \le i \le n, 1 \le n \le m$）。

一个在 $(x, y)$ 的国王可以走到 $(x', y')$ 当且仅当 $\max(|x - x'|, |y - y'|) = 1$。

现在想让你构造一条路径，使国王从 $(1, 1)$ 出发，经过每个格子恰好一次，在 $(a, b)$ 结束（$(a, b) \not= (1, 1)$）。

可以证明一定有解。

题解

考虑用分治解决问题。

首先，考虑 $n = 2$ 的情况（边界情况）。

我们可以像这样规划路径：

准确来说，路径是这样的：$(1, 1) \to (2, 1) \to (1, 2) \to (2, 2) \to \cdots \to (1, b - 1) \to (2, b - 1) \to (3 - a, b) \to (3 - a, b + 1) \to \cdots \to (3 - a, m) \to (a, m) \to (a, m - 1) \to \cdots \to (a, b + 1) \to (a, b)$。

$m = 2$ 的情况类似，交换行和列即可。

最后考虑 $n > 2$ 且 $m > 2$ 的情况：

考虑走 $(1, 1) \to (2, 1) \to (3, 1) \to \cdots \to (n, 1) \to (n, 2)$ 来消除第一列。

由于消除第一列的时候可能经过 $(a, b)$，我们分两种情况讨论：

1. 不经过 $(a, b)$。由于第一列已经走完，走到了 $(n, 2)$，这就变成了一个新的子问题，从 $(n, 2)$ 走到 $(a, b)$。删掉第一列，再将剩下的部分垂直翻转，问题就变成了从 $(1, 1)$ 走到 $(n - a + 1, b)$，到了一个棋盘规模更小的子问题上。

2. 经过 $(a, b)$。由于 $(a, b) \not= (1, 1)$，交换行和列即可归约到上一种情况。

到现在，这道题就做完了。

题意

link

给你一个长度为 $n$ 的正整数序列 $a$，定义一次操作为：

• 选择三个整数 $i, j, x$（$1 \le i, j \le n$，$0 \le x \le 10^9$）。

• 使 $a_i = a_i - x \times i$，$a_j = a_j + x \times i$。

• 每次操作之后，序列里所有元素都应该为正整数。

请你构造一种方案，执行至多 $3n$ 次操作，使 $a$ 中元素全部相等，或返回无解。

题解

注意到每次操作后，序列的和不变。

所以如果 $\sum a_i$ 不是 $n$ 的倍数则无解。

由于位置 $1$ 的特殊性，从位置 $1$ 移走的操作变为 $a_1 = a_1 - x$，$a_j = a_j + x$。

所以，如果我们能把所有其他的 $a_i$ 都移到 $a_1$，那么就可以用 $n - 1$ 次操作平均分配。

怎么移呢？

如果 $a_i$ 是 $i$ 的倍数，就可以直接一次操作移走。

否则（VP 时没想到），从 $a_1$ 借一个 $i - (a_i \bmod i)$ 到 $a_i$，就可以直接移走了。为什么一定可以借呢？因为 $a_i > 0$，所以移走 $a_i$ 时 $a_1 \ge i - 1$。

这样，就可以用至多 $2n - 2$ 次操作把所有其他的 $a_i$ 都移到 $a_1$。

$n - 1 + 2n - 2 = 3n - 3 \le 3n$，这道题就做完了。

题意

link

有一个可重集 $S$，最初里面只有一个元素 $L$。

定义一次操作为：

• 从 $S$ 中取出一个元素 $x$，选择一个正整数 $k$（$1 \le k \le x - 1$），往 $S$ 中加入 $k$ 和 $x - k$，代价为 $x$。

有一个大小为 $n$ 的可重集 $a$，请求出使 $a \subseteq S$ 的最小代价。

保证 $\sum_{x \in a} x \le L$。

题解

设 $suma$ 为 $\sum_{x \in a} x$。

如果 $suma = L$，那么最后 $S = a$。

如果 $suma < L$，那么最后 $S = a \cup \{L - suma\}$。

考虑往回推，从最终的 $S$ 合并到只剩一个元素 $L$。

于是操作就变成了这样：

• 从 $S$ 中取出两个元素 $x, y$，往 $S$ 中加入 $x + y$，代价为 $x + y$。

这不就是 [NOIP2004 提高组] 合并果子 吗？于是这道题就做完了。

赛时没想出来的原因：

1. 被诈骗的题面严重误导。
2. 降智。

题意

link

对于平面上的两点 $p(x_p, y_p), q(x_q, y_q)$，我们定义它们之间的曼哈顿距离 $d(p,q)=|x_p-x_q|+|y_p-y_q|$。

进一步定义由三个点构成的一组点 $p,q,r$ 是坏的仅当 $d(p,r)=d(p,q)+d(q,r)$。

定义一个序列 $b$ 是好的，当且仅当这个序列无法选出一组点 $i, j, k$ 使得 $(b_i, i), (b_j, j), (b_k, k)$ 是坏的。

给你一个序列 $a$，请求出 $a$ 的好的连续子序列个数。

题解

结论题。

根据曼哈顿距离的定义，当 $a_i \le a_j \le a_k$ 或 $a_i \ge a_j \ge a_k$ 时，$(a_i, i), (a_j, j), (a_k, k)$ 是坏的。

有一个结论：只要一个序列的长度 $\ge 5$，那么这个序列就是坏的。

证明比较显然，这里就不写了。

所以，我们只需要枚举长度 $\le 4$ 的连续子序列即可。

题意

link

有一个仅由小写字母组成的字符串 $s$。最开始，$|s| = 1$。

还有 $2n$ 个字符串，分别是 $t_1, t_2, \dots, t_{2n}$。

已经执行了 $n$ 次操作，第 $i$ 次操作把 $s$ 的一个子串 $t_{2i - 1}$ 替换为 $t_{2i}$。

你只知道最终的 $s$ 和被打乱顺序的 $t$。

请求出最开始的 $s$。数据保证有解。

题解

赛时觉得根本不可做，看了题解才发现这道题极度诈骗。

我们考虑每个字符在 $t$ 中出现的次数的奇偶性。

无论这个字符串是替换的，还是被替换的，字符出现的次数的奇偶性的变化都是相同的。

因为保证有解，所以每一个在 $t$ 中出现奇数次的字符要么在最终的 $s$ 中出现，要么在开始的 $s$ 中出现，且在开始的 $s$ 中出现的字符恰好只有一个。

输出在 $t$ 和 $s$ 中出现奇数次的唯一一个字符即可。

题意

给出一个 $n$ 位正整数 $x$，请你构造一个 $n$ 为正整数 $y$（不含前导 $0$），使得 $x + y$ 是回文的。

题解

link

挺诈骗的一道题。

可以发现，如果 $x$ 的第一位不是 $9$，直接输出 $999....9 - x$ 即可。（$n$ 个 $9$）

否则，输出 $111...1 - x$。（$n + 1$ 个 $1$）

题意

link

有一个长度为 $n$ 的序列 $a_i$。

你可以对这个序列执行三种操作：

1. 前缀减 $1$。
2. 后缀减 $1$。
3. 整体加 $1$。

请问将整个序列变为 $0$ 所需的最小步数。

题解

由于题面中并没有提到无解，所以我们思考如何构造出一组解。

然后我们发现执行以下三个操作可以使 $a_i$ 减 $1$ 且其他 $a_i$ 不变：

1. $[1, i]$ 减 $1$。
2. $[i, n]$ 减 $1$。
3. 整体加 $1$。

所以，我们可以首先执行 $\max(\max\limits_{i = 1}^n -a_i, 0)$ 次操作三，然后对于每一个数分别减。

然后我们会发现有一些冗余的操作，比如对 $[1, 4]$ 减 $1$，$[5, n]$ 减 $1$ 再整体加，尽可能抵消这些操作即可。

题意

link

给出 $a, b, c, d$ 四个数和只包含 $\texttt{"A"}, \texttt{"B"}$ 的字符串 $s$，请问 $s$ 是否能由恰好 $a$ 个 $\texttt{"A"}$，$b$ 个 $\texttt{"B"}$，$c$ 个 $\texttt{"AB"}$，$d$ 个 $\texttt{"BA"}$ 连接而成？

保证 $a + b + 2c + 2d = |s|$。

题解

神奇的贪心，会跳舞的贪心。

首先判掉字母个数不符合的情况，然后问题就变成了：

能否在 $s$ 里找到 $c$ 个 $\texttt{"AB"}$，$d$ 个 $\texttt{"BA"}$ 且它们互不重复？

为什么这样转换是正确的呢？因为如果字母个数符合，那么除去找到的位置，其它位置都可以用 $\texttt{"A"}$ 和 $\texttt{"B"}$ 填充。

然后我们发现如果相邻两个位置字符相同，那么这里不可能找到 $\texttt{"AB"}$ 或 $\texttt{"BA"}$，所以我们可以将 $s$ 分成若干极长连续段，每一段的相邻字符互不相等。

分出的极长连续段有三种情况，我们来列举一下：

1. $len$ 为奇数。在此情况下，无论是 $\texttt{"AB...BA"}$ 还是 $\texttt{"BA...AB"}$，可以选出 $x$ 个 $\texttt{"AB"}$ 与 $y$ 个 $\texttt{"BA"}$ 当且仅当 $x + y \le \frac{len - 1}2$。

2. $len$ 为偶数。我们还要继续分类讨论下去。

   1. 是 $\texttt{"AB...AB"}$。可以选出 $x$ 个 $\texttt{"AB"}$ 与 $y$ 个 $\texttt{"BA"}$ 当且仅当 $x + y \le \frac{len - 2}2$，或 $x = \frac{len}2$ 且 $y = 0$。

   2. 是 $\texttt{"BA...BA"}$。可以选出 $x$ 个 $\texttt{"AB"}$ 与 $y$ 个 $\texttt{"BA"}$ 当且仅当 $x + y \le \frac{len - 2}2$，或 $x = 0$ 且 $y = \frac{len}2$。

我们发现 $len$ 为偶数的特殊情况，可以使总共能找到的个数变得更多，所以优先考虑他们绝对是更优的。

所以，我们对于 $\texttt{"AB...AB"}$ 和 $\texttt{"BA...BA"}$ 这两种情况，将这些连续段分别按照大小排序，将他们分别优先贡献给 $\texttt{"AB"}$ 和 $\texttt{"BA"}$ 直到达到 $c$ 或 $d$ 的目标，或者无法继续贡献。如果还有剩下的连续段，就对他们随意处理。

时间复杂度为 $O(n \log n)$，排序用桶排可以做到 $O(n)$。

题意

link

有 $n$ 种金额不同的硬币，第 $i$ 种硬币的面额为 $a_i$，且 $a_1 = 1$，对于所有的 $1 \le i < n$ 有 $a_i | a_{i + 1}$。

给出金额 $k$，请问支付 $k$ 元需要的给出硬币数与找回硬币数之和。

题解

一道不错的贪心 / 递归。

令 $\operatorname{solve}(p, x)$ 为使用面额大于等于 $a_p$ 的硬币支付 $x$ 元的答案，那么所要求的答案就为 $\operatorname{solve}(1, k)$。

由于使用面额大于等于 $a_{p + 1}$ 的硬币支付的金额必须要是 $a_{p + 1}$ 的倍数，所以我们考虑使用一些面额为 $a_p$ 的硬币（给出或找回）使得 $k$ 是 $a_{p + 1}$ 的倍数。

于是我们就获得了递归公式，令 $x \bmod a_{p + 1}$ 为 $d$，则：

$\operatorname{solve}(n, x) = x / a_n$

$\operatorname{solve}(p, x) = \min(\operatorname{solve}(p + 1, x - d) + \frac d{a_p}, \operatorname{solve}(p + 1, x - d + a_{p + 1}) + \frac{a_{p + 1} - d}{a_p})$

由于 $x$ 维度只出现了 $\lfloor\frac xy\rfloor$ 和 $\lceil\frac xy\rceil$ 的转移，记忆化可以做到 $O(n)$。

题意

link

给出 $n$，构造一组 $x, y, z$ 使得 $\frac 1x + \frac 1y + \frac 1z = \frac 2n$。

题解

首先，我们发现只有分母为 $n$ 的项分子为 $2$，所以令 $z = n$，问题转化为构造出一组 $x, y$，使得 $\frac 1x + \frac 1y = \frac 1n$。

我们可以将 $\frac 1n$ 划分成两个分子为 $1$ 的分数之积，这让我们想起了裂项：$\frac 1n = \frac 1{n + 1} + \frac 1{n(n + 1)}$。

所以就有了一种构造方案：$x = n, y = n + 1, z = n(n + 1)$。

题意

link

有一个编辑器，每次你可以询问这个编辑器每行长度为 $x$ 时要花多少行才能装下 $n$ 个单词。

单词占的长度为它本身的长度，同一行的相邻单词之间有长度为 $1$ 的空格，一个单词不能换行写。

一个编辑器所占的面积为它的每行长度乘行数。问能装下这些单词的编辑器面积最小多少。

你最多能询问 $n + 30$ 次。

题解

很好的交互题。

$n + 30$ 次询问令我们想到 $n + \log$ 级别的询问。

考虑首先二分出只用一行的长度 $len$。

如果使用 $k$ 行比使用一行更优，那么编辑器的长度至多是 $\lfloor \frac{len}k\rfloor$。（因为如果长度更长的话面积就会更大）

我们还发现，如果使用 $k$ 行比使用一行更优，那么编辑器的长度至少也是 $\lfloor \frac{len}k\rfloor$。因为使用 $k$ 行比使用一行最多节省 $k - 1$ 个空格，所以编辑器长度不可能是 $\lfloor\frac{len}k\rfloor - 1$ 或更短。

所以我们对于每个 $2 \sim n$ 的长度查询一次并且更新答案即可。

题意

link

有一个长度为 $n$ 的 01 串 $a$，定义一次操作为删除 $a$ 的一个相邻字符都不同的子串。

$q$ 次询问，每次询问 $a$ 的一个子串最少几次删空。

题解

神仙诈骗题。

考虑维护 $\texttt{"00"}$ 和 $\texttt{"11"}$ 的个数。

首先我们发现，我们删掉的串一定是一个极长的合法串，所以，如果 $\texttt{"00"}$ 和 $\texttt{"11"}$ 都没了，那么串也被删空了。

然后如果删掉了一个极长的奇数长度的合法串，如 $0[01010]0 \to 00$，会减少一个 $\texttt{"00"}$ 或 $\texttt{"11"}$；

如果删掉了一个极长的偶数长度的合法串，如 $0[010101]1 \to 01$，会减少一个 $\texttt{"00"}$ 和一个 $\texttt{"11"}$。

显然进行第二种操作更优，且我们发现，只要 $\texttt{"00"}$ 和 $\texttt{"11"}$ 个数都不为 $0$ 就必然可以执行一次（因为相邻的 $\texttt{"00"}$ 和 $\texttt{"11"}$（或 $\texttt{“11”}$ 和 $\texttt{"00"}$）之间肯定能产生偶数长度的合法串），所以最优方案肯定是执行第二种操作直到不能做为止，再执行第一种操作。

所以设 $\texttt{"00"}$ 有 $x$ 个，$\texttt{"11"}$ 有 $y$ 个，那么答案即为 $\max(x, y) + 1$。

题意

link

你有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，每次操作你可以选择序列中的两个元素 $a_i,a_j$（需要保证 $\gcd\{a_i,a_j\}$ 不在原序列内），然后将 $\gcd\{a_i,a_j\}$ 放到序列末尾。求你最多能够对这个序列进行多少次操作。

题解

又又又又又又又是诈骗题。/oh

首先题目里的操作是骗你的，每一个放在末尾的数其实都是原序列里几个数的 $\gcd$。

由于值域只有 $10^6$，所以我们可以想到枚举每个数是否可以由原序列里的几个数的 $\gcd$ 得到。

然后发现一个数只有可能由它的几个倍数的 $\gcd$ 得到，所以对于每个数 $x$，我们可以贪心的将它的所有倍数都选中，检查 $\gcd$ 是否等于 $x$，如果是则 $x$ 能被得到。

设能被得到的数为 $ans$，则答案为 $ans - n$。

题意

给定 $n, k, m$，请构造一个由 $m$ 个长度为 $n$ 的 01 串构成的序列 $s$，下标从 $0$ 开始。使得序列中每个串恰好有 $k$ 个 $1$。且对于 $0 \le i < l$，$s_i$ 既可以通过循环移位，也可以通过将一个 1 与右边的 0 交换，变为 $s_{i + 1}$。

题解

由于构造出 $s_0$ 之后，可以将 $s_0$ 的每一个循环同构串插入 set。然后枚举每一个能交换的位置，判断是否在 set 里面即可求出 $s$。

所以这里只讲一下构造 $s_0$ 的方案，且只考虑 $\gcd(n, k) = 1$ 的情况。

设 $dis_i$ 为第 $i$ 个为 1 的位置与第 $i + 1$ 为 1 的位置的距离（第 $k + 1$ 个为 $1$ 的位置是第 $1$ 个为 $k$ 的位置）。

考虑递归构造，设 $\operatorname{solve}(n, k)$ 为一个长度为 $n$ 且 1 个数为 $k$ 的字符串。

如果 $k = 1$，那么直接构造一个第一位为 1，其余位均为 0 的字符串即可。

否则，在手玩 $k = 2$ 以及 $k = 3$ 的情况后，可以发现 $dis_i$ 要么等于 $\lfloor\frac nk\rfloor$，要么等于 $\lceil\frac nk\rceil$，因为 $\sum dis = n$，所以等于 $\lceil\frac nk\rceil$ 的 $dis_i$ 有 $n \bmod k$ 个，等于 $\lfloor\frac nk\rfloor$ 的 $dis_i$ 就有 $k - n \bmod k$ 个。

考虑交换操作的影响。

交换 $s_{0, i}$（为 1）和第 $s_{0, i + 1}$（为 0），实质上就是使 $s_{0, i}$ 减少 $1$，使 $s_{0, i + 1}$ 增加 $1$。如果 $s_{0, i}$ 是串里第 $j$ 个 1，那么 $dis_j$ 也减少 $1$，$dis_{j + 1}$ 增加 $1$。

发现交换操作对 $s$ 和 $dis$ 的影响是一样的，所以可以把 $\lceil\frac nk\rceil$ 都看成 $1$，$\lfloor\frac nk\rfloor$ 都看成 $0$，解决子问题 $\operatorname{solve}(k, n \bmod k)$。

发现 $\operatorname{solve}$ 的递归和欧几里得算法的递归是一样的，又因为 $n, k$ 互质，$k$ 维总是会变成 $1$，所以 $k = 1$ 的边界情况足够处理问题。递归深度为 $\log k$，我们就在 $O(n \log k)$ 的时间内构造出了 $s_0$。

题意

link

Task1

试判断能否构造并构造一个长度为 $n$ 的 $1 \sim n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同。

Task2

试判断能否构造并构造一个长度为 $n$ 的 $1 \sim n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同。

题解

神奇构造题。

Task1

首先考虑无解情况。

发现 $n$ 一定放在第一位，因为它无法带来贡献。（所以第一个前缀和为 $0$）

然后整个序列之和为 $\dfrac{n(n + 1)}2$，当 $n$ 为奇数时，这个和是 $n$ 的倍数，导致最后一个前缀和与第一个前缀和相同，无解。（$n = 1$ 的情况除外）

猜测 $n$ 为偶数的情况都有解，下面来构造。

我们可以考虑构造出排列 $a$ 在 $\bmod n$ 意义下的前缀和序列 $b$（实质上是 $0 \sim n - 1$ 的一个排列），通过差分的方法还原出排列 $a$。

由于 $b$ 的差分序列 $a$ 任意两项不能相等，所以我们考虑构造一个这样的序列：

$0, 1, -1, 2, -2, 3, -3, \dots, \frac n2 - 1, 1 - \frac n2, \frac n2$

这个序列的第 $i$ 项与 $b_i$ 同余，我们可以推出序列 $b$：

$0, 1, n - 1, 2, n - 2, 3, n - 3, \dots, \frac n2 - 1, n - \frac n2 + 1, \frac n2$

得出 $a$ 一定是这样的：

$n, 1, n - 2, 3, n - 4, 5, \dots, 2, n - 1$

Task2

首先考虑无解情况。

如果 $n$ 是除 $4$ 之外的合数，就可以找到两个不同的数 $p, q$（$1 < p, q < n$）使得 $pq \equiv 0 \pmod n$，又因为有 $n$ 的存在，至少有两个前缀积 $= 0$，所以无解。

然后对于 $n = 4$ 的情况，特判一下输出 $1, 3, 2, 4$ 即可。

猜测 $n$ 为质数的情况都有解，下面来构造。

首先，$1$ 一定是放在第一位的。（因为它对乘积没有影响）

然后，我们令前缀积分别为 $1, 2, 3, \dots, n - 1, 0$。

考虑当 $x$（排列第 $i + 1$ 项且 $i < n$）是什么时，$xi \equiv i + 1 \pmod n$。

$\begin{aligned} xi &\equiv i + 1 \pmod n\\ x &\equiv i^{-1}(i + 1) \pmod n\\ x &\equiv i^{-1}i + i^{-1} \pmod n\\ x &\equiv i^{-1} + 1 \pmod n\\ \end{aligned}$

因为 $n$ 是质数，所以在 $\bmod n$ 意义下，任意两个不同的数的逆元不同，所以得解。

题意

link

给你一个初始长度为 $n$ 的序列 $a$，你需要把这个序列分成几段，每一段长度都为偶数，且每一段前半段与后半段相同。

为了达成这个目标，你可以执行一个操作：

• 在序列的第 $p$ 个数后插入两个 $x$。

试问是否能在 $2n^2$ 次操作内达成目标。若能，给出操作方案与分段方案，否则报告无解。

题解

显然，如果有一个数出现次数是奇数，那么无解。因为操作无法改变数字出现次数的奇偶性，而每个数字都出现偶数次是满足要求的基本条件。

否则，大胆猜测都能构造出一组解，下面给出构造方案。

假设目前我们已经给前 $i - 1$ 个数分好段，目前要处理第 $i$ 个数。

1. 找到 $a_i$ 出现的下一个位置 $p$。

2. 把 $a_{i + 1}$ 到 $a_{p - 1}$ 之间的数都插入到 $p$ 后面，比如 $[9, 4, 8, 4, 1, 9, 2]$ 变成 $[9, 4, 8, 4, 1, 9, 4, 8, 4, 1, 1, 4, 8, 4, 2]$。

3. 这样，我们就成功划分了前面的一部分，并将未划分的长度缩小了 $2$。

题意

link

给你 $n$ 个大小为 $m$ 的不可重集，第 $i$ 个为 $a_i$。每个集合有一个权值，第 $i$ 个集合的权值为 $w_i$。

你需要选出两个下标 $i, j$（$1 \le i < j \le n$），满足 $a_i \cap a_j = \emptyset$。请求出所有选择方案中 $w_i + w_j$ 的最小值。

题解

容斥与双指针好题！

首先我们考虑如何判断一个集合是否与另外一个集合相交。这个很简单，直接扫一遍即可。

接着我们考虑如何判断一个集合是否与多个集合都相交。我们考虑使用容斥原理来解决这个问题。

先考虑一个集合是否与另外一个集合相交的情况。令一个集合为 $s$，另一个为 $s_1$，根据容斥原理，$\sum_{t \in s} (-1)^{|t|}[t \in s1]$ 这个柿子的值即为 $[s \cap s_1 = \emptyset]$ 的值。

然后考虑判断一个集合是否与多个集合都相交。令一个集合为 $s$，其他的分别为 $s_1, s_2, ..., s_k$，根据上式，与 $s$ 无交的集合个数为 $\sum_{i = 1}^k\sum_{t \in s} (-1)^{|t|}[t \in s_i]$，交换求和顺序得 $\sum_{t \in s} (-1)^{|t|}\sum_{i = 1}^k[t \in s_i]$。如果我们提前把每一个 $s_i$ 的所有子集都插入一个哈希表，上式就可以 $O(m2^m)$ 计算。因为 $m \le 5$，这已经足够快了。

然后我们回到原问题。我们把集合按照权值从小到大排序，并维护两个指针 $i, j$ 对应两个下标，初始时 $j$ 为它的最小可能值（即存在至少一个 $i$ 满足 $i < j$ 且 $a_i, a_j$ 无交），而 $i$ 在 $j$ 取最小的基础上取最小。

接着我们不断右移 $j$，且在右移 $j$ 的过程中 $i$ 只能向左移。为什么这样是对的呢？我们来证明向右移动 $i$ 一定是不优的。假设原本的两个下标为 $i, j$，新的两个下标为 $i', j'$（显然有 $i < i'$ 且 $j < j'$），因为集合已经按照权值排序，所以 $w_i \le w_{i'}, w_j \le w_{j'}$，进而得出 $w_i + w_j \le w_{i'} + w_{j'}$，所以向右移一定不优。

这样，两个指针都只会向一个方向移动，在移动的过程中动态维护哈希表即可，总共移动 $O(n)$ 次，时间复杂度为 $O(nm2^m)$。

题意

link

给定一个长为 $n$ 的不降序列 $a$，每次操作可以选择一个数 $i$（$1 \le i < n$），将 $a_i$ 和 $a_{i + 1}$ 替换为 $a_i \oplus a_{i + 1}$，现在需要破坏 $a$ 的不降，求最少操作次数或报告无解。

题解

诈骗题。

我们发现，如果存在一个数 $i$（$1 \le i \le n - 2$）满足 $a_i, a_{i + 1}, a_{i + 2}$ 最高位相同，将 $a_{i + 1}$ 和 $a_{i + 2}$ 替换为 $a_{i + 1} \oplus a_{i + 2}$ 即可破坏序列的不降。

而因为至多有 $\log_2 a$ 个不同最高位，所以如果 $n > 2\log_2 a$，那么一定存在一个 $i$ 满足上述要求，则操作次数为 $1$，否则直接暴力即可。

时间复杂度为 $O(n + \log_2^3 a)$。

题意

link

给你一个长度为 $2^n$，值域为 $[0, 2^n - 1]$ 的一个序列 $a$，每次你可以给出两个下标 $i, j$，并询问 $a_i \ \& \ a_j, a_i \ | \ a_j, a_i \oplus a_j$ 三个值其中一个。请你在不超过 $2^n + 1$ 次询问内求出序列 $a$。

题解

首先，我们如果求出了 $a$ 中任意一个值，我们就可以使用 $2^n - 1$ 次异或操作来求出其他所有值，这里我们考虑求出 $a_1$。

所以，我们可以先使用 $2^n - 1$ 次操作对于每一个满足 $1 \le i \le 2^n$ 的 $i$ 求出 $a_1$ 和 $a_i$ 的异或和，记作 $b_i$。（$b_1 = 0$，显然不用求）

然后，如果存在两个下标 $i, j$ 满足 $b_i = b_j$，那么就说明 $a_i = a_j$。有了 $b$ 数组，我们可以直接找到 $i$ 和 $j$。如果存在这样的一对 $i, j$，$a_i = a_j = a_i \ \&\ a_j$，我们就可以用一次操作简单的求出 $a_i$，并求出 $a_1 = a_i \oplus b_i$。

否则，$a$ 序列是一个 $0 \sim 2^n - 1$ 的排列。这意味着，$b$ 序列也是一个 $0 \sim 2^n - 1$ 的排列，所以，$b$ 序列一定包含一个 $1$ 和一个 $2^n - 2$，即存在两个下标 $i, j$ 使得 $b_i = 1, b_j = 2^n - 2$。$b_i = 1$ 意味着 $a_1$ 与 $a_i$ 除了后一位外都相同，$a_1 \ \& \ a_i$ 即为 $a_1$ 除了最后一位之外的结果；$b_j = 2^n - 2$ 意味着 $a_1$ 与 $a_j$ 除了最后一位外都不同，$a_1 \ \& \ a_j$ 即可得到 $a_1$ 的最后一位。$a_1$ 即为 $(a_1 \ \& \ a_i) \ | \ (a_1 \ \& \ a_j)$。

综上所述，我们最多使用 $2^n + 1$ 次询问即可求出 $a$。

题意

link

有一个长度为 $n$ 的 01 串 $a$，每次询问可以询问另一个长度为 $n$ 的 01 串 $b$，然后得到 $a$ 和 $b$ 有多少位相同。

在 $n \le 10^3$ 的限制下，请你使用不超过 $675$ 次询问求出 $a$。

题解

观察询问次数，我们发现 $675 \approx 10^3 \times \frac 23$，所以我们考虑用两次操作求出相邻的三个位置。

首先，我们可以用一次操作求出相邻的某三个位置里有多少个 $1$。这个很简单，在最开始时问一次全为 $0$ 的 $b$，令答案为 $cnt0$，然后每次询问将 $b$ 那三个位置改为 $1$ 再问一次，令答案为 $x$，$1$ 的个数（记为 $cnt1$）即为 $\frac{x - cnt0 + 3}2$。

然后，如果 $cnt1 = 0$ 或 $3$，三个位置是可以唯一确定的。

否则，我们考虑确定前两个位置，第三个位置根据 $cnt1$ 来确定。

首先我们考虑只有两个位置且知道 $cnt1$ 时应该如何确定这两个位置。

考虑问 $10$（设得到的结果为 $x$）和 $01$（设得到的结果为 $y$），会有以下三种情况：

• $x - y = 2$：此时这两个位置显然为 $10$。
• $y - x = 2$：此时这两个位置显然为 $01$。
• $x = y$：此时这两个位置可能为 $00$ 或 $11$，根据 $cnt1$ 判断即可。

回到原问题，我们考虑使用同样的思想，在最开始时问一次 $0101\dots$（就是 $0$ 和 $1$ 交错）的 $b$，然后每次询问将 $b$ 那两个位置取反再问一次，就使得每次确定两个位置的两次操作变成了一次。

然后还有剩余位置的话暴力即可。

题意

link

有一个游戏，这个游戏在一个平面直角坐标系的原点，$x,y$ 正半轴和第一象限中进行。

你与交互程序轮流下棋，交互程序执黑棋，你执白棋，黑棋先下，保证黑棋第一步下在 $(0, 0)$，且黑白棋都只能下在 $x, y$ 坐标都为自然数的点。

若出现横竖斜任意一个方向有连续的 黑白白白，则你赢。

你需要在四步之内取得胜利。

题解

我们考虑必胜的情况。

我们发现，黑空白白空 这种情况是必胜的，如果黑棋下第一个 空，白棋就下第二个 空；否则白棋下第一个 空。进而可以得出，如果场上同时出现两个 黑空白空空，这种情况也是必胜的，我们可以用两次操作达成胜利。

然后，第一步我们考虑下在 $(3, 0)$，这样就形成了一个 黑空空白空 的情况。然后，只要黑棋不下在 $(2, 0)$ 或 $(4, 0)$，我们必然能达成必胜情况。（如果黑棋下在 $(1, 0)$ 白棋就下 $(4, 0)$，否则白棋下 $(2, 0)$）

否则，不管黑棋下在 $(2, 0)$ 还是 $(4, 0)$，我们都下在 $(2, 2)$。这样 $(0, 0), (2, 2)$ 与 $(2, 0), (2, 2)$（或 $(4, 0), (2, 2)$）组成了两个 黑空白空空，也可以达成必胜情况。

综上所述，无论黑棋如何下，白棋都可以在四步之内达成胜利。

题意

link

有 $n$ 个格子排成一行，每个格子被涂成了红色或蓝色。

Alice 和 Bob 轮流进行操作，且 Alice 先手，Alice 每次操作选择两个相邻的格子，要求其中至少有一个是红色，然后把这两个格子涂成白色。Bob 每次操作选择两个相邻的格子，要求其中至少有一个是蓝色，然后把这两个格子涂成白色，最先不能操作的玩家输掉游戏。

现在给定初始局面，请问在他们进行最优操作的情况下，谁会获得胜利？

题解

博弈论好题。

下面称 Alice 为红方，Bob 为蓝方，红色是 Alice 的颜色，蓝色是 Bob 的颜色。

首先，两个玩家都会尽量把自己的颜色与对方的颜色一起消掉，这样是最优的。然后我们就可以得出一个结论：如果双方的颜色不一样，颜色多的玩家获胜。为什么呢？因为，只要两种颜色都存在，当前操作的玩家就一定可以达成自己的颜色与对方的颜色一起消掉的目的，所以每次操作两种颜色都会减少一个，颜色多的玩家获胜。

然后，我们考虑颜色相同的情况。

由于上面的最优策略，我们可以把这些格子分成若干极长双色相间连续段，且这些段不会相互影响（因为玩家无论怎样都不会删除两个自己的颜色）。显然，这个游戏的 SG 值就是每一个极长双色相间连续段的 SG 值的异或和。设一个长度为 $n$ 的双色相间连续段的 SG 值为 $SG(n)$，有：

$SG(n) = \begin{cases} n = 0 & 0\\ n = 1 & 0\\ n > 1 & \operatorname{MEX}_{i = 0}^{n - 2}\{SG(i) \oplus SG(n - i - 2)\} \end{cases}$

但是计算 $SG$ 值是 $O(n^2)$ 的，我们手写程序计算出部分 $SG$ 值可以发现，除了一些特例之外，$SG$ 值存在一个长度为 $34$ 的循环节，这样我们就可以打表 $O(1)$ 计算循环节。

题意

link

给出一个 $n$ 个点 $m$ 条边的无向连通图 $G$，还有一个长度为 $n$ 的 01 串 $s$，请你构造一条长度最多为 $4n$ 的路径（不一定简单）满足：对于每一个 $i$，如果 $s_i = 1$，$i$ 在路径中出现了奇数次；否则，$i$ 在路径中出现了偶数次。

题解

首先发现，所有情况都是有解的，进而推出所有 $G$ 是一棵树的情况都有解，而 $G$ 不是一棵树时，在 $G$ 的任意一棵生成树上求解即可。于是这个问题就被转化到了树上。

然后我们考虑把树定根（根定为 $1$ 号节点），递归求解问题。设 $S(u)$ 为一条 $u$ 子树内从 $u$ 出发又回到 $u$ 并令 $u$ 子树内除 $u$ 之外的其它节点都满足要求的路径序列，$S(u)$ 的构造方式是这样的：

1. 首先从 $u$ 出发。
2. 对于每一个 $u$ 的孩子 $v$ 执行以下步骤：
   1. 递归走进 $S(v)$，再回到 $u$。
   2. 如果 $v$ 不符合要求，走到 $v$ 再回到 $u$，这样 $v$ 经过次数的奇偶性就被改变了。

可以证明，这样构造出的 $S(1)$ 的长度最多为 $4n - 3$。

但是我们发现，$S(1)$ 还有一个 $1$ 号节点不一定满足要求。

如果 $1$ 号节点不满足要求，设 $1$ 号节点的任意一个孩子为 $x$，走到 $x$，回到 $1$ 再走到 $x$ 即可使一号节点满足要求。

这样构造出来的答案路径的长度最长恰好是 $4n$。

题意

link

给你三个整数 $m, n, k$，定义一个序列是合法的，当且仅当这个序列长度为 $n$，和为 $m$，且每个元素都是正整数。定义一个序列是优美的，当且仅当这个序列是合法的，存在一个子段和为 $k$。请问所有合法的序列是否都是优美的？

题解

首先有个很显然的转化，“所有合法的序列都是优美的”可以转化成“不存在一个序列是不优美的“，所以我们的目标就变成了尽量构造出一个合法且不优美的序列。

如果一个序列不优美，这个序列满足的条件就是不存在一个子段和为 $k$。看到子段和，我们考虑把序列做前缀和序列 $s$，显然 $0 = s_0 < s_1 < s_2 < \dots < s_n = m$，且不存在一对 $i, j(0 \le i < j \le n)$ 使得 $s_j - s_i = k$。继续考虑插板法，问题就变成了：在 $m$ 个小球中间插 $n + 1$ 块板，要求第 $0$ 个位置和第 $m$ 个位置都必须插板，且没有两块板之间距离为 $k$。我们求出能插的最多板数 $lim$，如果 $n + 1 \le lim$ 则可以。

然后发现 $\mod k$ 不同余的位置是互相独立的，所以这些位置可以被拆分成 $k$ 条互相独立的链，每条链相邻的两个位置不能都插板。那么如果一条链的长度为 $len$，则它最多能插 $\lceil len/2\rceil$ 块板。有 $m \bmod k + 1$ 条链长度为 $\lfloor m/k\rfloor + 1$，$k - m \bmod k - 1$ 条链长度为 $\lfloor m/k\rfloor$，于是 $lim$ 就可以 $O(1)$ 算出。最后可以证明，钦定 $0$ 和 $m$ 必须插板的限制对 $lim$ 是没有影响的。

题意

你占领了 $n$ 个据点，第 $i$ 个据点拥有 $a_i$​ 份口粮，需要至少 $b_i$​ 份口粮。

据点之间有 $m$ 条双向道路可供后勤部队输送口粮。后勤部队可以从任意据点出发，且处于任意据点时可以卸下或携带任意数量的口粮，但输送的过程中会造成损耗。具体而言，第 $i$ 条道路连接 $u_i, v_i$ 两个据点，后勤部队从其一端点出发到达另一端点时，其携带的口粮会损失 $w_i$ 份。特别地，若后勤部队携带的口粮不足 $w_i$ 份，则通过这条边后其不会携带任何口粮。

后勤部队是否存在一种口粮输送方案，使得每个据点的梯队都能在战斗结束前不撤离？

题解

首先考虑树的情况。发现最优解下一条边最多被后勤部队带着口粮经过一次，所以消耗口粮的一个上界是 $\sum w$。但是可能有一些边是不会被后勤部队带着口粮经过的，那么删掉这些边对答案不影响。所以，一棵树如果符合要求，要么口粮剩余大于等于 $\sum w$，要么这棵树可以被划分成两棵符合要求的子树。

考虑图的情况，发现上界就是这个图的最小生成树的上界，和判断树是否合法的方法一样，状压 DP 枚举子图转移即可。

题意

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

你可以选择两个整数 $x, y(\ge 2)$，然后将每一项 $a_i$ 对 $x,y$ 之中的一个数取模得到 $b_i$。

最小化 $b_1,b_2,\cdots,b_n$ 中不同的数值。

题解

首先模数可以取 $2$，所以最终答案至多是 $2$，所以问题转化为判断答案能否为 $1$。

首先给序列去个重，把 $1$ 的情况判掉，再随机选择 $i, j(i \ne j)$，钦定它们模同一个数，则这样钦定至少 $\frac 12$ 的概率是对的（如果答案为 $1$）。也就是，说多选几次，至少钦定一对正确的概率就足够大了，随机选择 $30$ 次，则至少钦定一对正确的概率为 $1-\frac 1{2^{30}}$，已经足够。

钦定 $i, j$ 之后，这一组的模数 $x$ 是 $|a_i - a_j|$ 的约数，可以直接枚举 $x$，我们要让每个数都变成 $b = a_i \bmod x$。

枚举所有 $i$，找出所有不满足 $a_i \bmod x = b$ 的数，对这些 $i$ 计算 $a_i - b$ 的 $\gcd$，即可判断是否存在 $y(y > 1)$ 使 $\forall i(a_i \bmod x \ne b), a_i \bmod y = b$。

时间复杂度 $O(30nD \log v)$，适当剪枝可以通过。

题意

给定一个包含至多 $10$ 个不同变量，运算包含与、或、异或、非、与非的逻辑表达式 $S$，变量使用大写英文字母命名，每个变量在 $S$ 中可能出现很多次，$|S| \le 5\times 10^5$。请你输出一个只包含与非运算的表达式 $T$，只包含 $S$ 里出现过的变量，使无论每个变量如何取值两个表达式的计算结果都相同，且 $|T| \le 5\times 10^5$。

题解

1. 用 bitset 快速求出每种情况中表达式的值，具体在表达式树上用 bitset 存下每种情况的值，合并时整个 bitset 合并。

2. 把每种结果为 $1$ 的情况用非和与表示出来，比如：

   原表达式有两个变量 A,B，$A = 1, B = 0$ 的情况原表达式中结果为 $1$，那么 $A$ 保持不变，$B$ 取反，再与起来，结果就是 $1$，(A&(~B)) 就是当且仅当 $A = 1, B = 0$ 时值才为 $1$ 的表达式。

3. 将结果为 $1$ 的所有情况使用上述方式生成的表达式用或连接，这样，在得到的新表达式中，这些变量取到任意一组原表达式中结果为 $1$ 的情况，表达式结果都为 $1$，否则为 $0$，这样就生成了一个和原表达式结果一致的新表达式，长度为 $O(n2^n)$ 级别。

4. 用与非（下图中为 #）代替非、与、或即可：

   1=A#(A#A)

   ~A=A#1

   A#B=~(A#B)

   A|B=(~A)#(~B)

这个变换过程是线性的，可行。

题目

题解

我们发现，$(15 + 1)^2 = 256$。然后考虑把每个串分成 $16$ 块，则干扰后的串至少有一块和原串一样。

然后我们考虑以下算法：给每一块开个桶，记录该块值为 $x$ 的串有哪些，这个预处理可以 $O(256n)$ 完成。然后对于每次查询，对于每段暴力在桶中查找，并用 bitset 比对。

然后我们考虑证明其时间复杂度的正确性。因为串是完全随机生成，所以这些串在同一段的每个桶里是均匀分布的，于是每个桶的期望大小是 $\frac n{2^{16}} \approx 6$，期望比对 $6 \times 16 = 96$ 次，所以这样足以通过本题。