Atcoder Regular Contest 165(A~E)-526互联

赛时 45min 切 A~C，降智不会 D，罚坐 1h，喜提 rk70+ -> rk170+。

A - Sum equals LCM

可证明结论：若 \(N\) 只含有一种质因子则无解，否则有解。

B - Sliding Window Sort 2

这么多 corner case 的题竟然 10min 一发入魂，类目了。

由于操作是升序排序，且要求最终字典序最大，所以如果存在一个长度为 \(K\) 的递增子序列，我们一定是会操作它的。否则我们会将操作尽可能地向后放。

贪心地讲，我们一定会让字典序发生改变的位置在 \(n-K\) 之后，否则一定没有无脑操作 \([n-K+1,n]\) 更优。所以我们可以先将操作放在 \([n-K+1,n]\)，并且向前寻找左端点前一个位置上的值是否小于左端点位置，若是则向前移动区间，直到移动不了即可得到最优操作区间。

写了很菜的二分答案。考虑如何判定。

首先有经典结论：若两条相邻的边边权和小于 \(X\)，一定无解。证明可以采用鸽巢原理。

所以我们可以由此结论先确定二分上界。

限制完这个之后我们发现此时对于任意长度大于等于 \(2\) 的路径都是一定合法的，剩下的只有长度为 \(1\) 的路径了。于是把所有边权 \(<X\) 的边拉出来黑白染色，判断是否为二分图即可。

时间复杂度 \(O(n\log V)\)。

D - Substring Comparison

其实没必要一上来就把约束形式化描述的，不妨先只考虑每一条约束中最简洁最弱的那个，即 \(a_i<c_i\)。

将二元偏序关系连边，如果不出现环则直接出解，否则每个强连通分量位置上的值一定相同，而这些相同会打破一些偏序关系，强制使得一些 \(a_i=c_i\)。此时我们可以将被打破的约束中的 \(a_i,c_i\) 不断后移，直到两者不在同一连通分量为止，此时若 \(c_i>d_i\)，则一定无解，否则若 \(a_i>b_i\)，我们之后就可以不再管这条约束。若 \(a_i,c_i\) 依旧小于 \(b_i,d_i\)，我们可以在图上建立若干新边表示这些新的偏序关系，一直做下去直到不再产生新的强连通分量为止。

由于至多会跑 \(n\) 次 tarjan，且对于每个偏序关系至多移动 \(n\) 次，所以时间复杂度为 \(O(n(n+m))\)。

本题启发我们对于带有继承关系的【或】约束，不妨先从最弱的约束下手，根据是否合法依次增强约束。

E - Random Isolation

其实很容易想到树形 dp 来做，但是难点在于如何计算连通块的贡献。对吧，我们既不知道连通块被删的先后顺序，也不清楚如何计算当前连通块被分割之后的贡献。

但是我们发现我们并不需要知道这些啊？如果对于当前局面，存在一个大小为 \(x>k\) 的连通块，无论如何我们一定会删它一次，它无论如何都会造成一次删除代价。所以其实只要我们知道该连通块出现的概率，我们就可以得到它对于问题的贡献。而删这个连通块之后的代价则可以交给其子连通块统计，对于当前连通块的贡献我们就不用再管了。所以最终的答案即为所有 \(x>k\) 的连通块出现的概率之和。

所以现在问题来到了，如何统计某个连通块的出现概率。

考虑将问题进行神秘的转化：随机一个长度为 \(n\) 的排列 \(P\)，从 \(P_1\) 到 \(P_n\) 依次考虑每一个节点当前所在连通块大小是否 \(>k\)，若是则删除，否则不删，求有效删除次数的期望。两个问题是等价的，因为固定了前若干个有效删除位置之后，下一个有效删除位会等概率出现。

设连通块大小为 \(x\)，与该连通块相连的节点个数为 \(y\)，此时我们可以将统计连通块的出现概率转化为统计在 \(P\) 中 \(x\) 个节点在 \(y\) 个节点之后的概率，即为 \(\frac{x!y!}{(x+y)!}\)。可以发现上步转化通过将随机删点转化为随机排列，使得我们对于概率的描述变得清晰了许多。

于是我们现在只剩下了最后一个任务，统计每一种 \((x,y)\) 的连通块各有多少个。

这个使用树形 dp 统计就很方便了。可以设 \(dp_{u,x,y}\) 表示以 \(u\) 为根，大小为 \(x\)，且有 \(y\) 个节点与之相接的连通块个数，转移套路树形背包即可。总时间复杂度 \(O(n^2k^2)\)。

将统计的主体转化成每个连通块，将随机删点转化为随机排列，很巧妙的题目啊。