题解 P3825 【[NOI2017]游戏】

这道题很多人的提交交到uoj上会获得97分。 这是因为实际上 $O(2^d\times N)$ 如果被一组无解的数据卡的话就会跑满。 很多人的常数比较大就会TLE(当然你常数小就不会)。 所以我们考虑随机化。每次DFS时随机枚举当前 $x$ 是 $a$ 还是 $b$ 。然后如果次数超过一定程度就直接输出无解。 可以证明这样出错的概率是极低的。