题面
$T1$
Solution
首先，我们不考虑字典序，只考虑代价最小。
明显的，我们有一个贪心的想法：确定先填奇数还是先填偶数之后，我们让奇数和偶数的相对位置关系不变，这种策略的代价一定是最小的。
（证明：我们考虑交换排序过后的两个数，分类讨论一下，可以得知答案一定不会比直接按照原来的顺序更优。）
对于连续的一段（这里只谈奇数或者偶数），如果他们在排序之后相对原来的位置都是向右移动，且移动之后最小的编号都不小于原来位置最大的编号，那么他们是可以随便安排位置的（消耗的代价： $\sum p_i-i$ ，是固定的）。因为要保证字典序最小，所以我们从小到大向里面放。
类似的，如果都是向左移动，且移动之后的最大编号都不大于原来的最小编号。我们就从大到小的且尽量靠右的放进去。
Code
1 |
|
$T2$
Solution
Code
$T3$
Solution
首先，我们需要明确一个事实：颁奖的集合有且只有一个。
如果有多个，很容易用反证法推出矛盾。
设 $F_{n,k}$ 表示 $n$ 个人中，给 $k$ 个人颁奖的概率。
考虑转移。
设 $p=\frac{a}{b},q=1-p$ 。
如果不给第 $n+1$ 个人颁奖，那么他一定要输给在集合中的 $k$ 个人。因为这 $k$ 个人的编号一定比 $n+1$ 小，所以概率是 $p^k$ 。
如果要给第 $n+1$ 个人颁奖，那么他一定要赢前面的 $n-k+1$ 个人，概率为 $q^{n-k+1}$ 。（和在集合中的 $k$ 没有关系）
因此我们有 $F_{n+1,k}=F_{n,k}\cdot p^k+F_{n,k-1}\cdot q^{n-k+1}$ 。
这样我们就可以得到一个 $O(n^2)$ 的算法。
考虑优化。
我们发现在中间加入很困难，可以试着找两边的加入。因为右边已经考虑，所以考虑 $1$ 。
如果不给第 $1$ 个人颁奖，那么他一定要输给在集合中的 $k$ 个人。因为这 $k$ 个人的编号一定比 $1$ 大，所以概率是 $q^k$ 。
如果要给第 $1$ 个人颁奖，那么他一定要赢后面的 $n-k+1$ 个人，概率为 $p^{n-k+1}$ 。（和在集合中的 $k$ 没有关系）
因此我们又有 $F_{n+1,k}=F_{n,k}\cdot q^k+F_{n,k-1}\cdot p^{n-k+1}$ 。
和上面的式子合并一下，可以得到：
这样就可以 $O(n\log n)$ 完成计算。（ $\log$ 是由于求逆元）
Code
1 |
|
总结
还是不会分析题目，提炼出有用的性质。还有对于 $dp$ 还是不够熟练，特别是概率期望 $DP$ ，只要考到就懵逼，要加强练习。