题解 P8566

· · 题解

Solution 1

手玩 n\le 5，期望通过数据点 1,2。如果有惊人的毅力可以手玩 n \le 7，通过数据点 3,4。

写一个爆搜或者状压 dp，期望通过数据点 1 \sim 6。如果写的不好可能过不了 n=8 的点。期望代码量 4\text{kb}，非常不好写。

Solution 2

本题的主要部分就是猜测和验证以下的一系列结论。诱导出结论的过程大致是从两头开始优化最终达到的平衡。

一种观点是每一次 Yes 会将整个游戏分治成两个游戏。在之后的题解中也会多次用到这个观点，我们会运用【当前的多边形】来表示被分治出来的某个游戏。之后我们会发现被在最优情况下分治出来的游戏只有一个还有再提问的空间。

结论 0 B 不会询问和已经确定存在的边相交的边，因为这些边肯定不存在。

结论 1 最优的 k=2n-6。

证明 注意到 2n-6=2(n-3)，之后我们的策略也会往“一次 Yes 回答对应一次 No 回答"这个方向去靠拢。

此外注意到一次 Yes 询问相当于是将整个游戏分治成了两个游戏，当然和这次 Yes 相交的 No 也就不带来任何额外信息了。从这一点我们很容易看出 A 有如下策略：回答 Yes 当且仅当这次询问和之前的询问相交，这样一次 Yes 至少对应一次 No，也就是 k \ge 2n-6。

而从同样的角度思考，我们也能给出一种 B 的策略。B 不断询问长度为 2 的边，并且保证被询问到的边是连续的一段。如果得到 Yes 的答案，有一个 No 白费了，并且 n 减少了 1，因此这个方案最多询问了 2n-6 次。

当然上述证明可能会带来疑问，例如会不会围成一圈了还没有得到答案。这当然是不会的，因为统计边数就能得知整个三角剖分至少有两条长为 2 的弦。

结论 2 所有一直最优的策略如下：对于 B，每一次询问之后得到的所有 No 必须是当前的多边形中一些连续的长为 2 的弦（指弦的中点连续）；并且除非已经得到了 n-3 次 No，也就是确定了剩余部分是一个点连出若干条边以外可以任意顺序问这个已知的三角剖分以外，必须继续询问长度为 2 的弦。对于 A，由于 B 必须采用上述策略，只用所有 Yes 的时候都有相交就行。

证明 上面的叙述中已经证明了 A 的策略（在假设 B 的策略的前提下），这里主要证明 B 的策略。

我们引入 坏弦 的定义，一条弦为坏的当且仅当它没有被问过，并且存在一种使得这条弦答案为 Yes 的问题，并且和两条以上问过的 No 相交。如果任意时刻出现坏弦，那么 A 告诉 B 这条弦答案为 Yes，B 必须询问这条弦，那么就亏了一次以上的操作。到这里可以用归纳法证明结论，然而这种证明要对前几条弦进行繁琐的讨论（可能要四步以上才会出现坏弦），感兴趣的读者可以自行补全。

这里叙述一个较为简短但是不那么自然的证明，同时可以引入一个比较好玩的结论。

引理 对于任意 n-3 条弦，存在一个不包含其中任意一条弦的三角剖分。更进一步地，除非这 n-3 条弦是相邻的长为 2 的弦，这个三角剖分都不唯一。

如果有了引理，A 可以无脑回答 n-3 次 No；这样如果 B 某一次操作不按照要求，n-3 次后还无法唯一确定，那么肯定不能在 2n-6 次中得到答案。并且即使最后是 n-3 条相邻的长度为 2 的弦，任意时刻也必须连续，否则会出现坏弦。

引理证明 我们对 n 归纳，n\le 5 的情况容易验证。下面假设 n\ge 6 并且 n-1 时结论成立。

首先证明这样的三角剖分存在。考虑所有长度为 2 的弦，一定有一条没有被选上。如果没有任意一条选上，任选一条和某条禁止的弦相交的弦；否则选择最边上一条长度为 2 的弦再旁边一条。这样如果去掉和被选上的弦相交的弦就规约到了 n-1 时的归纳假设。

当然唯一性也很好顺着上面的思路归纳得到。假设变成 n-1 后不唯一，并且形成了多边形 x_1x_2\cdots x_{n-1}，其中 x_ix_{i+2}(1 \le i \le n-4) 连边。

考虑是从什么角度扩展来的。如果被缩掉的点 X 在某个 x_ix_{i+1} 之间，其中 1 \le i \le n-3，那么考虑改连 Xx_{n-1}，分出的两个部分不包括缩点时去掉的弦分别含有 u-4,v-4 条弦（u,v 为这两部分的大小），那么加上一条弦最多 u-3,v-3，并且有一部分取不到等，肯定至少两种情况。另外两种对称的情况只用考虑一种，也就是在 x_{n-1}x_1 之间，这时如果那条弦是 Xx_2 那么就是所说的唯一的情况；否则是 xx_{n-2}，改连 x_{n-1}x_{n-3} 就只剩下 n-1 个点和 n-5 条边，肯定有至少两种情况。证毕。

实现

直接拿链表甚至 set 来维护都行，主要不要漏情况，尤其是重复询问。用中点表示弦可以节省代码量。时间复杂度视实现为 O(n) 或者 O(n\log n)。

后记