Contest Info

practice link

Solutions

A. The Party and Sweets

签到题。

B. The minimal unique substring

签到题。

C. Permutation recovery

签到题。

D. Winding polygonal line

题目大意：给你平面上的 \(n\) 个点，无三点共线。另外给出一个长度为 \(n-2\) 的 LR 串。要求你将这 \(n\) 个点连成一条不自交的折线，使得每次转向时的方向恰为给出的 LR 串。

题解：首先求出凸包，如果第一个方向是 L，就选取逆时针的相邻两点作为前两个点；如果第一个方向是 R，就选取顺时针的相邻两点作为前两个点。可以发现这时无论怎么选取第三个点，第一个方向都一定满足了。之后去掉第一个点，再求一次凸包，以此类推。

时间复杂度 \(\mathcal{O}(n^{2})\)。

E. Strange device

题目大意：交互题。有一棵 \(n\leq10^{3}\) 个点的树，你最多询问 \(80\) 次，每次询问要给出序列 \(d_{1},d_{2},\cdots,d_{n}\)，交互器会回答你一个长度为 \(n\) 的序列 \(s\)，其中 \(s_{i}=1\)，当且仅当存在一个 \(j\neq i,dis(i,j)\le d_{j}\)，否则为 \(0\)。你需要还原这棵树。

题解：考虑先求出每个点到 \(1\) 的距离。如果询问 \((\frac{n}{2}-1,0,0,\cdots)\) 和 \((\frac{n}{2},0,0,\cdots)\)，我们既可以得到距离 \(\le\frac{n}{2}-1\) 的点，也可以得到距离恰为 \(\frac{n}{2}\) 的点。类似地，我们可以对 \(1\) 和所有距离为 \(\frac{n}{2}\) 的点分别询问距离 \(\frac{n}{4}-1\) 和 \(\frac{n}{4}\)。但是我们不能一直这样分开询问，事实上，在下一轮询问中，对于距离 \(0\) 和 \(\frac{2n}{4}\) 的点和距离 \(\frac{n}{4}\) 和 \(\frac{3n}{4}\) 的点，分别可以合并起来询问，以此类推。正确性就不赘述了。这一部分的总次数为 \(4\log n\)。

之后我们对每一位 \(i\)，将所有 \(i\) 位为 \(1\) 的点置为 \(1\) 来询问，这样我们就可以得到所有邻点中有 \(i\) 这一位的点。如果我们按照深度模 \(3\) 的余数询问 \(3\) 次，就可以保证这个邻点一定是父亲，这样在 \(3\log n\) 次询问中解决了该部分。

F. Density of subarrays

题目大意：本题的字符集为 \(\Sigma=1,2,\cdots,c\)。定义一个串的价值为 \(p\)，当且仅当其包含了所有长为 \(p\) 的串作为子序列，但是没有包含所有长为 \(p+1\) 的串。给你一个长为 \(n\) 的串，对于每个 \(p=0,1,\cdots,n\)，求出原串价值为 \(p\) 的子序列的数量。

题解：求 \(p\) 比较显然，定义一个好的串为包含所有字符的串，那么我们显然是从左到右贪心，最多能划分出的好的子串数量就是 \(p\)。接下来我们需要用两种方法求答案：

方法一

假设 \(dp[i][j]\) 表示第 \(i\) 个字符恰好是第 \(j\) 个极小好串的最后一个字符的方案数。那么最终答案 \(\ge j\) 的方案数就是 \(\sum_{i=1}^{n}dp[i][j]2^{n-j}\)，然后再容斥一下就能得到答案了。

\(dp[i][j]\) 的计算方法为：设 \(trans[i][j]\) 表示 \(i\) 到 \(j\) 中有多少个子序列，恰好在 \(j\) 处变成好的。我们先求出 \(t'[i][j]\)，表示 \(i\) 到 \(j\) 中好的子序列数量，那么就是每个字符至少出现一次，也就是说 \(\displaystyle{t'[i][j]=\prod_{ch\in\Sigma}\left(2^{cnt_{i,j,ch}}-1\right)}\)。然后再容斥，即 \(trans[i][j]=t'[i][j]-2t'[i][j-1]\) 即可。\(dp[i][j]=\sum_{k<i}dp[k][j]trans[k+1][j]\)。

时间复杂度 \(\mathcal{O}(\frac{n^{3}}{c})\)。

方法二

方法二较为简单，设 \(dp[i][j][S]\) 表示到位置 \(i\) 处，已有 \(j\) 个好的子串，不完整的子串的状态为 \(S\) 的方案数。

时间复杂度 \(\mathcal{O}(\frac{n^{2}2^{c}}{c})\)。

当 \(\frac{n^{3}}{c}=\frac{n^{2}2^{c}}{c}\) 时复杂度取最小值，即 \(c=\log n\)。时间复杂度 \(\mathcal{O}(\frac{n^{3}}{\log n})\)。有些卡常，方法一的 \(dp\) 可能需要做一些 cache 上的优化。