Contest Info

practice link

Solutions

A. Sum of Interior Angles

签到题。

B. Sumo

签到题。

C. Best-of-(2n-1)

题目大意：两个人玩游戏，一个人胜 \(n\) 局时结束游戏。每局第一个人赢的概率为 \(A\%\)，第二个人赢的概率为 \(B\%\)，平局的概率为 \(C\%\)。问游戏进行的局数的期望。

题解：首先不考虑平局，并将答案乘上 \(\frac{100}{A+B}\)。

假设游戏在第 \(i\) 局结束，那么必然有一个人恰好赢了 \(n\) 局。那么概率为 \((\frac{A}{100})^{n}(\frac{B}{100})^{i-n}{i-1\choose n-1}+(\frac{B}{100})^{n}(\frac{A}{100})^{i-n}{i-1\choose n-1}\)，简单计算即可。

D. Maximum Sum of Minimum

题目大意：给你一棵 \(n\) 个点的树，和一个大小为 \(n\) 的多重集。让你把集合中的元素分配给点作为点权，使得树的价值最大。树的价值为边权之和，边权为两个点点权的最小值。需要求方案。

题解：贪心。将集合中最小的元素赋给度最小的点，然后将该点删去，按照同样的方法继续做。

其实就是每次找一个叶子将集合中最小的元素给它。这样答案就是前 \(n-1\) 小的元素之和。

这个答案已经是最优的了。对于任意一种填法，我们将前 \(i\) 大的元素组成的连通块取出，显然它最多只有 \(i-1\) 条边，也就是说前 \(i\) 大的元素至多只能给答案贡献 \(i-1\) 个。这样就能得到前面的结论。

E. Product of Arithmetic Progression

题目大意：给定等差数列的首项，公差和项数，求数列的乘积。有 \(10^{5}\) 次询问。模 \(10^{6}+3\)。

题解：这题有一点点意思。若 \(d=0\) 就是个快速幂。否则我们将数列每项都乘 \(d^{-1}\)，就得到公差为 \(1\) 的等差数列，用一个前缀积就能维护了。

F. Random Tournament

题目大意：有 \(n\le2000\) 个人排成一排，告诉你两两间的胜负关系（不一定是个偏序）。比赛的过程是每轮任选两个相邻的人打，进行 \(n-1\) 轮。问有多少人可能获胜（任意安排比赛的顺序）。

题解：设 \(dpl[i][j]\) 表示考虑 \([i,j]\)，\(i\) 是否能获胜；\(dpr[i][j]\) 表示考虑 \([i,j]\)，\(j\) 是否能获胜。\(i\) 能获胜的条件是 \(dpl[i][n]\) 和 \(dpr[1][i]\) 均为真。

以 \(dpl[i][j]\) 的转移为例，考虑枚举 \(i\) 最后一个打的人 \(k\)。此时比赛一定是存在一个 \(u\)，\(i\) 打败了 \([i+1,u-1]\) 的人，\(k\) 打败了 \([u,j]\) 的人。

假如 \(k<j\)，那么刚才说的情况当且仅当 \(dpl[i][k]\) 和 \(dpl[k][j]\) 均为真。

假如 \(k=j\)，枚举 \(u\) 的值，当且仅当 \(dpl[i][u-1]\) 和 \(dpr[u][k]\) 均为真。

用 bitset 加速。