A
倒着做即可，每次找 \(a_i = i\) 的位置。
时间复杂度 \(\mathcal{O}(n^2)\) 或 \(\mathcal{O}(n \log n)\)。
B \((\texttt{Easy} \ 2 / 0)\)
考虑在完全图上断掉一些边。
若 \(2 \mid n\)，则断掉所有 \((i, n - i + 1)\) 的边即可；否则断掉所有 \((i, n - i)\) 的边即可。
时间复杂度 \(\mathcal{O}(n^2)\)。
C \((\texttt{Easy} \ 2 / 3)\)
好想但是有点恶心的题。
一个必要条件是图的每个连通块都要存在欧拉回路。在此之上，我们对连通块数量分类讨论。
- 连通块数量 \(\ge 3\)：此时必然有解。
- 连通块数量 $ = 2$：此时有解当且仅当两个连通块不全是环。
- 连通块数量 $ = 1$：此时若存在 \(\deg \ge 6\) 的结点或存在 \(\ge 3\) 个 \(\deg \ge 4\) 的结点则必然有解；对于恰好有两个 \(\deg = 4\) 的结点的情况，我们称这两个点为关键点，则有解的条件是存在只包含一个关键点的环；其余情况无解。
时间复杂度 \(\mathcal{O}(n)\)。
D \((\texttt{Easy} \ 3 / 0)\)
首先每个数至多被操作一次，于是我们考虑去钦定每个数是用 \(A\) 操作 / 用 \(B\) 操作 / 不操作。
不难发现不操作的数肯定构成了一个上升子序列，考虑其中相邻的两个数 \(p_l\) 和 \(p_r\)。若 \((l, r)\) 中存在 \((p_l, p_r)\) 中的数，则把这个数直接加进上升子序列显然不劣，所以最优方案中不存在这样的数。那么对于 $ < p_l$ 的数，其只能向左移；否则只能向右移。即，确定了满足条件（相邻两数之间不存在值在他们之间的数）的不操作的上升子序列之后，剩下的数的操作是确定的。
于是考虑设 \(f_i\) 表示考虑前 \(i\) 个数，钦定 \(p_i\) 在上升子序列内所需要的最小代价，则对于满足条件的 \(j < i\)，设 \((j, i)\) 中有 \(x\) 个数 \(> p_i\)、\(y\) 个数 \(< p_j\)，则转移为
\[f_i \leftarrow \min\{f_i, f_j + xa + yb\} \]直接 \(\mathcal{O}(n^2)\) dp 即可。
E \((\texttt{Medium} \ 4 / 1)\)
接连想出了一车子假做法！！！
首先把 \(a\) 排序。
可以通过调整法证明，\(\exist p \in [0, n]\)，使得存在一种最优方案的配对方式为 \(a_i\) 和 \(a_{2p - i + 1}\) 配对，其中 \(1 \le i \le p\)；以及 \(a_{p + i}\) 和 \(a_{2n - i + 1}\) 配对，其中 \(1 \le i \le n - p\)。
\(p\) 越小越好，我们二分出 \(p\) 的最小值即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
F \((\texttt{Hard} \ 7 / 0)\)
复读题解。
我们首先证明一个结论：\(n\) 个 \([0, 1)\) 上的随机变量 \(x_1, x_2, \cdots, x_n\) 满足 \(\sum x_i = 1\)，则
\[E(\min_k \{x_i\}) = \frac1n \sum\limits_{i = 0} ^ {k - 1} \frac{1}{n - i} \]证明：首先考虑求出 \(E(\min \{x_i\})\)。如果最小值 \(\ge x\)，则我们可以把所有 \(x_i\) 都减去 \(x\)，则变为在 \([0, 1 - nx)\) 中随机取 \(n - 1\) 个点，我们有
\[ \begin{aligned} E(\min \{x_i\}) & = \int_{0} ^ {\frac1n} (1 - nx) ^ {n - 1} \mathrm d x \\ & = -\frac1n \int_{0} ^ {\frac1n} (1 - nx) ^ {n - 1} \mathrm d (1 - nx) \\ & = \frac1n \int_{0} ^ 1 x^{n - 1} \mathrm d x \\ & = \frac{1}{n^2} \end{aligned} \]接着考虑次小值。发现我们把最小值去掉以后问题形成了一个递归的形式，我们有
\[ \begin{aligned} E(\min_2 \{x_i\}) & = E\left( \min\{x_i\} + \frac{1 + \min\{x_i\}}{(n - 1)^2} \right) \\ & = E(\min \{x_i\}) + \frac{1 - E(\min \{x_i\})}{(n - 1)^2} \\ & = \frac1n (\frac1n + \frac{1}{n - 1}) \end{aligned} \]其余的可以归纳证明。
回到本题。不妨建立极坐标系，钦定一条线为极轴，并把极角分为 \([0, \frac{\pi}{3}), [\frac{\pi}{3}, \frac{2\pi}{3}), [\frac{2\pi}{3}, \pi)\) 三部分，并把这三部分旋转重合，这样我们在 \((0, \frac{\pi}{3})\) 中随机 \(n - 1\) 条线以及它们所属的部分，求所属的部分不同的两条线组成的夹角的最小值期望。特别地，极角为 \(0\) 的线属于第一部分；极角为 \(\frac{\pi}{3}\) 的线属于第三部分。
显然这个最小值必然由相邻的两条线组成，我们枚举它在所有相邻线之间距离中的排名 \(k\)。这等价于我们钦定了 \(k - 1\) 条线的颜色，并钦定排名 \(k\) 的两条线所属部分不同，概率即
\[\frac23 \cdot \frac{1}{3^{k - 1}} = \frac{1}{3^{k - 1}} - \frac{1}{3^k} \]特别地，因为 \(k = n\) 时两段线段颜色必不同，此时 \(- \frac{1}{3^k}\) 要去掉。
所以答案即
\[ \begin{aligned} & \sum\limits_{i = 1} ^ n \left(\frac{1}{3^{i - 1}} - \frac{1}{3^i}\right) \cdot \frac1n \sum\limits_{j = 1} ^ i \frac{1}{n - j + 1} \\ = & \frac1n \sum\limits_{j = 1} ^ n \frac{1}{n - j + 1} \sum\limits_{i = j} ^ n \left(\frac{1}{3^{i - 1}} - \frac{1}{3^i}\right) \\ = & \sum\limits_{j = 1} ^ n \frac{1}{3^j \cdot n} \cdot \frac{1}{n - j + 1} \end{aligned} \]注意前两行的式子并没有考虑上面说的 \(k = n\) 的情况，第三行中就把它减去了。
时间复杂度 \(\mathcal{O}(n)\)。
标签：pi,frac,min,sum,AGC032,mathcal,frac1n From： https://www.cnblogs.com/Scintilla/p/16801056.html