XIX Open Cup named after E.V. Pankratiev. Grand Prix of Peterhof

Contest Info

date: 2019.03.27 16:14-21:14

practice link

Solutions

A. Alice and Path

签到题。

E. Coin Tournament

题目大意:有\(n+m\)个人排成一行,当剩余人数大于\(1\)时进行一轮游戏,每轮游戏,处于当前编号最大的位置\(k\)的人要和\([\frac{k}{2}]\)位置的人进行比赛,有\(\frac{1}{2}\)的概率获胜,\(\frac{1}{2}\)的概率失败,败者退出,胜者占据\([\frac{k}{2}]\)这个位置,问后\(m\)个人获得最终胜利的概率之和。

题解:建出比赛的胜者树,每个叶子获胜的概率为\(2^{-depth}​\),对每个叶子单独计算求和即可。

F. Fizz and Buzz

签到题。

G. Game on Tree

题目大意:给定一棵有根树,两个人在上面玩游戏。先手每次可以选择一个非根的叶子结点,将它打上标记;后手每次可以走一步到相邻节点(也可以不走,起始在根)。后手如果走到一个未标记的叶子节点,那么获胜。

题解:显然后手不会停住不走,每一步一定是朝着叶子的方向走,不会走回头路。定义 \(dp_i\) 表示后手在 \(i\) 点的时候,先手要获胜至少需要预先删除的叶子节点的个数。那么叶子结点的 \(dp\) 值为 \(1\)。其余点的 \(dp\) 值为儿子节点的 \(\max(0,\sum dp-1)\)。如果根的 \(dp\) 值为 \(0\),那么先手获胜。

H. Jack and Jill

签到题。

I. Laws

题目大意:你有一个数 \(x\)\(1\le x\le 10^9\))。你每次可以将其加 \(1\),或者除以 \(2\)(如果能整除),或者除以 \(3\)(如果能整除)。现在让你用最少的加 \(1\) 操作将其变为 \(1\)

题解:bfs 求最短路。注意除以 \(2\) 和除以 \(3\) 是边权为 \(0\) 的点,所以要 push_front。并且每次扩展边权为 \(0\) 的时候,不能只枚举 \(\frac{x}{2}\)\(\frac{x}{3}\),而是要枚举所有的 \(\displaystyle \frac{x}{2^a3^b}\)。最短路至多是 \(\mathcal{O}(\log x)\) 的,每次扩展 \(\mathcal{O}(\log^2 x)\) 个点,总复杂度 \(\mathcal{O}(\log^3 x)\)

J. Cubic Path

题目大意:定义一个 \([0,2^{n})\) 中的整数组成的序列 \(\{x\}_{1}^{m}\) 合法,当且仅当该序列的每个元素互不相同,且对每个 \(1\le i<m\)\(x_{i}\)\(x_{i+1}\) 恰有一个二进制位不同。定义一个序列 \(x\) 是好的,当且仅当它合法,且不存在另一个合法的真子序列,开头结尾与 \(x\) 相同。求最长的好序列。\(n\le6\)

题解:我们证明,一个序列是好的,当且仅当它任意两个不相邻的元素不同的二进制位数不为 \(1\)。这个条件显然是必要的,否则我们只要把这两个元素中间的序列删去,仍然是一个合法的序列。对于充分性,我们从 \(x_{1}\) 只能走到 \(x_{2}\)\(x_{2}\) 只能走到 \(x_{3}\cdots\)。利用这个性质暴搜即可。

K. Red-Black Tree

题目大意:有一个\(n\le3000\)个点的二叉树(每个点最多两个儿子),并且认为每个节点空的儿子指向一个哨兵节点void。每个点可以是红色和黑色两种颜色,void节点固定为黑色。问是否有一种染色方案,使得不存在一条边两端的点都是红色,并且void到根的每条路径上的黑色节点个数相同。

题解:令dp[0/1][i][j]\(i\)的颜色为0/1,子树中所有void\(i\)的路径上的黑色节点数为j的可行性布尔状态。则枚举左右儿子的颜色和黑色节点数转移即可。