小火车

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\gt p$ 呢！

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

那么这和 $2^n\gt 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}\gt r-l+1$，那么对于 $k\in[l,r)$，$s_{l,k}\gt k-l+1$ 和 $s_{k+1,r}\gt r-k$ 至少有一个成立，否则 $s_{l,r}=s_{l,k}+s_{k+1,r}\leq 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_ix\bmod p$。

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

神隐

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

题外话

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

面基之路

idea from he_____he, data,solution from hehezhou

算法一

首先需要注意到最重要的结论：题意等价于所有人走到同一位置所需最短时间。证明只需要让所有网友在面基成功之后跟随 hehe 蚤行动即可。

对于子任务 $1$，不难发现最终汇合点一定在某个点上或某条边正中。如果汇合点在边的非中点位置，移动到端点或中点，一定有一种更优。

只需要求出会合到每一个位置的答案即可。时间复杂度 $O(k(n\log n+m))$，期望得分 $30$。

算法二

对于子任务 $2$，不难发现 $T$ 就是最远点距离除以二。

首先会合时间不可能更早，因为 $1$ 和最远点的距离达到了 $2T$。而只需要让所有人移动到 $1$ 和最远点的带权中心就是一组合法方案。

算法三

首先汇合点在点上的情况是简单的，考虑汇合点在边上的情况。

定义边的左右侧是它的两个端点，枚举每个人是从哪一侧进入这条边的，每侧只需要考虑最晚进入的人即可，答案不难计算。

时间复杂度 $O(m2^k+kn\log n)$，期望得分 $85$。

算法四

由于每侧只需考虑最晚进入的人，对于每条边，一定存在一种最优方案，将所有人按照到达左侧时间排序后，一个前缀从左侧进入而剩余的后缀从右侧进入。

时间复杂度 $O(kn\log n+mk\log k)$，期望得分 $100$。

bonus

如果 hehe 蚤的速度是 $a$ 而网友们的速度是 $b$，这个问题又该怎么解决呢？

这个问题会在数日后被加入 uoj 题库。

机器人表演

idea, data from djq_cpp, solution from hehezhou

本题改编自 CPIdeas (https://codeforces.com/blog/entry/104374) 生成的题面：

You are given a string S consisting of 0 and 1. You can do the following operation on S any number of times: Choose a non empty substring T of S, and append 0 to the beginning and 1 to the end of T. The resulting string will be S again. How many different strings will S be after the operations? Find the count
modulo 998244353.

算法一

我会状压！

接下来令左括号对应 0，右括号对应 1，合法括号前缀是满足任意前缀 0 不少于 1 的串，合法括号串是 01 个数相等的合法括号前缀，$A$ 和 $B$ 可以合并出 $C$ 等价于 $C$ 可以被划分为两个子序列分别等于 $A$ 和 $B$。

首先我们考虑给定一个串 $T$，判断其是否可以通过合并串 $S$ 和某个括号串得到。这可以在 $O(|S||T|)$ 的时间内完成，具体的，设 $f_{i,j}(i\geq j)$ 表示是否存在一个合法括号前缀使得它和 $S[1:j]$ 可以合并出 $T[1:i]$。考虑转移，有以下两种转移：

1. $f_{i,j}\to f_{i+1,j+1} (S_{i+1}=T_{j+1})$

2. $f_{i,j}\to f_{i+1,j} (a_{i+1}\geq b_{j})$

其中若 $T_i$ 是左括号，$a_i=a_{i-1}+1$，否则 $a_i=a_{i-1}-1$，$b$ 是定义在 $S$ 上的类似序列。第一种转移显然正确，第二种转移是因为：所有合并方案中，合法括号前缀的两种数量都是固定的。

如果 $f_{|T|,|S|}=\text{true}$ 且 $a_{|T|}=b_{|S|}$，则串 $T$ 可以通过合并串 $S$ 和某个括号串得到。

对应这个 dp，我们可以列出求解原题的状压 dp。$dp_{i,j,V}$ 表示已经填好了 $T$ 的前 $i$ 位，$f_{i,k}$ 等于 $V$ 的第 $k$ 位，$a_i=j$，转移按照上述转移式对应转移即可。

时间复杂度 $O(2^nn(n+t)^2)$，可以通过子任务 $1,2,4$，期望得分 $45$。

如果省略无用状态，可以额外通过子任务 $3$，期望得分 $60$。

算法二

我是打表大师！我打表转移找到规律了！

规律就是：对于固定的 $S,i,j$，非零 $dp_{i,j,V}$ 两个后继状态的 $V$ 的最高位只和当前 $V$ 的最高位有关。

可以只记录 $V$ 的最高位，状态数减少为 $O(n(n+t)^2)$。

时间复杂度 $O(n^2(n+t)^2)$，进一步得到转移规律可以做到 $O(n(n+t)^2)$，期望得分 $75\sim 100$。

算法三

我喜欢严谨做题！我要证明这个结论！

先注意到几个重要性质：

1. 两个合法括号前缀合成的串一定是合法括号前缀。考虑定义不难得出。

2. 若 $f_{i,j}=1$，则有 $a_i\geq b_j$。考虑转移或考虑 dp 意义均不难得出。

考虑当前已经匹配了前 $i$ 位，$a_i$ 确定，并且可以匹配的 $S$ 的最长前缀是 $k$，考虑在算上第 $i+1$ 位 $x$ 以后，可以匹配的 $S$ 最长前缀：

1. $S_{k+1}=x$：显然新的最长前缀是 $k+1$。

2. 否则若 $x=0$（即左括号） 或 $a_i\gt b_k$：那么 $a_{i+1}\geq b_k$，新的最长前缀是 $k$。

3. 否则有 $x=1$（即右括号）且 $a_i=b_k$，这种情况较为复杂。先给出结论：新的最长前缀 $k'=\max_{t\lt k,b_{t}\lt b_k} t$。第一步证明这个前缀是合法的：不难发现 $S[k'+1,k]$ 是一个合法括号前缀，否则就存在更大的位置满足 $b_{t}\lt b_k$。首先证明 $f_{i,k'}=\text{true}$，只需要将 $f_{i,k}$ 对应的合法方案中，$S[k'+1,k]$ 对应的子序列划为合法括号前缀部分，由性质 $1$ 我们就得到了 $f_{i,k'}$ 对应的一组方案，因此 $f_{i,k'}=\text{true}$ 且可以转移到 $f_{i+1,k'}$。然后我们证明不存在更长的前缀 $x$ 可以匹配 $T$ 的前 $i+1$ 个位置，否则 $b_x\geq b_k\gt a_i-1=a_{i+1}$，与性质 $2$ 矛盾。

至此我们证明了这个结论。

期望得分 $100$ 分。

稳健型选手

idea,data,solution from xyr2005

谢罪！谢罪！谢罪！谢罪！谢罪！

算法一

我会暴力！状压当前剩下哪些数，复杂度 $O(n2^n+q)$，可以通过子任务一获得 $10$ 分。

算法二

我会观察性质！先考虑单组询问。

首先，如果 $n$ 是奇数，那 QAQ 蚤会在最后一次取最后一个数，转化成前 $n-1$ 个数的问题，容易发现这是最优的。所以我们可以假设 $2\mid n$。

考虑 QAQ 蚤取的数的集合要满足什么条件。令序列 $b_i=0/1$ 表示这个位置最终 QAQ 蚤 取不取。

那 QAQ 蚤可以贪心每次取 $b_i=1$ 的最靠前的那个，那么可以发现 一个 $b$ 合法当且仅当 $\sum b_i=\frac n2$ 且 $\forall i\in[1,n],\sum_{j=1}^ib_j\le \lceil\frac i2\rceil$

我们可以 $dp_{i,j}$ 表示考虑了前 $i$ 个元素，总共取了 $j$ 个，和最大是多少，转移时保证 $j\le \lceil\frac i2\rceil$ 即可。

复杂度 $O(n^2q)$ ，可以通过子任务一二获得 $20$ 分。

算法三

考虑优化算法二。

可以使用反悔贪心，从前往后扫，维护 QAQ 蚤取了哪些数。

每次加进来两个数 $x,y$，首先假设 $x,y$ 都取了，这时候取了的数的总数是 $\frac{i}2+1$，再删掉一个最小的已经取了的数。

用堆维护上述过程，复杂度 $O(nq\log n)$ ，可以通过子任务一二三获得 $40$ 分。

算法四

我们发现，前 $2i$ 个取了 $\le i$ 个 $\Leftrightarrow$ 后 $2i$ 个取了 $\ge i$ 个。

于是算法三也可以倒着来做，从后往前扫，维护 QAQ 蚤没取哪些数。

每次加进来两个数 $x,y$，首先假设 $x,y$ 都没取，这时候取了的数的总数是 $\frac i2-1$，再取一个最大的没取的数。

于是我们现在可以在 $O(\log n)$ 复杂度内，向前加两个数，向后加两个数，使用不删除莫队维护。

复杂度 $O(n\sqrt q\log n)$，可以通过子任务一二三四获得 $70$ 分。

使用压位trie/veb 维护，复杂度 $O(n\sqrt q\log_wn)/O(n\sqrt q\log\log n)$，期望得分 $70$ 分，实际得分 $100$ 分。

算法五

继续优化算法四。

使用分治，用主席树对 $[l,mid]$ 的每个后缀维护取了哪些数，对 $[mid+1,r]$ 的每个前缀维护没取哪些数。

然后考虑合并 $[x,mid]$ 和 $[mid+1,y]$，那会发生的变化是，$[x,mid]$ 中一些取了的数现在不取了，$[mid+1,y]$ 中一些没取的数现在取了。假设 $[x,mid]$ 中发生变化的数的集合是 $S$，$[mid+1,y]$ 中发生变化的数的集合是 $T$，那么 $|S|=|T|$ ， $\max S< \min T$，$S$ 是一段前缀，$T$ 是一段后缀。于是我们二分 $k$ ，找到最大的 $k$ 满足左边第 $k$ 小 $<$ 右边第 $k$ 大，然后就知道了 $S,T$，于是做完了。

复杂度 $O((n+q)\log^2n)$，可以通过子任务一二三四五获得 $100$ 分。

经过一周的准备， Public Judge 即将投入运营！

PJ Round #1 将在 2022 年 4 月 3 日 8:30 举行！比赛将进行 4.5 小时，共 3 道题，OI 赛制。难度可以近似为省选。

本次模拟赛的搬题人为 cdw, hehezhou ，组题人为 p_b_p_b 。另外，特别感谢 Qingyu 和其他所有参与者对 OJ 搭建和题源筛选做出的巨大贡献。

赛后会公开原题链接和题解链接。

参加本场比赛将有机会获得 pjudge 抱枕！获奖条件的 SHA256 为 bc082bd4ee6e645bccf44197d13a0da2d23138b26c67e37044859188305a7aed 。比赛结束后将公布条件。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

欢迎加入 Public Judge 用户群（1009677675）。

OJ 的网址是 pjudge.ac。

后续通知将在群里发布，如果你有想提出的建议或是发现 OJ 的 bug，可以向 hehezhou 或 p_b_p_b 汇报。

upd: Round #1 结束啦

echo -n "没有 没有 没有 别想了" | sha256sum
bc082bd4ee6e645bccf44197d13a0da2d23138b26c67e37044859188305a7aed -

随机薅羊毛

idea, std from xuanyiming data, solution from hehezhou

算法一

我会 $n=2$！

设从 $1$ 号机开始的期望为 $x_1$，$2$ 号机开始的期望为 $x_2$。

如果 $1$ 号机抽奖失败，则接下来的过程就是从 $2$ 号机开始抽奖，反之同理。

因此 $x_1=(1-p_1)x_2+1, x_2=(1-p_2)x_1+1$。

解得 $x_1=\frac{2-p_1}{p_1+p_2-p_1p_2},x_2=\frac{2-p_2}{p_1+p_2-p_1p_2}$。

算法二

上面的方程组在 $n$ 更大的情况同样可以被列出来！

具体的，设从 $i$ 号机开始抽奖的期望是 $x_i$，那么有：

$$x_i=\frac{(1-p_i)\sum_{j\neq i}x_j}{n-1}+1$$

列出系数高消即可，时间复杂度 $O(n^3)$，期望得分 $40$。

算法三

令 $s=\sum_{i=1}^n x_i$，答案即为 $\frac{s}{n}$，那么上述方程可简化为：

$$x_i=\frac{(1-p_i)(s-x_i)}{n-1}+1$$

简单变形后化为：

$$x_i=\frac{(1-p_i)s+n-1}{n-p_i}$$

将 $n$ 个方程求和，整理得：

$$s=s\sum_{i=1}^n\frac{1-p_i}{n-p_i}+(n-1)\sum_{i=1}^n\frac{1}{n-p_i}$$

这是一个一元一次方程，简单求出系数即可。

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

重构元宇宙

idea, std1, solution1 from vfleaking data, std2, solution2 from hehezhou

算法一

我会 $k=1$！

先确定 $0$ 号点的坐标为 $0$，找一个与 $0$ 号点距离非 $0$ 的点，不妨设为 $1$ 号点，令其坐标为 $d(0,1)$。

对于其他点，求出与这两个点的距离，即可简单分讨出坐标。

算法二

我会 $n=3$！

同样先确定两个点的坐标，简单解出第三点坐标即可。

算法三

考虑逐个点加入，同样令 $0$ 号点坐标均为 $0$，维护出当前这些点可以嵌入空间的最小维数 $k$ 以及一组坐标，同时维护一组含 $0$ 号点的大小为 $k+1$ 的点集 $\{x_i\}_{i=0}^k$，使得这个点集可以嵌入空间的最小维数同样为 $k$。

设当前加入点为 $x'$，考虑列出方程：

$$\sum_{i=0}^k(x_{t,i}-x'_i)^2=d^2(x',x_t)~~(t\in[1,k])$$

注意到 $d^2(0,x)=\sum x_i^2$，因此：

$$\sum_{i=0}^{k-1} x_{t,i} \cdot x'_i=-\frac{d^2(x',x_i)-d^2(0,x)-d^2(0,x_t)}{2}~~(t\in[1,k])$$

由于这个点集的性质，这 $k$ 个方程线性无关，可以使用高消唯一确定 $x'$ 的前 $k$ 维坐标。如果此时 $\sum_{i=0}^{k-1}x_i^{'2}\lt d^2(0,x')$，则说明空间的维数需要增加 $1$，简单的将 $x'_k$ 设为左右差的平方根，并将 $x'$ 加入点集即可。

时间复杂度 $O(n^4)$，交互次数不超过 $n(k+1)$，期望得分 $70$。

算法四

考虑维护出矩阵的逆，高消可以认为是将向量乘上逆矩阵。

每次计算出加入点集的新点后，相当于在原矩阵的下方增加了一行。新的逆矩阵可以在旧逆矩阵的基础上，以 $O(n^2)$ 的开销计算得到。

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

算法五

vfk 咕咕咕。

UPD: 更新了 https://vfleaking.blog.uoj.ac/blog/7612

磁球与磁棍

idea, solution from jacder, std, data from djq_cpp

算法一

暴力枚举删哪些边然后判。时间复杂度 $\tilde O(2^n)$，期望得分 $10$ 分。

算法二

考虑 DP。

令 $f[i][j][k][l]$ 表示子树 $i$ 被切成 $j$ 块，结点 $i$ 所在的连通块叶子深度均为 $k$，$i$ 和其父结点的连边情况是 $l$ 是否为合法的状态，转移可以直接树上背包。

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

算法三

为了达到线性复杂度，我们需要将 $j$ 这一维优化掉。

对于原问题，容易发现当 $k < n$ 时，若存在切成 $k$ 个连通块的方案，则一定存在切成 $k+1$ 或 $k+2$ 个连通块的方案：称一个点是自由的当且仅当它的颜色与它所在连通块的叶子颜色不同，则此时必然存在一个自由的点；若它的度为 $2$，则可删两条边构造出 $k+2$ 的方案，否则可删一条边构造出 $k+1$ 的方案。

进一步地，若 $k \not= n - 3$，则要么有度数为 $2$ 的自由点，要么有至少两个度数大于等于 $3$ 的或一个度数大于等于 $4$ 的自由点。这些情况均可构造出 $k+2$ 的方案。而 $k = n - 1$ 必然无解。

这意味着可以直接令 $dp[i][j][k][l]$ 表示子树 $i$，子树内连通块数模 $2$ 余 $j$，根所在连通块叶子颜色为 $k$ 根和父结点连边状况为 $l$ 时子树内的最小连通块数，容易做到 $O(1)$ 转移。

std 中还原方案采用的方式是构造出最小值对应的方案再用上述的调整算法调整。直接用 dp 值自顶向下还原应该也是可行的，但需要一些讨论。

再见，辛丑！

转眼间，魔幻的 2021 就结束了，虎年到来了，vjudge 蜀汉的五虎上将跨越千年时空，前来 UOJ 庆祝新年，并注册为了 UOJ 用户 GuanYunChang, ZhangYiDe, ZhaoZiLong, MaMengQi, HuangHanSheng。

你将和这五位五虎上将一起，策划或参与各式各样的活动！

我们将于 $1$ 月 $30$ 日下午 13:00 到 18:00 举办一场 Goodbye Xinchou 比赛。比赛时间为 5 小时，共 5 道题。

赛制为 OI 赛制，有简单题也有有趣题，还有有趣的简单题，欢迎各位选手来玩！

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

赛制采取 OI 赛制，这也意味着只计入最后一次提交结果。这场比赛有很多有意思的题目，大家一定不要错过！

出题人：vfleaking, LMoliver, vectorwyx, orbitingflea, byqx, djq_cpp

这场成绩将计入 rating。

参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码为 6ca9cedbed07373bd30c7044928bd6c942babe696570b854af15df5e7d54c857。比赛结束后将公布条件。

UPD: 恭喜前5名的选手！

1. zhoukangyang
2. Itst
3. hos_lyric
4. csy2005
5. AKEE

echo -n "全场倒数第二个计入最终成绩的100分提交，如有多个取排名最高者。" | sha256sum
6ca9cedbed07373bd30c7044928bd6c942babe696570b854af15df5e7d54c857  -

恭喜 tzc_wk 获得 uoj 抱枕！