专栏文章

P11516 题解

IIsaacX
P11516题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqadqw2
此快照首次捕获于
2025/12/04 01:34
3 个月前
此快照最后确认于
2025/12/04 01:34
3 个月前
查看原文
P11516 CCO 2024 Summer Driving
博弈终止节点编号大小，这提示我们直接按双方策略 dp。
先考虑一些部分分。
Sub1：A≤BA \le B 时，相当于每次往 11 的方向走 B−AB-A 步，最终一定走到 11。
Sub2：最后的停止点显然由 Bob 决定，线段树优化 dp。
考虑把 Sub2 的做法拓展到树上，设 fu,guf_u,g_u 表示 Alice/Bob 在点 uu 时的结果。额外地设 fu′f'_u 表示当前在 faufa_u，不能走进 uu 的子树的结果。
设 F(u,x)F(u,x) 为 uu 子树内距离 uu 等于 xx 的点集，G(u,x)G(u,x) 表示距离 uu 不超过 xx 的点集（不含祖先），Par(u,x)Par(u,x) 表示 uu 的 0∼x−10 \sim x-1 级祖先。
fu=max⁡v∈F(u,A)gvgu=min⁡{min⁡v∈G(u,B)fv,min⁡v∈Par(u,B)fv′}f_u=\max_{v \in F(u,A)}g_v\\ g_u=\min\{\min_{v\in G(u,B)}f_v,\min_{v\in Par(u,B)}f'_v\}
现在你已经会 O(n2)O(n^2) 了。（在 Alice 无路可走的时候 fuf_u 的转移有变，但也可以简单计算）
考虑优化 dp。
  1. 对于 ff 的转移，不难发现每个 gvg_v 只会被一个 fuf_u 用到，均摊 O(n)O(n)。
  2. 对于 gg 的转移，min⁡v∈Par(u,B)fv′\min_{v\in Par(u,B)}f'_v 树剖，min⁡v∈G(u,B)fv\min_{v\in G(u,B)}f_v 点分树（吗？）。
发现 kk 邻域可以模板点分树，然而扣掉祖先后就不行了。

做法一

但是如果我们要查的是 ∑v∈G(u,B)fv′\sum_{v\in G(u,B)}f'_v 而不是 min⁡\min 就能做了。
于是我们在最外层二分一个答案 AnsAns，编号 ≤Ans\le Ans 的点为白点，编号 >Ans>Ans 的为黑点。把 fuf_u 定义改成“能否走到一个黑点”，gu,fu′g_u,f'_u 同理。
然后我们就要查询类似“uu 的 kk 邻域内有没有 11”的形式，就可以愉快地上点分树了。
复杂度 O(nlog⁡3n)O(n \log^3 n)，盲猜过不了。

做法二

假设当前查询的点为 xx，在点分树上跳 lcalca。对于 yy。
  • x,yx,y 不能在 lcalca 的同一颗子树内。
  • yy 在原树上不能是 xx 的祖先，不难发现如果这样的话 yy 一定是 lcalca 的祖先，在加入线段树时排除这些点即可。
对于点分树上每个点开一颗树状数组，每个位置维护最大值所在子树和其他子树的最大值。
复杂度 O(nlog⁡2n)O(n\log^2 n)，比当前次优解快 0.8s。
代码放 LOJ 上了。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...