ARC111 题解
Froggy
·
·
个人记录
AtCoder Regular Contest 111
A - Simple Math 2
这场 ARC 中最难的题目。（确信
设 \left\lfloor \frac{10^n}{m}\right\rfloor=Am+B（0\leq B<m），那么 B 就是我们需要求的答案。
把下取整搞掉就变成了：
那么显然 $B=\left\lfloor \frac{10^n\bmod m^2}{m}\right\rfloor$。
快速幂解决。
[***code***](https://atcoder.jp/contests/arc111/submissions/19340783)
---
### [B - Reversible Cards](https://atcoder.jp/contests/arc111/tasks/arc111_b)
显然有个二分图最大匹配做法，直接跑 Dinic 可以过。
$\mathcal{O}(n\sqrt{n})$ 很蠢，其实有个更蠢的 $\mathcal{O}(n)$ 做法。
把每个 $a_i$ 和 $b_i$ 之间连一条边，那么答案就是每个连通块的点数和边数的 $\min$ 之和。正确性显然。
[***code***](https://atcoder.jp/contests/arc111/submissions/19344100)
---
### [C - Too Heavy](https://atcoder.jp/contests/arc111/tasks/arc111_c)
显然只需单独考虑每个大小 $>1$ 的置换环。
显然要保证所有置换环上的物品都能动，否则无解。
假设一个置换环的大小为 $m$ ，那么移动次数的下界显然是 $m$，考虑如何构造。
让重量最轻的物品沿着环跑一遍即可。
时间复杂度：$\mathcal{O}(n)$。
[***code***](https://atcoder.jp/contests/arc111/submissions/19391116)
---
### [D - Orientation](https://atcoder.jp/contests/arc111/tasks/arc111_d)
容易想到如果一条边连着的两个点的 $c_i$ 不同，那么一定是 $c_i$ 大的往 $c_i$ 小的点。
接下来对于每个 $k\in [1,n]$， 抠出所有满足两端点 $c_{i}$ 都等于 $k$ 的边，然后继续给这些边定向。
由于一定有解，那么对于每个连通块中的点一定在同一个强连通分量中。
~~于是找一条哈密尔顿回路？？n 只有 100 别怕~~
其实只需要撸出来一颗 dfs 树，然后树边父亲往儿子连，非树边让后代往祖先连即可。正确性显然。
[***code***](https://atcoder.jp/contests/arc111/submissions/19391634)
---
### [E - Simple Math 3](https://atcoder.jp/contests/arc111/tasks/arc111_e)
就像题目标题所写，这题很 simple。
题意就是求：
$$\sum\limits_{i=1}^\infty\left[\left\lfloor\frac{A+Ci}{D}\right\rfloor-\left\lfloor\frac{A-1+Bi}{D}\right\rfloor=0\right]$$
先考虑下 $i$ 的上界。
如果 $Ci-Bi+1\geq D$ ，那么这个 $i$ 显然不合法。
也就是说 $Ci-Bi+1<D$，即 $i\leq \frac{D-2}{C-B}$，这个上界设为 $n$。
显然 $\forall i\in[1,n]$，$\left\lfloor\frac{A+Ci}{D}\right\rfloor-\left\lfloor\frac{A-1+Bi}{D}\right\rfloor\in [0,1]$，那么答案就呼之欲出了：
$$\sum\limits_{i=1}^n\left\lfloor\frac{A+Ci}{D}\right\rfloor-\sum\limits_{i=1}^n\left\lfloor\frac{A-1+Bi}{D}\right\rfloor$$
直接上类欧板子即可。
由于 Atcoder Library 里有 `floor_sum` 这个东西，所以主代码2行。
[***code***](https://atcoder.jp/contests/arc111/submissions/19392878)
---
### [F - Do you like query problems?](https://atcoder.jp/contests/arc111/tasks/arc111_f)
题目看着挺吓人，上来就是吉老师线段树，其实仔细分析后并不难。
先计数转期望一波，这样更容易处理。
根据期望的线性性，可以把每个位置对答案的贡献分别考虑。
不妨考虑位置 $i$ 对答案的贡献。
无论是1操作还是2操作还是3操作，操作区间覆盖到这个位置的概率都是 $\frac{2i(n-i)}{n(n+1)}$，令其为 $k$。
容易发现，执行一次覆盖到这个位置的操作2后这个位置期望值一直为 $\frac{m-1}{2}$。
也就是说在第一次操作2之后，每执行一次覆盖到这个位置的询问操作都会对答案产生 $\frac{m-1}{2}$ 的贡献。
设 $p2$ 表示有效操作2的概率，$p3$ 表示有效询问操作（操作3）的概率。
则 $p2=\frac{mk}{2m+1}$，$p3=\frac{k}{2m+1}$。
不妨枚举第一次操作 2 出现的位置，就能得到第 $i$ 个位置对答案的贡献：
$$\sum\limits_{j=1}^Q (1-p2)^{j-1}p2\cdot p3\cdot (Q-j)\cdot\frac{m-1}{2}$$
提出 $p2\cdot p3\cdot \frac{m-1}{2}$，然后把柿子拆成一个等比数列加一个等差等比数列求和即可。
[***code***](https://atcoder.jp/contests/arc111/submissions/19389763)