【11.2】【VP】Codeforces Round #728 (Div. 2)

ALL：6
AC：3
补题：1

---

B. Pleasant Pairs

题意：

给你一个长度为 $n$ 的序列，且元素两两不同，你需要求出满足 $i<j$ 且 $i+j=a_i\cdot a_j$ 的数对个数。

$n\le 10^5,1\le a_i\le 2n$

思路：枚举每一个 $a_j$ ，对于该数枚举倍数，即 $a_i$ ，然后维护一个标记数组即可。

AC代码：https://codeforces.com/contest/1541/submission/178916763

---

C. Great Graphs

题意：

给你一个长度为 $n$ 的序列 { d } \{d\} {d}，你需要构造一个有向带权图，使得点 $1$ 到点 $i$ 的最短路长度为 $d_i$，同时使得所有边的边权之和尽可能地小。

注意：图中不能出现负环和重边。

$n\le 10^5,0\le d_i\le 10^9$

思路：如果不考虑连接负边，构建出来的一定是一棵树，要让树边权之和最小，即把最短路从小到大排序，然后连接成一条链即可，差分数组即为连接的边权。

如果要连接负边，我们考虑一棵树，要连接负边，一定是在原树上 $i\to j(w)$ 的一条路径，我们反向连接 $j\to i(-w)$ ，这样可以保证连接出来的正边和负边没有产生负环，一共是 $n^2$ 级别的边。

易知当连接成一条链时，上述两个贡献都是最小的，因此边权之和也是最小的。

AC代码：https://codeforces.com/contest/1541/submission/178917969

---

D. Tree Array

题意：

给定一棵 $n$ 个节点的树。
对于这棵树，我们通过下列方法来生成一个序列：

1. 等概率选择这 $n$ 个节点中的一个节点，并对这个节点打上标记（初始时没有节点被打上标记）；
2. 在所有没被打上标记且与至少一个打上标记的节点相连的节点中等概率选择一个节点并对这个节点打上标记；
3. 重复步骤 2 直到所有节点都被打上标记，此时生成的序列就是所有节点编号按照节点被打上标记的时间排序后的形成的序列。

求生成序列的期望逆序对数对 $10^9+7$ 取模后的值。
$2\le n\le 200;$ 给出的是棵树。

题解：CF1540B Tree Array 题解

思路：一道好的概率期望题目。考虑枚举钦定根，并且枚举每一个逆序对 $(u,v)$ ，计算该逆序对被选中的概率。易知从根节点取到该逆序对的概率，等于 $\text{lca(u,v)}$ 取到该逆序对的概率。

我们可以思考用一个容器模拟这个取的过程，虽然这个过程中容器大小在变化，即取到一个点的概率是实时在变得，但是取到两个点方向的节点的概率是相等的。因此可以忽略其他点的影响。

设 $d{p}_{i,j}$ 为从 $(u,v)$ 的 $\text{LCA}$出发，在链上走 $i$ 步到 $u$ ，在链上走 $j$ 步到 $v$ ，使得 $u$ 在 $v$ 前面的概率。可以预处理。

AC代码：https://codeforces.com/contest/1541/submission/178924086