RainAir
My OI Blog
RainAir
「NOIP2016」天天爱跑步

题目链接

NOIP 史上最毒瘤的一个题目……花了 2h 总算肝出来了。

解题报告

暴力测试点

大力枚举时间然后统计答案就可以了…….简单的模拟题目。

期望得分 $25$ 分。

链情况

考虑链情况的每一个人只能向左或向右走,也就是 $s \leq t$ 向右,否则向左。我们考虑点 $v$ 的观察员,不妨发现他能观察到的向右的玩家应满足 $ s + w_v = v $ ,即 $ s=v-w_v $。

同理,对于向左走的玩家有 $ s=v+w_v $。

排序或者用桶来维护这个东西即可。

时间复杂度 $ O(nlogn) \to O(n) $。

期望得分 $40$ 分。

起点为1

我们钦定这个树的根是1,~~找一找规律~~ 发现点 $v$ 的观察员能够观察到的点当且仅当 $w_v= depth_v$,统计每个点的子树有多少个终点即可。

期望得分 $60$ 分。

终点为1

依然钦定,考虑一个点 $v$ 能看到的路径,显然该路径的起点应该在 $j$ 的子树里而且满足条件 $w_v + depth_v = l$,其中 $l$ 为链的长度。这个我们开一个全局的桶,每一次我们 $dfs$ 后统计桶的增量即可。

期望得分 $80$ 分。

无特殊情况

~~你都80分了还不满足过分了啊~~

依然钦定,总体考虑 $i$ 点能看到谁。

把上面两种情况整合一下:发现对于一条路径 $u\to v$,相当于可以拆成两条路径 $u\to lca$ 和 $lca\to v$。这样的话对于向上走的玩家 $i$ 点能看见应满足 $depth_u – w_i = depth_i$,即 $ depth_u = w_i + depth_i $。

同理:向下的路径满足的条件是 $ depth_v -depth_i = l – w_i $,其中 $l$ 是链长,移项也可以得到 $ depth_v – len = depth_i – w_i $。

对着两种路径进行差分(我觉得不像是差分),我们用一个桶来统计,下标表示等式右边的表达式,记录的值是左边的表达式,如果出现负数,整体左移即可(对增量没有影响)。

我们来考虑 $lca$ 会被重复计算,那么我们减掉 $lca$ 的一次贡献即可。

具体可看代码,

代码实现

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/60
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOIP2016」天天爱跑步
题目链接 NOIP 史上最毒瘤的一个题目......花了 2h 总算肝出来了。 解题报告 暴力测试点 大力枚举时间然后统计答案就可以了…….简单的模拟题目。 期望得分 $25$ 分。 链情况 考…
扫描二维码继续阅读
2018-11-08
标签
近期评论