日记

十分颓废。

Hot Potato# Link to

看到：$n \le 20$，直接状压。一开始设的状态是：$dp_{s,i}$ 表示已经走过的点的状态是 $s$，$i$ 的失败概率。但是我们发现：有了 $s$，已经可以确定 $i$ 是否失败了，而且这个状态转移也很麻烦。考虑换一种状态。

我们设 $dp_{s,i}$ 表示走过的点状态为 $s$，当前在 $i$ 的概率。考虑如何转移。我们设当前 $i$ 有 $cnt$ 个备选。循环每个与 $i$ 有边的点 $j$，那么显然转移有：$dp_{s \cup \{j\},j} \leftarrow dp_{s,i} \times \frac{1}{cnt}$。如果 $cnt = 0$，就把 $ans_i$ 加上 $dp_{s,i}$，表示这种状态会输，并不进行转移。

时间复杂度 $O(n^2 2^n)$，实现不能太劣。

Crashing Competition Computer# Link to

考虑设 $f_i$ 表示不保存打 $i$ 个字符的期望时间。那么显然有 $f_i = f_{i - 1} + 1 + p \times f_i$。转换一下就是 $f_i = \frac{f_{i - 1} + 1 + p \times r}{1 - p}$。

设 $dp_i$ 表示保存打 $i$ 个字符的期望时间。初始化就是 $dp_i = f_i$。转移有 $dp_i = \min_{j = 0}^{i}\{dp_j + t + f_{i - j}\}$。表示在 $j$ 的位置保存并打 $i - j$ 个字符。

最后答案就是 $dp_n + t$。

Dice Grid# Link to

唐题。

直接从 $[n,n]$ 开始 bfs 看看能不能给正方体的每个面都染色就行了。

后日谈 # Link to 后日谈

今天晚上有久违的 div.2。切掉 T3 就是半赢。切掉 T4 就是赢！