差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260 [2020/08/14 13:26]
nikkukun
+++ 2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260 [2020/08/14 16:59] (当前版本)
nikkukun
@@ 行 40: / 行 40: @@
 当所有卡片都取完时，得分大的人获胜；若最终同分，则 Bob 获胜。
-求两人在最优策略下，Alice 的初始胜率。
+求两人在最优策略下，Alice 作为先手的初始胜率。
@@ 行 69: / 行 69: @@
 ===== D - 10億ゲーム =====
+==== 题目描述 ====
 （交互题）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。
 注意本题中，利用操作 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)$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具