2020-2021:teams:intrepidsword:2020-nowcoder-multi-6

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020-nowcoder-multi-6 [2020/08/05 15:27]
admin I. Valuable Forests
+++ 2020-2021:teams:intrepidsword:2020-nowcoder-multi-6 [2020/08/09 17:32] (当前版本)
admin C & E
@@ 行 7: / 行 7: @@
 ====== Solutions ======
-===== I. Valuable Forests =====
+===== A. African Sort =====
-**题目大意**：定义一个森林的价值为所有点的度数平方和。求所有 $n$ 个点带标号的森林的价值和。
+**题目大意**：给你一个排列，每次选一个子集 $S$，花费 $|S|$ 的代价将 $S$ 位置的所有元素随机打乱。问排好序的期望代价。
+**题解**：题解（不甚严谨地）证明了：最优策略为对排列的每个环分别操作，每个环全部打乱。这个结论我们比赛时也猜到了，具体证明请看题解。
+设 $f(n)$ 表示将一个长为 $n$ 的环排好序时的期望代价，$g(n)$ 表示将一个长为 $n$ 的随机排列排好序的期望代价。
+$$
+\begin{aligned}
+f(n)&=g(n)+n(n>1)\\
+g(n)&=\frac{1}{n!}\sum_{i=1}^{n}{n-1\choose i-1}(i-1)!(n-i)!(f(i)+g(n-i))\\
+g(n)&=\frac{1}{n}\sum_{i=1}^{n}(f(i)+g(n-i))\\
+\end{aligned}
+$$
+显然可以用前缀和维护。
+===== B. Binary Vector =====
+**题目大意**：求有多少 $n\times n$ 的模 $2$ 意义下的矩阵满秩。
+**题解**：注意到，为了使第 $i$ 个行向量与前面的行向量线性无关，有 $2^{i-1}$ 种向量不能取。因此答案为 $f_{n}=\prod_{i=1}^{n}(2^{n}-2^{i-1})$，它等于 $2^{n}(2^{n}-1)f_{n-1}$，因而可以递推。
+===== C. Combination of Physics and Maths =====
+签到题。
+===== E. Easy Construction =====
+签到题。
-**题解**：首先求树的价值平方和。注意到一个点的度数等于 prufer 序列中出现次数加 $1$，且每个点的贡献相同，因而是 $n\cdot\sum_{i=0}^{n-2}(i+1)^{2}{n-2\choose i}$。森林 dp 一下即可。

2020-2021/teams/intrepidsword/2020-nowcoder-multi-6.1596612450.txt.gz · 最后更改: 2020/08/05 15:27 由 admin