目录
补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 2 | 0 | 0 |
| B | 0 | 0 | 0 |
| C | 2 | 0 | 0 |
| D | 2 | 0 | 0 |
| E | 0 | 0 | 0 |
| G | 2 | 1 | 0 |
| I | 0 | 0 | 0 |
| J | 2 | 0 | 2 |
| K | 0 | 0 | 0 |
题解
A. Browser Games
题意
给定 $n$ 个字符串，对 $i=1\sim n$，找出一个最小的前缀集合，满足：
对前 $i$ 个字符串都至少有一个前缀位于该集合且对于后面的 $n-i$ 个字符串都不存在前缀属于这个集合。
数据保证不存在一个字符串是另一个字符串前缀的情况，且内存限制为 $32\text{ megabytes}$。
题解
首先不考虑内存限制，可以对所有串建立字典树，并用叶子结点代表每个字符串。
然后问题转化为从树上选择最少的结点集合，使得前 $i$ 个字符串至少有一个祖先结点被选中，且后 $n-i$ 个字符串不存在祖先结点被选中。
不难发现，如果一个结点的子树中叶子结点都属于前 $i$ 个字符串，则以该结点为根的子树答案为 $1$。否则该结点答案等于所有儿子结点答案之和。
建立字典树后依次处理 $i=1\sim n$ 的询问，动态更新每个结点的子树中的后 $n-i$ 个字符串个数以及以该结点为根的子树答案。
每次询问的答案记为字典树根节点的答案，注意特判 $i=n$ 的询问，因为前缀不能是空串。
然后考虑内存限制，注意到只有一个儿子结点的结点都是可以压缩的，于是树上的关键结点个数可以卡到 $O(n)$。
最坏的情况是完全二叉树，这时节点个数是 $2n-1$，于是开两倍空间即可。
关于建树，可以递归构建，如果当前结点的字符串个数为 $1$ 则直接返回。
否则找到最小的当前结点的所有字符串的非公共前缀长度，然后划分字符串，继续递归，同时记录非公共前缀的位置用于后续更新操作比较。
C. Dance Party
题意
给定 $n\times 2$ 的二分图。对左部每个点，仅和右部 $k_i$ 个点不连边。求二分图最大匹配。
题解
设 $k=\max_{i=1}^n k_i$。
先进行预匹配，每个左部点任选一个还未被匹配且有连边的右部点匹配，可以用 $\text{set}$ 维护所有未匹配的右部点，时间复杂度 $O(nk\log n)$。
接下来剩下的未匹配的点一定不超过 $k$ 个，对每个点考虑匈牙利算法匹配， 总时间复杂度为 $O(km)$。
$O(m)\sim O(n^2)$，考虑优化。假定现在需要对点 $i$ 进行匈牙利算法，将右部与点 $i$ 不相邻的点染黑，其余右部点染白。
对除点 $i$ 以外的左部点，仅保留与黑点相关的连边，这样 $O(m)\sim O(nk)$，总时间复杂度 $O\left(nk^2\right)$ 足以通过此题。
关于算法的正确性，假设在原图上存在一条从 $i$ 出发的增广路，且增广路上除了 $i$ 以外有其他点的失配边指向白点。
找到增广路上的最后一个白点，直接将 $i$ 的失配边指向该点然后保留原增广路的剩余部分也可以一条增广路。
同时该增广路上除了 $i$ 其他点的失配边都指向黑点。因此只要原图存在一条从 $i$ 出发的增广路则只保留与黑点相关的连边也可以得到一条增广路。
D. Diameter Counting
题意
求所有 $n$ 标号树的直径和。
题解1
考虑求树的直径的过程，可以先删去所有叶子结点，得到一棵新树，称为一次操作。然后再不断对新树进行操作，知道最后剩下一个或两个结点。
此时如果只剩下一个结点，则树的直径为操作次数 $\times 2$。如果剩下两个结点，则树的直径为操作次数 $\times 2+1$。
考虑通过逆算法反向构建树。设 $f(i,j)$ 表示有 $j$ 个叶子结点的 $i$ 标号树个数，假设上一步操作删除了 $k(k\ge j)$ 个叶子。
于是问题等价于给这 $k$ 个叶子找一个父结点，使得原来的 $j$ 个叶子结点至少有一个儿子。
同时对于这 $i+k$ 个结点，标号是任意的，对所有 $i+k$ 标号树而言，删去 $k$ 叶子结点得到的树的标号方式实际上有 ${i+k\choose i}f(i,j)$ 种。
设 $g(i,j,k)$ 表示长度为 $k$ 且每个位置有 $i$ 种可选取值且特定的 $j$ 个值至少出现一次的序列个数，于是有
$$ f(i+k,k)\gets g(i,j,k)f(i,j){i+k\choose i} $$
接下来考虑求 $g(i,j,k)$，可以考虑序列前 $k-1$ 位，如果此时 $j$ 个特定值都出现了至少一次，则第 $k$ 位可以任取，于是有
$$ g(i,j,k)\gets i\times g(i,j,k-1) $$
如果前 $k-1$ 位只有 $j-1$ 个特殊值出现了至少一次，则显然前 $k-1$ 位的取值只有 $i-1$ 种，同时要从 $j$ 个特殊值中确定一个放在第 $k$ 位，有
$$ g(i,j,k)\gets j\times g(i-1,j-1,k-1) $$
最后设 $h(i,j)$ 表示有 $j$ 个叶子的 $i$ 标号树的直径之和。同样假设上一步操作删除了 $k(k\ge j)$ 个叶子。
考虑原有的树的直径和操作带来的直径 $+2$ 的新贡献，于是有
$$ h(i+k,k)\gets g(i,j,k){i+k\choose i}(h(i,j)+2f(i,j)) $$
另外所有 $h(i+k,k)\gets 2f(i,j)g(i,j,k){i+k\choose i}$ 也可以等价于 $h(i,j)\gets 2f(i,j)$。时空间复杂度 $O\left(n^3\right)$。
题解2
设 $f(i,j)$ 表示深度为 $j$ 的 $i$ 标号树个数，$g(i,j)$ 表示深度不超过 $j$ 的 $i$ 标号树个数。
对一个直径为 $2d+1$ 的 $n$ 标号无根树，可以沿着直径的中心边切开，得到两个深度为 $d$ 的有根树。
设 $1$ 号点所在的有根树大小为 $i$，考虑为他分配 $i-1$ 个编号，于是直径为 $2d+1$ 的 $n$ 标号无根树个数为
$$ \sum_{i=1}^{n-1}f(i,d)f(n-i,d){n-1\choose i-1} $$
对一个直径为 $2d$ 的 $n$ 标号无根树，可以认为是根节点连接至少两个深度等于 $d-1$ 的有根树。
利用容斥，用深度为 $d$ 的 $n$ 标号有根树个数减去根节点仅连接一个深度为 $d-1$ 的有根树个数的情况。
根节点仅连接一个深度为 $d-1$ 的有根树可以认为是由一个深度不超过 $d-1$ 的有根树根节点连接一个深度等于 $d-1$ 的有根树得到的。
于是直径为 $2d$ 的 $n$ 标号无根树个数为
$$ f(n,d)-\sum_{i=1}^{n-1}f(i,d-1)g(n-i,d-1){n\choose i} $$
接下来考虑计算 $f(i,j),g(i,j)$。$f(i,j)$ 难以直接计算，但显然有 $f(i,j)=g(i,j)-g(i,j-1)$，于是只需要计算 $g(i,j)$。
对于深度不超过 $j$ 的 $i$ 标号树个数，可以先分配一个编号给根结点，然后从与根节点相连的子树中找到编号最小的结点所在的子树。
设子树大小为 $k$，对该子树，他深度不超过 $j-1$，显然有 $g(k,j-1)$ 种。另外需要从剩余 $i-2$ 个编号再分配 $k-1$ 个编号给子树。
对于余下的 $n-k$ 个点，深度仍然不超过 $j$，但根节点编号已经分配，所以总数为 $\frac {g(i-k,j)}{i-k}$。于是有
$$ g(i,j)=\sum_{k=1}^{i-1}i{i-2\choose k-1}g(k,j-1)\frac {g(i-k,j)}{i-k} $$
时间复杂度 $O\left(n^3\right)$，空间复杂度 $O\left(n^2\right)$。
G. Game of Death
题意
一个游戏，有 $n$ 名玩家。每个玩家等概率选择一名除自己以为的人进行射击，射击的命中率为 $p$。
对每个 $k=1\sim n$ ，询问最后存活 $k$ 人的概率。
题解
设 $f(k)$ 表示固定 $k$ 个人的集合，这 $k$ 个人全部死亡的概率。$g(k)$ 表示固定 $k$ 个人的集合，死亡的人是这个集合的子集的概率。
首先考虑计算 $g(k)$，事实上可以把所有人分成两种人，一种是在这个 $k$ 人集合中的人，记为 $A$ 类人。另一种记为 $B$ 类人。
于是只需要保证不杀死 $B$ 类人即可。于是对 $A$ 类人，这个概率为 $1-\frac {p(n-k)}{n-1}$。而对于 $B$ 类人，这个概率为 $1-\frac {p(n-1-k)}{n-1}$。
于是有
$$ g(k)=\left(1-\frac {p(n-k)}{n-1}\right)^k\left(1-\frac {p(n-1-k)}{n-1}\right)^{n-k} $$
同时有 $g(k)=\sum_{i=0}^k {k\choose i}f(i)$，根据二项式反演，得 $$ f(k)=\sum_{i=0}^k (-1)^{k-i}{k\choose i}g(i)=k!\sum_{i=0}^k\frac{(-1)^{k-i}}{(k-i)!}\frac{g(i)}{i!} $$ 卷积计算即可，最终 $k$ 人死亡的答案为 ${n\choose k}f(k)$。时间复杂度 $O(n\log n)$。
J. Illuminations
题意
给一个凸多边形，和凸多边形外侧若干个点，每个点作为一盏灯，向四面八方发出光线，让用最少的点照亮平面除凸包内部外所有区域，如果不存在方案输出 $-1$ 。
题解
这题可以分成两个部分，一个是求凸包切线部分，一个是求环区间最小覆盖部分。
我们注意到，一个点能照亮的最大区域是这个点对于这个凸包求左右两条切线，然后点亮所有区域的等价条件是所有边都被一个点的两条切线夹起来过，求切线就是一个二分的板子，然后这个问题就转化为环形结构内给若干个线段（可以跨过原点），求最少的线段的数量，覆盖 $1$ 到 $n$ 的所有点。
关于求环区间最小覆盖部分，首先肯定是断环成链，然后枚举 $i=1\sim n$ 区间 $[i,i+n)$ 的最小线段覆盖，但这是 $O\left(n^2\right)$ 的，有以下几种解法。
第一种，本人最初过题思路，设 $\text{dp}(l,r)$ 表示区间 $[l,r]$ 的最小线段覆盖。
固定 $l$，显然 $\text{dp}(l,r)$ 是分段的。然后对给定 $l$，显然策略为找到覆盖他的线段中的最大的右端点 $k$。
于是有
$$ \text{dp}(l,i) \begin{cases} 1, &i\le k\\ \text{dp}(k+1,i)+1, &i\gt k \end{cases} $$
于是可以可持久化线段树维护每个 $\text{dp}(i,\ast)$ 数组的所有分段点，然后 $O(n\log n)$ 查询 $\text{dp}(i,i+n-1)(i=1\sim n)$，得到答案。
第二种，由于对给定 $l$，最优策略为找到覆盖他的线段中的最大的右端点 $r$，然后跳到 $r+1$，于是每个状态的后继都是唯一的。
因此如果对每个 $l$，建边 $l\to r+1$，可以得到一棵树。
考虑树上倍增，可以 $O(n\log n)$ 查询每个结点 $i=1\sim n$ 跳到不小于 $i+n-1$ 的祖先的最小步数得到答案。
另外这也可以通过 $\text{dfs}$ 维护根到当前结点的路径然后二分来实现。
第三种，首先淘汰掉被另一条线段完全包含的线段，然后选取余下的线段中最短的线段的每个位置作为起点暴力跳查询答案。
设最短的线段长度为 $L$，则每次跳的长度不小于 $L$，于是最多跳 $O(\frac nL)$ 次，于是总复杂度 $O(L\times \frac nL)\sim O(n)$。
关于淘汰被另一条线段完全包含的线段，也可以利用桶排等技巧 $O(n)$ 实现。
关于为什么选最短的线段的每个位置作为起点可以保证得到最优解，本人无法证明。
