小火车

idea from 神秘人, data, solution from hehezhou

算法一

我会按照题意模拟！

直接枚举 $b_i=0,-1,1$，判断是否合法。

时间复杂度 $O(3^n)$，期望得分 $20$。

算法二

我会 meet in middle！

把所有数均匀分成两半，分别对两侧求出填上 $b$ 以后，能得到哪些和。

考虑找出将两侧合并出 $0$ 的方案，对左侧某个和为 $x$ 的组合查询右侧能否组合出 $-x$ 即可。

时间复杂度 $O(3^{n/2})$，期望得分 $40$。

算法三

我们还没用到 $2^n>p$ 呢！

题意等价于找出两个不相交的子集，使得集合元素和相等。这又等价于找出两个不相同的子集，使得集合元素和相等，后者到前者只需删去两个集合的公共元素即可。

那么这和 $2^n>p$ 有什么关系呢？实际上这个条件保证了本题一定有解，因为子集有 $2^n$ 个，而子集和只有 $p$ 种，由鸽巢原理可以得出一定有两个子集的和相同。

直接搜出所有子集和，找到两个相同的即可。

时间复杂度 $O(2^n)$，期望得分 $40$。

算法四

对于数据随机的部分，算法二和算法三简单改造以后都可以通过，背后的理论是生日碰撞。

对于算法二，在两侧随机 $O(\sqrt{p})$ 种方案，对于算法三，随机 $O(\sqrt{p})$ 个子集，有极大概率能找到解。

时间复杂度 $O(\sqrt{p}n)$，期望得分 $60$。

算法五

我们从鸽巢原理入手。

假想有 $p$ 个桶，分别编号为 $0$ 到 $p-1$，将子集放进子集和对应的桶。

那么 $p$ 个桶一共装了 $2^n$ 个子集，一定有一个桶至少装了两个子集，我们的目标就是找到这个桶，称包含超过一个子集的桶为目标桶。

更近一步，对于一个桶的区间 $[l,r]$，如果这些桶中装了超过 $r-l+1$ 个子集，那么 $[l,r]$ 中一定存在一个目标桶。

令桶区间 $[l,r]$ 中一共装了 $s_{l,r}$ 个子集。

如果 $s_{l,r}>r-l+1$，那么对于 $k\in [l,r)$，$s_{l,k}>k-l+1$ 和 $s_{k+1,r}>r-k$ 至少有一个成立，否则 $s_{l,r}=s_{l,k}+s_{k+1,r}\le r-l+1$ 矛盾。

因此，我们只需要能快速计算 $s_{l,r}$，就可以通过二分，在 $\log p$ 次询问内定位到某个目标桶。

而计算 $s_{l,r}$，同样使用 meet in middle，把数分为两侧，计算出两侧的所有子集和并提前排序后，每次询问双指针即可。单次询问时间复杂度 $O(2^{n/2})$。

定位到某个目标桶后，同样使用 meet in middle 找到对应子集即可。

时间复杂度 $O(2^{n/2}\log p)$，期望得分 $100$。

题外话

其实这道题是一篇论文的子问题。但是原论文中的做法比算法五复杂许多。

这题数据实在太难造啦！

造题人想破头只想出来一个构造：

1. 给定 $n$，令 $p=2^n-1$。

2. 先令 $a_i=2^i$，再随机取 $l\in [0,n-1]$ 使 $a_l$ 特殊的变为 $2^l-1$。

3. 随机打乱，随机将一些数变为相反数。

4. 随机取 $x$ 满足 $x$ 与 $p$ 互质，将所有 $a_i$ 变为 $a_{i}xmodp$。

这个构造的答案只有两组，是理论最低值。那么聪明的大家能否找到其他的构造方式呢？

神隐

idea from skip2004, data from skip2004, solution from skip2004, skyline

这题其实给出每条边的编号也是简单的，但是略微增加代码难度，就去了。

算法一

我们直接进行 $n-1$ 次询问，每次询问加入一条边，此时有一个连通块有两个点，就是这条边的两端。

询问次数 $n-1$，时间复杂度 $O(n^2)$，可以通过子任务 $1$。

算法二

如果一个询问包含一条边，那么这条边两边的点就会在一个连通块中，不然就不在。

考虑进行如下 $2\lceil {\log }_{2}n\rceil$ 次询问，第 $2i-1$ 与 $2i$ 次分别加入二进制第 $i$ 位为 $0/1$ 的边。

考虑两个点，如果恰好出现在其中 $\lceil {\log }_{2}n\rceil$ 个连通块中，就是树上一条边。

如果使用暴力的实现，时间复杂度为 $O(n^2{\log }_{2}n)$，可以通过子任务 $1,2$。

如果使用精细的实现（类似于算法四），时间复杂度为 $O(n{\log }_{2}n)/O(n{\log }_2^{2}n)$，可以通过子任务 $1,2,4$。

算法三

from p_b_p_b

对于任意两条相邻的边：

必须有询问只有第一条边没有第二条边，且有询问只有第二条边没有第一条边。

不然容易构造多种情况询问结果相同。

算法二显然是满足的，但是询问次数过多，我们可以使用以下方法：

选取 $[0,2^T)$ 中，二进制 $1$ 个数为 $\frac{T}{2}$ 的所有数作为编号进行二进制分组。

其余部分和算法二相同。

如果使用暴力的实现，询问次数为 $(1+o(1)){\log }_{2}n$, 时间复杂度为 $O(n^2{\log }_{2}n)$，可以通过子任务 $1,2,3$。

算法四

from skyline

注意到边是所有 $2k$ 次询问中恰好 $k$ 次在一个连通块中的点对（这里定义 $k$ 为询问次数的一半），以及任何点对最多一共出现在连通块中 $k$ 次，我们考虑以下搜索方法：

solve(当前限制下连通块交, 当前已经处理的询问轮数, 当前已经被要求强制在一个连通块里的轮数)

如果点集大小是 $1$，没有继续找其中点对的必要，可以立即返回。

如果当前已经被要求强制在一个连通块里的轮数达到 $k$，点集描述的就是一对边，加入答案并返回

如果不强制此轮在一个连通块里仍然可能最后 $k$ 轮在一个连通块，我们尝试不强制的情况进入下一层搜索（连通块交不变）

如果强制此轮在一个连通块里，我们使用时间戳+类似基数排序的手段来关于连通块交大小线性地对连通块做出划分并进入下一层搜索

我们下面将证明上面的策略是 $O(n{2}^k)$ 的。我们暂不考虑立刻返回的情形。由于点集大小大于 $1$，树上连通块中点数比边数多 $1$，从而点数不超过边数两倍。我们只需要证明总边数是 $O(n{2}^k)$ 的。假设当前已经处理的询问轮数是 $x$, 当前强制要求在一个连通块里的轮数是 $y$，如果不强制会传导所有的边，而强制会去掉一半的边（此轮询问中没有询问的边被割了没法进入下一层搜索，更严格的说明方法是所有 $C_{2k}^k$ 种询问策略在 $y$ 轮强制中都在待处理边集中的不超过 $C_{2k-y}^{k-y}\le \frac{C_{2k}^k}{2^y}$ 种，从中随机挑选 $n-1$ 个询问策略分给边期望有不超过 $\frac{n-1}{2^y}$ 条被保留，当然你也可以精心挑选符合条件的策略给边），所以进入 solve(any, x, y) 的边数是 $O(\frac{n{C}_x^y}{2^y})$ 的，而我们有限制 $(y\le x\le y+k,y<k)$, 满足此条件的 $\frac{C_x^y}{2^y}$ 之和是 $2^{k+1}-2$，故总边数是 $O(n{2}^k)$ 的，从而总点数也是 $O(n{2}^k)$。再加入考虑立即返回的情形，它们从不立即返回的点集来，而且每个点在进入下一轮递归的时候两种抉择各至多送入一个点，所以这样的点集大小和也是 $O(n{2}^k)$ 的。所以整个搜索中出现的点集大小和是 $O(n{2}^k)$ 的，而搜索内部是线性的，所以整个做法的总复杂度是 $O(n{2}^k)$的。

这是一份严格按照上述描述写的代码

这是一份不严格按照上述描述写，使用了一些常数优化的代码

算法五

from skip2004, hehezhou

考虑一个点什么时候是叶子，就是他度数为一，此时其在一半询问中单独一个点为连通块。

而删叶子是很简单的事情，因此我们可以一个个剥叶子。

剥完叶子我们开始反着加，此时考虑一个点的父亲是谁。

一个点在另外一半不是孤立点时候的询问所在的连通块，一定包含了它的父亲。也容易说明这些连通块的交集中只有它的父亲。

此时只要做树上 ${\log }_{2}n$ 个集合的交，其必定是其中一个集合顶部（深度最小的点），如果交唯一，一定是这些顶部深度最大的那个点。

时间复杂度 $O(n{\log }_{2}n)$。

结合算法二，可以通过子任务 $1,2,4$。

结合算法三，可以通过本题。

Border 的第五种求法

idea, data, solution from he_____he

出题人在此谢罪。被意料之外的简单做法过了。

算法 1

简单清新 $O(n^2)$ 暴力。记 $\text{occ}$ 表示子串在原串中的出现次数。预处理每个区间的子串的 $\text{occ}$ ，然后对每个询问，暴力枚举 border 长度，统计答案即可。期望得分 $10$ 分。

算法 2

A 性质有什么用？可以发现，对两个不同位置，长度大于 $O(\log n)$ 且相等的区间，其代表的两个子串几乎一定不同！ 这说明 border 长度不超过 $O(\log n)$ ！我们只需枚举不超过 $O(\log n)$ 的长度即可。为了加快 $\text{occ}$ 的求值速度，可以选择建一个 SAM ，在枚举 border 长度的时候顺便在 SAM 的 DAG 上走，定位每个 border 所在的 SAM 节点。结合算法 1 ，期望得分 $20$ 分。

算法 3

要不，猜个结论？众所周知，一个区间的 border 能被分成 $O(\log n)$ 段等差数列。那么一个区间 border 的 $\text{occ}$ 有这个性质吗？遗憾的是，并没有。但是 $\text{occ}$ 实际上能被分成 $O(\sqrt{n}\log n)$ 段等差数列（证明先鸽着，说不定实际上是 $O(\sqrt{n})$ ）。用基本子串字典求出 border 序列后寻找这些等差数列，在 $f_i=i$ 的时候即可求出答案。时间复杂度 $O(q\sqrt{n}\log n)$ ，结合算法 1,2 后，期望得分 $45$ 分。

算法 4

重新观察 border 的性质，我们回到最初的起点：找到所有 $1\le i\le r-l+1$ 使得 $s[l,l+i-1]$ 为 $s[1,r]$ 的后缀。那么我们可以找到 $s[l,l],s[l,l+1],\dots ,s[l,r]$ 在 SAM 的 DAG 上对应的链，答案即为这些点中作为 parent 树上 $s[1,r]$ 的祖先的那些点的 $\text{occ}$ 之和。

考虑该题中提到的 DAG 剖分，我们可以把链分成若干段重链上的区间。现在问题就相当于：每个 SAM 节点在 DAG 结构上有一个标号，有一个权值 $f_{\text{occ}}$ ，需要多次查询某个点到根的链上，某个区间的权值之和。等价于一个二维数点。共 $O(n)$ 个点，$O(q\log n)$ 次查询，总复杂度 $O(n\log n+q{\log }^{2}n)$ ，期望得分 $100$ 分。

题外话

本题说明，我们能够将一个区间中所有 border 的信息定位到 SAM 节点上，相较于基本子串字典，我们虽然没有得到 border group 的表示，但我们得到了另一个角度的信息。或许我们以后能获得更有价值的信息？