2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260 [2020/08/14 12:52] nikkukun 创建 |
2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260 [2020/08/14 16:59] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| - $p, q$ 都是偶数，那么 Bob 下模仿棋，最后两人各占领一半； | - $p, q$ 都是偶数，那么 Bob 下模仿棋，最后两人各占领一半； | ||
| - | - $p, q$ 一奇一偶，那么 Alice 优先取奇数的那一侧，接着模仿 Bob 走即可。 | + | - $p, q$ 一奇一偶，那么 Alice 优先取奇数的那一侧，接着模仿 Bob 走即可； |
| - $p, q$ 都是奇数，那么 Alice 第一步有两种选择，接下来都只需要模仿 Bob 走即可，因此 Alice 优先选择让差较大一点的那一侧。 | - $p, q$ 都是奇数，那么 Alice 第一步有两种选择，接下来都只需要模仿 Bob 走即可，因此 Alice 优先选择让差较大一点的那一侧。 | ||
| 行 35: | 行 35: | ||
| 有 $n \leq 10$ 个写了数字的卡片 $a_1, a_2, \ldots, a_n$，Alice 和 Bob 轮流从里面选择一个尚存的卡片，若上面的数字为 $x$： | 有 $n \leq 10$ 个写了数字的卡片 $a_1, a_2, \ldots, a_n$，Alice 和 Bob 轮流从里面选择一个尚存的卡片，若上面的数字为 $x$： | ||
| - | - 有 $\dfrac 1x$ 的概率成功，选择者的得分 $+x$，同时移除该卡片； | + | * 有 $\dfrac 1x$ 的概率成功，选择者的得分 $+x$，同时移除该卡片； |
| - | - 有 $1 - \dfrac 1x$ 的概率失败，无事发生； | + | * 有 $1 - \dfrac 1x$ 的概率失败，无事发生。 |
| 当所有卡片都取完时，得分大的人获胜；若最终同分，则 Bob 获胜。 | 当所有卡片都取完时，得分大的人获胜；若最终同分，则 Bob 获胜。 | ||
| - | 求两人在最优策略下，Alice 的初始胜率。 | + | 求两人在最优策略下，Alice 作为先手的初始胜率。 |
| 行 69: | 行 69: | ||
| ===== D - 10億ゲーム ===== | ===== D - 10億ゲーム ===== | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| （交互题）Alice 和 Bob 各有一个 $10^9$ 的因子，从 Alice 开始轮流对各自的数 $x$ 进行下列一种变换： | （交互题）Alice 和 Bob 各有一个 $10^9$ 的因子，从 Alice 开始轮流对各自的数 $x$ 进行下列一种变换： | ||
| 行 81: | 行 83: | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| - | 若数字可以分解为 $2^x 5^y$ 的形式，则实际相当于两人在 $[0, 9] \times [0, 9]$ 的格点上移动棋子，棋子每次能往上下左右四个方向移动一步，Alice 的目标是追上 Bob。 | + | 若数字可以分解为 $2^x 5^y$ 的形式，则实际相当于两人在 $[0, 9] \times [0, 9]$ 的格点上从初始点 $(x, y)$ 移动棋子，棋子每次能往上下左右四个方向移动一步，Alice 的目标是追上 Bob。 |
| 这是个经典问题：若一开始两人距离是奇数，则 Alice 先走到 $(9, 9)$，然后会与 Bob 所在位置形成一个矩形。若矩形不是正方形，则 Alice 就向下或向左沿着较长一点的那条边移动，使得矩形变成正方形；若矩形是正方形，则每次 Bob 移动后，Alice 都沿着能继续保持正方形的方向移动。显然，这样 Alice 最后一定能在至多 $35$ 轮内抓住 Bob。 | 这是个经典问题：若一开始两人距离是奇数，则 Alice 先走到 $(9, 9)$，然后会与 Bob 所在位置形成一个矩形。若矩形不是正方形，则 Alice 就向下或向左沿着较长一点的那条边移动，使得矩形变成正方形；若矩形是正方形，则每次 Bob 移动后，Alice 都沿着能继续保持正方形的方向移动。显然，这样 Alice 最后一定能在至多 $35$ 轮内抓住 Bob。 | ||
| 注意本题中，利用操作 4 可以做到 $(7, 9) \to (9, 9)$ 的移动改变奇偶性，因此根据初始距离奇偶性确定要不要走这一步即可。 | 注意本题中，利用操作 4 可以做到 $(7, 9) \to (9, 9)$ 的移动改变奇偶性，因此根据初始距离奇偶性确定要不要走这一步即可。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== E - ねこちゃんゲーム ===== | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给定一棵 $n \leq 2 \times 10^5$ 个点的树，树上有 $m \leq 2 \times 10^5$ 只猫，第 $i$ 只猫在 $a_i$ 节点。每回合，Alice 和 Bob 轮流任选一只猫，将猫移动到其相邻的结点上，直到不能操作为止。对于猫 $i$，它不能移动到之前它呆过的节点，同时一个结点上可以有多只猫。 | ||
| + | |||
| + | 判断 Alice 作为先手是否必胜，若必胜给出第一步走法。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 显然这是一个组合游戏，只要求出猫猫以每个点为起点时对应的 SG 函数值即可。不妨假设已经以 $1$ 为根求出了每个点 $u$ 的 $\mathrm{SG}(u)$ 及其所有儿子节点 SG 函数值的出现次数 $\textit{cnt}_u$ 数组（用于求 $\mathrm{mex}$）。考虑换根 DP 正在处理 $u$ 为根的情况： | ||
| + | |||
| + | **转移 1**：父亲节点有一个 $\mathrm{SG}(\textit{pa})$：直接更新 $\textit{cnt}_u$，然后 $O(\textit{siz}_u)$ 更新 $\mathrm{SG}(u)$。 | ||
| + | | ||
| + | **转移 2**：准备转移到儿子节点 $v$ 上：这里不能像上面一样 $O(\textit{siz}_u)$ 更新，否则总的更新复杂度 $O(\sum _{u=1}^n \textit{siz}_u^2)$ 是不对的。考虑删掉 $\mathrm{SG}(v)$ 对 $\mathrm{SG}(u)$ 的影响，发现只有删掉后 $\mathrm{SG}(v)$ 的出现次数为 $0$，且 $\mathrm{SG}(v) < \mathrm{SG}(u)$ 时，$u$ 的 SG 函数值才会变成 $\mathrm{SG}(v)$，否则不变。这样做就是 $O(1)$ 的。 | ||
| + | |||
| + | 综上，计算出所有点为起点时对应的 SG 函数值是 $O(n)$ 的。为了输出方案，还需要知道每个点为根时相邻节点的 SG 函数值。可以归纳地证明，为了让 SG 函数为 $i$，至少需要 $2^i$ 个节点，因此所有节点的 SG 函数值不超过 $\log_2 n \leq 17$，额外记录一下这 $O(\log n)$ 个信息即可。 | ||
| + | |||
| + | 总时间复杂度 $O(n \log n)$。 | ||
2020-2021/teams/i_dont_know_png/nikkukun/yukicoder-contest-260.1597380772.txt.gz · 最后更改: 2020/08/14 12:52 由 nikkukun
