a
给定程序，求程序地期望运行结果
考虑一个长度为 \(n\) 地排列，其逆序对数地期望为 \(\frac{\binom{n}{2}}{2}\)，由此，不妨设 \(f_n\) 为长度为 \(n\) 的排列期望运行结果，则有
\[ f_n\ =\ \frac{n(n-1)}{4}+\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}f_i \] 这时候可以移项得到一个 \(O(n^2)\) 的 \(DP\) 方程，但是我们考虑求出 \(f_n\) 的通项，将组合数拆开有
\[ \frac{f_n}{n!}\ =\ \frac{n(n-1)}{4}\times\frac{1}{n!}+\frac{1}{2^n}\sum_{i=0}^n\frac{1}{(n-i)!}\frac{f_i}{i!} \]
不妨设 \(<f_0,f_1,f_2...>\) 的 \(egf\) 为 \(f\)，\(<0,0,2,6...>\) 的 \(egf\) 为 \(g\)
则有
\[ f(x)\ =\ \frac{1}{4}g(x)+e^{\frac{x}{2}}f(\frac{x}{2}) \]
根据 \(EGF\) 性质
\[ x^me^x\ =\ \sum_n[n\ge m]n^{\underline{m}}\frac{x^n}{n!} \]
可以得到 \(g\ =\ x^2e^x\)
盲猜一波如果方程成立，那么解一定为 \(cx^2e^x\) 的形式，解出 \(c=\frac{1}{3}\)，则 \(f_n=\frac{n(n-1)}{3}\)
那么答案为
\[ \frac{1}{n}\sum_{i=1}^nf_i=\frac{1}{3n}\times[\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2}]=\frac{n^2-1}{9} \]
1 |
|
c
给定一颗树，已知 \(s\) 和 \(t\)， 求 \(s\) 到 \(t\) 按题意要求游走的最坏情况下的最小花费
首先考虑 \(s\) 和 \(t\) 直接相连的情况，此时最坏的情况一定出现在以 \(t\) 为根，\(s\) 的子树内，先分类讨论，如果节点 \(x\) 为叶子节点，那么它的代价为从 \(s\) 到该节点再到 \(t\) 的最小花费，最小花费由两部分组成，首先是保证可以到达该节点，并在该节点停在直到删边后满足 \(x\) 到 \(t\) 有唯一通路，即 \(x\) 到 \(t\) 除 \(t\) 以外的路径上每个点的子节点数减 \(1\)，其次保证从这个节点可以回到 \(s\)节点，那么这一部分代价为 \(dis(x,\ s)\)，如果 \(x\) 为非叶节点，那么在这个节点时，最优解一定为先删掉代价最大子节点对应的边，所以这个节点的代价为子节点中的次大代价，同时如果这个节点无次大值，那么可以额外耗费 \(1\) 的花费使它变为叶子
之后考虑 \(s\) 和 \(t\) 不直接相连的情况，注意这是 \(s\) 若一开始就向 \(t\) 的方向随机游走可能情况会变得更差，所以我们最后的最小花费应不超过从 \(s\) 向 \(t\) 方向游走过程中的最坏情况的最优花费，答案具有单调性，考虑二分值为 \(mid\)，定义每个节点的代价 \(f\) 为由离着个点最近的 \(s\) 到 \(t\) 的节点出发再走到 \(t\) 的最小花费，判断 \(mid\) 是否合法则模拟从 \(s\) 向 \(t\) 方向游走的过程，设当前枚举的路径上的点为 \(u\)，其不在路径上的子节点为 \(v\)，游走过程中由于需要满足最坏情况不超过 \(mid\)，则需要删除一些边，即枚举过程中删除的边为 \(del\)，则当 \(f_v-[u=s]+del>mid\) 时需要删除 \((u,\ v)\) 这条边，前面的减 \([u=s]\) 时由于这个点就是由 \(s\) 向上游走来的，而在 \(f_v\) 中计算了删边的贡献，所以要减去，最后设当前枚举的 \(u\) 时 \(s\) 到 \(t\) 的第 \(i\) 个点，则它有 \(i\) 次删除额外边的机会，依此来判断 \(mid\) 是否合法
1 |
|