题解 P3825 【[NOI2017]游戏】

这道题很多人的提交交到uoj上会获得97分。

这是因为实际上 $O(2^d\times N)$ 如果被一组无解的数据卡的话就会跑满。

很多人的常数比较大就会TLE(当然你常数小就不会)。

所以我们考虑随机化。每次DFS时随机枚举当前 $x$ 是 $a$ 还是 $b$ 。然后如果次数超过一定程度就直接输出无解。

可以证明这样出错的概率是极低的。


发表于 2018-04-11 21:08:50 in 题解