题解：P12099 [NERC2024] Hunting Hoglins in Hogwarts

KK_lang · 2025-12-18 17:23:53 · 题解

【评价】

想了一下午进行的全是无效思考。想到解法后感觉何意味。

真的好牛。

【题解】

如果交互库自适应或者有策略，那次数一定不能少于 n。

所以我们的做法肯定是基于随机的，n 特别大，所以肯定是二分状物去做。

如果发出一声巨响，我们考察这意味着什么。

说明有怪物的移动路线越过了墙，所以他此时不会动；如果没有发出巨响，说明移动始终在一段连续区间内进行。

二分地去做的话：放置 mid，如果没有发出巨响，说明霍格林在 mid 一侧内活动，但他此时的可见范围并未缩小，所以再撞墙可能还是 mid；否则说明他尝试越过 mid 未果，仍然留在一侧，并且不会尝试往外走。

我们无法知道他在哪一侧。我们能否得知？

我们肯定先等当前 mid 发出巨响之后再进行操作，这样使他的可见范围缩小，从而不会混淆信息。

所以我们在左侧 mid_L 再放一堵墙，等待 inf 多次，直到一声巨响，这样我们就能判断他在左边，或者从此可以断言不在左边。

此时我们知道了在哪一侧。最坏情况下，霍格林总在右边，所以在左边放墙除了排除左边不会带来任何额外信息。我们每次二分需要 inf 次知道是否在一侧，这样做是非常非常劣的。

考虑为什么会这么劣。按理来说，如果这一段有怪物，他期望 2 次就能撞到墙；但是如果没怪物的话，我们需要 inf 次才能笃定地确认这里没有。

如果我们知道有一个区间很有可能有怪物，我们在二分下一轮先去询问这个就可以优化 inf 个询问。

我们肯定需要在每个区间里都放一次墙。在原方案中，我们为了避免混淆信息，我们首先问了每个区间 inf 次来知道是否有，这样再去做下一个才能保证如果响了，就在那里。

我们能不能把这个优化？

如果我们不问 inf 次，就使劲放，那么如果响了，我们能不能知道，在若干个区间内，究竟是哪个撞了？