Alan233

发布于 2024-10-05 22:02 浙江

+ 关注

2024 牛客 OI 赛前集训营-提高组（第一场）

牛牛找三元组

观察到该式子是个轮换对称 (cyc) 的式子，考虑 $a_i,a_j,a_k$ 在质因子 $p$ 下的指数分别为 $x,y,z$ ，不妨设 $x<y<z$ ，计算可知分子分母的指数恰好相等。因此，该式子是个恒等式。

对于 $n<2$ ，输出 $\texttt{-1 -1 -1}$ ；

对于 $n\ge3$ ，输出任何一个合法三元组均可。

时间复杂度： $O(n)$ 。

牛牛研究大图

注意到这个边权涉及到 $\sqrt{\frac{y}{x}}$ ，因此从 $x$ 跳到 $y$ ，我们一定尽可能从 $x$ 跳到 $k^2x$ ，这样显然不会比从 $x$ 跳到 $((k+1)^2-1)x$ 劣。

边权最大也只有 $\sqrt{3000}$ ，下取整得 $54$ ，而在 $10^9$ 范围内，从 $x=1$ 出发，走 $k^2x\ (k\ge 2)$ 能到达的数打表发现只有 $5342$ 个点，故预处理跑 spfa 求出所有可达的位置的距离即可。

查询只需要找到第一个 $\le y$ 的位置，从这个位置可以走 $0$ 边权到达 $y$ 。

fib 树上博弈

问题可以看作每次删一条边 $(u,v)$ ，保留根节点所在的连通块，删不了边的一方输。

我们先用 Grundy Number 判断当前局面的胜负。定义 $f_u$ 为以节点 $u$ 为根的子树的 Grundy Number。如果 $f_1$ 是 $0$ ，后者胜；否则，前者胜。

考虑如何计算 $f$ 。假设 $u$ 有若干个儿子 $v_1,v_2,\cdots,v_k$ ，注意 $u$ 与 $v$ 之间的这条边，定义 $g_v$ 为以节点 $v$ 为根（含 $v$ 的父边）的子树的 Grundy Number，我断言 $g_v=f_v+1$ 。

证明考虑第二数学归纳法，按 $v$ 的子树大小归纳：
若删除 $v$ 的父边，Grundy Number 显然是 $0$ ；
若删除其余边，由归纳知 Grundy Number 为 $1,2,\cdots, f_v$ ；
因此 $g_v=\text{mex}\{0,1,2,\cdots,f_v\}=f_v+1$ 。

因此 $f_u=\bigoplus\limits_{i=1}^{k} \left(f_{v_i}+1\right)$ 。

这一部分是 AGC017 D. Game on Tree。

20 分

《看图说话》

40 分

枚举删除每个节点，然后对 $\text{tree}'(n)$ 暴力 dfs 博弈。期望得分 40 分。

70 分

注意到 $\text{tree}(n)$ 的节点个数为 $\text{fib}_{n+2}-1$ ，其中 $\text{fib}_1=1,\text{fib}_2=1,\text{fib}_n=\text{fib}_{n-1}+\text{fib}_{n-2}\ (n\ge 3)$ 。

枚举删除每个节点，然后检验根的 Grundy Number 是否为 $0$ 。

时间复杂度 $\mathcal O((\text{fib}_{n+2})^2)$ ，其中 $\text{fib}_{20}=6765$ ，期望得分 60 分。

100 分

现在我们寻找第一步所有的必胜点。记 $\text{ways}_{i,j}$ 表示 $\text{tree}(i)$ 中有多少个点 $u$ 满足：删除以 $u$ 为根的子树后， $\text{tree}_i$ 的根的 Grundy Number 为 $j$ 。

转移是容易的： $\text{ways}_{i,j}=\text{ways}_{i-1,j\oplus (f_{i-2}+1)-1}+\text{ways}_{i-2,j\oplus (f_{i-1}+1)-1}$ ，其中 $f_i$ 表示 $\text{tree}(i)$ 的根的 Grundy Number。