[套题记录]AtCoder Regular Contest 108

vp 被暴打了。 # [A - Sum and Product](https://atcoder.jp/contests/arc108/tasks/arc108_a) 根号求因数。 [评测记录](https://atcoder.jp/contests/arc108/submissions/26814568) # [B - Abbreviate Fox](https://atcoder.jp/contests/arc108/tasks/arc108_b) 用栈做类括号匹配。 [评测记录](https://atcoder.jp/contests/arc108/submissions/26814673) # [C - Keep Graph Connected](https://atcoder.jp/contests/arc108/tasks/arc108_c) 考虑一棵树的情况。 根的颜色随便选。对于子树，若父边已被占用，则钦定不选某种颜色，反之则钦定选某种颜色。 对于子树的字数约束形式仍相同。 因此总有解，一次 dfs 即可。 [评测记录](https://atcoder.jp/contests/arc108/submissions/26815005) # [D - AB](https://atcoder.jp/contests/arc108/tasks/arc108_d) 分类讨论。特判 $n\leq 3$ 。 只考虑 $c_{AB}=\texttt{A}$ 的情况，对于 $c_{AB}=\texttt{B}$ 的情况可以将 $\texttt{A},\texttt{B}$ 取反并将串翻转。 - $c_{AA}=\texttt{B}$ 我们先用 $c_{AB}$ 制作 $\texttt{AAAAA...AAB}$ ，然后往要插 $\texttt{B}$ 的地方插。 最终的串都以 $\texttt{A}$ 开头，以 $\texttt{AB}$ 结尾。 - $c_{BA}=\texttt{A}$ 我们没必要使用 $c_{BA}$。此时不能插出相邻的两个 $\texttt{B}$ ，故不考虑 $c_{BB}$ 。 答案是 $F_{n-2}$。 - $c_{BA}=\texttt{B}$ 可以任意插，答案为 $2^{n-3}$ ，显然不可能更多。 - $c_{AA}=\texttt{A}$ 显然我们只能造出 $\texttt{AAAAA...AAB}$ 。 [评测记录](https://atcoder.jp/contests/arc108/submissions/26829781) # [E - Random IS](https://atcoder.jp/contests/arc108/tasks/arc108_e) **题意** ： 有一个排列 $A_{1\sim n}$ ，维护 $S\subseteq A$ ，初始时 $S=\varnothing$ ，执行以下步骤： - 记 $B=\{a\in A:\text{将}a\text{加入}S\text{后其仍然是上升子序列}\}$ - 等概率选择 $B$ 中的一个元素加入 $S$ 。 - 不断重复直到 $B=\varnothing$ 。 求最终 $|S|$ 的期望。 $n\leq 2000$ ，时限$\texttt{3s}$。 ------------ - **结论** ：题目的随机规则等价于：随机一个顺序（排列），并按照这个顺序逐个尝试加入元素。 （技巧：均匀随机合法分支 = 整棵搜索树，每条路径只保留合法步骤） **证明** ：将策略改写，每次均匀随机各个元素之一，若不合法则不加入。不难发现，对于一次有影响的加入操作，概率和原问题相符。（技巧：鞭尸） 排列不会重复考虑两个数，但这个策略可能重复考虑两个数，不符合要求。 注意到一个数不会加入两次，也不会先不合法然后合法，所以我们可以进一步规定不能随机到已经随机过的元素。有影响的加入操作的概率和原问题仍相符。 可以发现，在选择判定元素 $x$ 是否可以被选择时，只跟目前 $S$ 左右的两个元素有关，这提示我们使用区间 DP。 在我们选定了 $A_i$ 后，整个序列就被分成了前后两个部分 $A_{1\sim i-1},A_{i+1\sim n}$ ，这两个部分是互不影响的。 于是我们可以看做，在第一个部分随机排列加点，然后在第二个部分随机排列加点，然后将两个部分的元素个数期望简单相加即可。 这会有一点小小的不等价之处：我们的之前可能已尝试过若干元素，但没能加入，然而我们在子问题中会重新考虑这些元素。 不难发现，这些元素即使轮到也必不会加入，故只是掺了点沙子，不会影响答案。（技巧：鞭尸） 记 $f_{l,r}$ 为选定 $A_l,A_r$ 后仅考虑 $A_{l,r}$ ，答案的期望。 记可选的数为 $A_{p_1},A_{p_2},A_{p_3},...,A_{p_k}$ ，则有转移： $$f_{l,r}=2+\dfrac{1}{k}\sum\limits_{i=1}^kf_{l,p_i}+f_{p_i,r}-1$$ 其中 $p$ 需要满足的条件是 $l<p<r,\ A_l<A_p<A_r$。 显然可以树状数组维护。 具体地，对于 $k$ 可以用二维前缀和得到。 $$ \begin{aligned} &\sum\limits_{i=l+1}^{r-1}f_{l,i}[A_l<A_i<A_r]\\ =&\sum\limits_{i=1}^{r-1}f_{l,i}[A_l<A_i<A_r] \end{aligned} $$ 对每个 $l$ 维护一个以 $A_i$ 为下标的树状数组，值为 $f_{l,i}$ ，即可查询。 $$ \begin{aligned} &\sum\limits_{i=l+1}^{r-1}f_{l,i}[A_l<A_i<A_r]\\ =&\sum\limits_{i=l+1}^{n}f_{i,r}[A_l<A_i<A_r] \end{aligned} $$ 对每个 $r$ 维护一个以 $A_i$ 为下标的树状数组，值为 $f_{i,r}$ ，即可查询。 逐渐增大区间长度，对于第一类树状数组相当于逐渐增大 $r$ ，对第二类而言相当于逐渐减小 $l$ 。 复杂度 $O(n^2\log n)$。 [评测记录](https://atcoder.jp/contests/arc108/submissions/26831020) # [F - Paint Tree](https://atcoder.jp/contests/arc108/tasks/arc108_f) **题意** ： 给定一棵 $n$ 个点的树，每个点可染成黑色或白色。 定义一种染色方案的权值为：$\max\big($ 所有黑色点中距离最远的两个点的距离，所有白色点中距离最远的两个点的距离 $\big)$ 求所有染色方案的权值之和，答案对 $10^9+7$ 取模。 $n\leq 2\times 10^5$ ，时限$\texttt{2s}$。 ------------ 首先找到任意一个直径，记为 $s,t$ ，若 $s,t$ 颜色相同，则答案必然为直径长。 若 $s,t$ 颜色不同，不妨令 $s$ 为白 $t$ 为黑，$E_0,E_1$ 分别为白黑点集，有结论： $${\rm Ans}=\max\Big(\max_{u\in E_0}dis(u,s),\max_{u\in E_1}dis(u,t)\Big)$$ 对于点 $u$，记 $a_u=dis(u,s),b_u=dis(u,t)$ ，容易 dfs 求出。 对每个 $i=1\sim n$ 计算最大值 $\geq i$ 的概率，然后求和即为答案。 取反变为对每个 $i=0\sim n-1$ 计算最大值 $\leq i$ 的概率。 枚举 $i$ ，$a_u,b_u\leq i$ 的点可黑可白，$a_u,b_u>i$ 的点会使得方案数为 $0$ ，其余的点根据 $a,b$ 那个小于等于 $i$ ，染成对应的颜色。 方案数为 $2$ 的 $a_u,b_u\leq i$ 点数次方。 复杂度 $O(n)$。 [评测记录](https://atcoder.jp/contests/arc108/submissions/26837598)