Codeforces Gym 100015 简要题解

A. Another Rock-Paper-Scissors Problem

归纳一下可以发现这就相当于求 $N$ 在三进制下的表示。

时间复杂度：$O(\log N)$

用 $f_{i, j}$ 表示有 $j$ 个球被涂黑且这些球总共占用 $i$ 行的方案，枚举最后一个球是否占用了一个新的列可得递推式

$$ f_{i, j} = f_{i, j - 1} \times (2i - j + 1) + f_{i - 1, j - 1} \times 4$$

预处理后直接输出即可。

时间复杂度：$O(N^2)$

基环树上最短路。实现起来稍微有点麻烦的板子题。

时间复杂度：$O(N)$

令 $f_i, p_i$ 分别表示在原图上从 $i$ 点开始走的期望边数以及从 $1$ 点开始走经过 $i$ 点的概率。

$$f'_u = \frac{f_u \times w_u - w_e(f_v + 1)}{w_u - w_e}$$

其中 $w_u$ 表示 $u$ 的所有出边的权值和，$w_e$ 表示边 $e$ 的权值。

$$f_1 + p_u(f'_u - f_u)$$

枚举所有边然后取最大值即可。

时间复杂度：$O(M)$

暴力求出所有交点，暴力建边。

注意到抽象成图后每个点的度数恰好为 $4$，因此可以暴力求三元环的个数。

时间复杂度：$O(N^2 \log N)$

用 $f_S$ 表示当前已经有集合 $S$ 中所有边的情况下先手与后手得分差的最大值。

状压 DP 预处理后直接查询即可。

时间复杂度：$O(N \cdot 2^N)$

注意到 $a_i + b_j \leq c \Leftrightarrow a_i - (- b_j) \leq c$ 以及 $a_i + b_j \geq c \Leftrightarrow (-b_j) - a_i \leq c$，这是差分约束的形式。于是建图之后判断图中是否存在负环即可。

时间复杂度：$O(Q(N+M))$

显然两个串做差之后的结果要么是密码串的一个前缀，要么是密码串后面加上加密结果的一个前缀。

枚举长度检查即可。

时间复杂度：$O(Nl^2)$

想不出来有什么正经做法。反正我是枚举若干个特值检查来的。