ICPC 2019 Shenyang Online Contest

Problem A

Unsolved.

Problem B

Solved by Xiejiadong. 02:32 (+1)

题意：可以在糖果房间任意有选择性的走，在怪物房间，会被任意传送一次，只能进一次怪兽房间，求最多能遍历的房间数量。

题解：不妨将所有的怪物房间全部切断。

显然，一开始和 $1$ 联通的房间，都能直接走到。

由于只能进入一次怪兽房间，肯定会选择进入期望最大的房间。

于是就算怪兽房间的期望，怪兽房间的期望，就是连出去的那个联通快的数量。

于是怪兽房间切断以后，用并查集维护联通块的大小即可。

Problem C

Solved by Xiejiadong. 00:25 (+1)

题意：完全背包，求价值 $\ge m$ 的时候需要的最小代价。

题解：可以发现，价值最大只需要 $m+max{v_i}$ ，所以只需要记录最多 $20000$ 的状态。

完全背包，暴力转移即可。

Problem D

Solved by Weaver_zhu. 01:46 (+1)

Problem E

Unsolved.

Problem F

Solved by Kilo_5723. 00:17 (+)

题意：有 $n$ 堆石子，每次从石子最多的堆挪出一个石子后，放到石子数最小的堆里。求这么操作 $m$ 次后两堆石子数量差最大的是多少。

题解：从石子数多的数个石子堆中拿 $m$ 个放到石子数少的数个石子堆里。map 维护。

Problem G

Solved by Kilo_5723. 03:30 (+2)

题意：给出一个电路图，求两点电阻。

题解：发现可以通过迭代解出答案，又发现迭代几次之后答案就几乎不会变了，所以迭代求解，如果答案的变化值已经很小就直接返回答案。

Problem H

Solved by Xiejiadong. 01:23 (+1)

题意：给出每个人持有的扑克牌，按照德州扑克的顺序排列。

题解：大模拟，按照题意写就完事了。

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 04:51 (+1)

题意：生成一个 $n$ 个点的随机有向图，其中每个点的入度出度都是 $1$，且每一个联通块都是一个环，求有多大的概率使得其中最大环的大小 $<x$，其中 $x>\frac{n}{2}$。

题解：考虑枚举非法最大环的大小。因为 $x>\frac{n}{2}$，所以非法最大环只会存在一个。那么，我们要求的就是 $m$ 个点能构成多少有向环图。可以找到递推式并不断化简，也可以通过打表找规律发现是 $m!$。于是，就可以枚举最大环对贡献求和，除以总数就是答案。

Problem K

Solved by Kilo_5723. 02:42 (+2)

题意：长度为 $k$ 的序列 $\{a_k\}$，规定

\begin{equation} f(n)=\left\{ \begin{aligned} a_n && n \le k \\ \sum_{i=1}^k p_i \cdot f(n-i) && n > k \end{aligned} \right. \end{equation}

其中 $\sum_{i=1}^kp_i=1$，并给出 $f(k+1)$ ~ $f(2*k)$，求 $\sum_{i=1}^n f(i)$。

题解：通过 $f(1)$ ~ $f(2*k)$ 高斯消元求出 $p_1$ ~ $p_k$，再通过矩阵快速幂求出 $\sum_{i=1}^n f(i)$。