Virtual PTS 2020 Day 3 总结

``` --- layout: post title: Virtual PTS 2020 Day 3 总结 date: 2020-06-17 updated: 2020-06-17 katex: true categories: 总结 tags: [总结, Virtual PTS, 数据结构, 计数] --- ``` 这套题总体有很多可做可学的地方，比较值得弄清楚。 ### [莫得感情的复读机](http://csp.ac/problem/182) 题意：一个有向图，有 $n$ 个点；依次加入 $m$ 条边，若图中出现有向环，则发生一次事件，并且将已加入的所有边清空。求每次发生事件的时间。$n,m\le 10^5$。 首先如何判定图中是否存在有向环？可以 tarjan 求强连通分量，当然更简单的方法是试图进行拓扑排序，例如若发现 dfs 遍历到了当前栈（函数栈）中的节点则有环。 这样就解决了只需判定“是否有事件发生”的部分分。对于“求出事件的第一次发生时间”部分分，只需二分答案即可。 对于要求出每次事件的发生时间的部分，我们肯定不能“接续进行二分”，也就是在上一次二分得到的区间后再接着进行二分；因为每次二分的时间复杂度是 $\mathrm{O}(n\log n)$，如果加的边是 $(1,2),(2,1),(1,2),(2,1),\cdots$，那么一共要进行 $\mathrm{O}(n)$ 次二分，总时间复杂度达到了 $\mathrm{O}(n^2\log n)$，不可承受。 与二分类似的算法是倍增，每次倍增所需的验证次数可以做到 $\mathrm{O}(\log \mathrm{ans})$，做法是先从 $1$ 验证，到突变成不可行的时候停止，再从高到低叠加二进制位（这一步类似倍增求 LCA），最后加 $1$ 即得答案。那么是不是可以得到更好的复杂度呢？ 如果我们能够在倍增的时候做到每次验证 $\mathrm{O}(\mathrm{ans})$ 以下，那么由于倍增结束后正好能“吃掉”长 $\mathrm{ans}$ 的区间，总的时间复杂度就不会超过 $\mathrm{O}(n\log n)$。 那么如何保证倍增验证复杂度达到 $\mathrm{O}(\mathrm{ans})$ 呢？只需保证每次搜索时只遍历区间内的边及其端点即可。当然这里一定要小心，图的边表要清空，否则可能会遍历无用边而造成复杂度不正确。 总之，区间答案的倍增，常常通过“验证 $\mathrm{O}(\mathrm{ans})$”来保证总体复杂度 $\mathrm{O}(n\log n)$。 ### [装备重铸](http://csp.ac/problem/183) 题意：某装备有 $n$ 个等级，$n$ 级为最高级。第 $i$ 级的装备用 $c_i$ 的代价可以进行一次重铸，重铸时变成第 $j$ 级装备的概率为 $p_j$（此概率与 $i$ 无关）。现在有 $k$ 个这样的装备，各自所处的等级为 $a_1,a_2,\cdots,a_k$，若想得到（至少）一个最高级装备且始终采取最优策略，求总代价的期望。 这道题之所以可做，是因为“此概率与 $i$ 无关”；一定要坚持本题的基本条件 270 分钟不动摇（大雾）。 首先考虑 $k=1$ 的部分分。设 $f_i$ 表示一个 $i$ 级装备变成最高级的期望花费，则 $f_i=c_i+\sum_{j=1}^{n-1}p_jf_j$。 这里如果像通常的期望 dp 一样，把含 $f_i$ 的项移到一边，就会陷入困境。一题作难而十分无，身死人手，为天下笑者，何也？基础不坚而做题之势异也！ 还是要坚持基本条件。条件提示我们，不同的 $i$ 之间有很大的相似性。因此我们不妨列一下 $f_i$ 的式子： $\begin{cases}f_1=c_1+\sum_{j=1}^{n-1}p_jf_j \\ f_2=c_2+\sum_{j=1}^{n-1}p_jf_j \\ \cdots \\ f_{n-1}=c_{n-1}+\sum_{j=1}^{n-1}p_jf_j\end{cases}$ 我们发现 $\sum_{j=1}^{n-1}p_jf_j$ 这个部分是共有的，设它为 $t$，则 $\begin{cases}f_1=c_1+t \\ f_2=c_2+t \\ \cdots \\ f_{n-1}=c_{n-1}+t\end{cases}$ 再结合 $t=\sum_{j=1}^{n-1}p_jf_j$，知 $t=\sum_{j=1}^{n-1}p_j(c_j+t)=t\left(\sum_{j=1}^{n-1}p_j\right)+\sum_{j=1}^{n-1}p_jc_j$；也就可以知道 $t=\dfrac{\sum_{j=1}^{n-1}p_jc_j}{1-\sum_{j=1}^{n-1}p_j}$。算出了 $t$，也就可以知道 $f_i$，于是答案就能求了。 $k=2$ 的部分分呢？最优策略肯定是选花费较低的一个装备进行重铸。 先不妨设 $c_1\le c_2\le \cdots\le c_{n-1}$，也就是先对等级进行排序。 接下来，我们还是可以设 $f_{i,j}(i\le j)$ 表示一个 $i$ 级装备和一个 $j$ 级装备中的一个变成最高级的期望花费。那么可以列出这样的转移式： $$f_{i,j}=c_i+\sum_{u=1}^{j}p_uf_{u,j}+\sum_{u=j+1}^{n-1}p_uf_{j,u}$$ 接下来，我们~~乳法炮制~~ 如发炮制，令 $t_j=f_{i,j}-c_i$，那么就有 $$\begin{aligned}&t_j \\ =&\sum_{u=1}^{j}p_uf_{u,j}+\sum_{u=j+1}^{n-1}p_uf_{j,u}\\ =&\sum_{u=1}^{j}p_u(t_j+c_u)+\sum_{u=j+1}^{n-1}p_u(t_u+c_j)\\ =&\sum_{u=1}^{j}p_ut_j+\sum_{u=1}^{j}p_uc_u+\sum_{u=j+1}^{n-1}p_ut_u+\sum_{u=j+1}^{n-1}p_uc_j\\ =&t_j\sum_{u=1}^{j}p_u+\sum_{u=1}^{j}p_uc_u+\sum_{u=j+1}^{n-1}p_ut_u+c_j\sum_{u=j+1}^{n-1}p_u\end{aligned}$$ 从而 $$\left(1-\sum_{u=1}^{j}p_u\right)t_j =\sum_{u=1}^{j}p_uc_u+\sum_{u=j+1}^{n-1}p_ut_u+c_j\sum_{u=j+1}^{n-1}p_u$$ 这个式子中，$\left(1-\sum_{u=1}^{j}p_u\right), c_j\sum_{u=j+1}^{n-1}p_u, \sum_{u=1}^{j}p_uc_u$ 都可以 $\mathrm{O}(n)$ 计算，$\sum_{u=j+1}^{n-1}p_ut_u$ 只依赖 $u\ge j+1$；从而可以倒着递推，在 $\mathrm{O}(n\log p)$（$\mathrm{O}(\log p)$ 计算逆元）的时间内把所有结果计算完成。 关于一般的情形，推导较为复杂，这里只提一个模型。 有一种独立随机试验，成功的概率为 $p$（这意味着失败的概率为 $1-p$；而且顺便提一句，概率中的“成功”不一定是好事）。不断进行该试验，直到成功或试验满 $k$ 次便停止。求最后成功的概率和试验总次数的期望。 或者提一个实际背景：神犇在考场上 AK 后开始写 Link-Cut Tree，但他的记忆不太清楚了。假设他写一次 LCT，写对的概率为 $p$，且这个概率不随时间而改变。因为神犇信奉“LCT 这种东西只能一遍过，不能调试；不对就重构”，因此如果写不对，他会开另一个文件重构代码；但他打算至多写 $k$ 次，如果 $k$ 次还写不对就去写可持久化动态仙人掌。那么求他写出 LCT 的概率 $f$ 和他写的 LCT 的份数的期望 $g$。 首先求概率。方便起见令 $q=1-p$。$f$ 有两种求法，一种是讨论他是第几次成功的： $$f=p+qp+q^2p+\cdots+q^{k-1}p=p\cdot \dfrac{1-q^k}{1-q}=1-q^k$$ 另一种方法是考虑反面，他没有写出的概率是 $q^k$，因此写出了的概率是 $1-q^k$。 再求期望。我们所用的随机变量 $X$ 表示的应该是“他写的 LCT 的份数”。求期望当然可以列分布列： | $x_i$ | $1$ | $2$ | $\cdots$ | $k-1$ | $k$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $\mathrm{P}(X=x_i)$ | $p$ | $qp$ | $\cdots$ | $q^{k-2}p$ | $q^{k-1}p\color{red}{+q^k}$ | 俗话说得好，列完分布列一定要检查各项的概率之和是不是 $1$，否则绝对会后悔；就像表中标红色的项，初列时有可能会漏掉——如果全部写错，那他同样也是写了 $k$ 份 LCT，要把这个概率也写上去。 这样就可以求出 $g$： $$\begin{aligned}&g\\=&p+2qp+3q^2p+\cdots+(k-1)q^{k-2}p+kq^{k-1}p\color{red}{+kq^k}\\=&p(1+2q+3q^2+\cdots+(k-1)q^{k-2}+kq^{k-1})+kq^k\\=&\dfrac{1-q^k}{p}-kq^k+kq^k\\=&\dfrac{1-q^k}{p}\end{aligned}$$ 嗯，这个 $f$ 和 $g$ 的式子怎么这么像？具体地说，$f=pg$。 这个式子我暂时不知道如何作出直接的解释；但是我们可以从另一个角度进行理解。 两端取 $k\to +\infty$ 的极限，得到 $\lim\limits_{k\to +\infty}f=p\lim\limits_{k\to +\infty}g$（因为 $p$ 是常数，所以提出了极限符号）。当尝试次数趋向于正无穷时，成功率应该趋向于 $1$，而尝试次数的期望应该趋向于 $\dfrac{1}{p}$，因此这个式子在极限情形成立。 这个模型应该还是挺有趣的，可以试着研（chu）究（ti）。 ### [起床失败综合症](http://csp.ac/problem/184) 题意：给出一棵以 $1$ 为根的 $n\ (1\le n\le 2\times 10^5)$ 点树，每个叶节点有一个位于区间 $[0,2^k)\ (1\le k\le 31)$ 的整数权值；每个非叶节点有一个标记（$\mathrm{and,or,xor}$ 三者之一），它的权值为它所有孩子的权值的 $\mathrm{and/or/xor}$。要求支持三种操作（共 $q$ 次，$1\le q\le 2\times 10^5$）：修改叶子的权值、修改非叶节点的操作和查询某个点的权值。 看到 $k$ 位和位运算，应该要想到按位分开处理。此后我们就只考虑一位的情形。 一位的时候，$\mathrm{and}$ 值为 $1$ 当且仅当子节点该位**全部**为 $1$，$\mathrm{or}$ 值为 $1$ 当且仅当子节点该位有**至少一个**为 $1$，$\mathrm{xor}$ 值为 $1$ 当且仅当子节点该位有**奇数个**为 $1$。我们发现这些都与子节点中 $1$ 的个数有关，因此只要维护 $1$ 的个数就可以知道权值了。 这样，每次修改的时候像（zkw）线段树一样向父节点更新信息，就可以完成深度不大于 $\lceil \log_2 n\rceil$ 的部分分了。 这里有一个优化，若向父节点更新时发现当前节点的权值没有发生变化，就不必向上更新了（其实有些类似我在“异或粽子”一题的玄学算法）。而这题的数据较弱，加上这个优化就可以通过了（如果要卡掉这个做法，只需把操作全部弄成异或，这样优化就不起作用了）。正解似乎要用到动态 dp，可以用树剖或 LCT 维护。 我做这题时只是觉得这个可能很难，没有贯彻落实“举例是理解的试金石”思想，没有从 $k=1$ 的方面下手，从而没有发现性质，于是只拿了可怜的暴力分（哭）。因此今后考试还是要沉下心来，通过举例、找规律、化式子来发现性质。