P6896 [ICPC 2014 WF] Maze Reduction 题解

· · 题解

:::::info[闲话]{open} 我们充分发挥人类智慧，后面忘了。 ::::: :::::success[Hint 1] 考虑何时能区分任意两个点。 ::::: :::::success[Hint 2] 考虑通过随机化决策向那个点偏移。 :::::

对应 Hint 1：

首先我们考虑对于一对点 (u,v) 何时我们能区分这两个点，我们发现我们每进入一个点唯二知道的就是这个点的度数和上一步我们是从哪个点到来的，那么由于每个点的相邻的点是按顺时针给出的，那么我们在到达一个点后（除一开始）可以规定一个下一个点相对于上一个点的相对位置。

由于每个点是从任意一个相邻的点开始顺时针给出的，那么我们给两个点之间钦定一个偏移量 k，然后对于 u 向某个点偏移 v 就向与其相对位置为 k 的那个点偏移，接下来不断从 u 和 v 的相同方向的点（相同方向指与上一个点的相对位置相同）偏移，只要不管怎么走到达的点的度数都相同那么这个 k 就合法，进而 (u,v) 不可区分，否则两点可区分。

对应 Hint 2：

考虑根据上述直接直接得出算法，首先枚举 u,v,k，考虑不断从 u 和 v 的相同方向的点偏移这一步我们怎么决策。

我们充分发挥人类智慧，对向哪个点偏移进行随机化，然后我们随机 10000 次，然后我们发现这个算法得到了比较高的正确率，然后我们就过了。

具体实现细节详见代码。

code