赛时思路,想了很久没有进展,求问按这个思路往下想能不能做。
首先可以发现此游戏由Nim扩展,第一反应肯定是先打表输出异或和,发现以下结论:
-
初始局面异或和不为零是先手必胜的充分条件
-
初始局面异或和为零是先手必败的必要条件
至于为什么这两个结论每一个是充要条件,是因为存在一种特殊局面:异或和为 0 但是先手必胜的局面,比如 1 2 3 这样的局面。
进一步发现,本题判断先手必败的充要条件是所有数出现次数为偶数,于是场上拿到了判断的 20 分,拼了一个Nim游戏的分同时过了第一个点一共拿到 36分。
于是我就开始往特殊局面为什么能够先手必胜这一方面思考,想到之所以其能够胜利是因为这种特殊局面虽然异或和为零,但他能通过让别的堆加石子保持异或和为0 的局面。
但是我始终不会构造保持异或和为 0 的操作,求助这种局面是否能够被构造(时间复杂度不重要,因为赛时我理论最高 n2V2 的代码没有 TLE),以及如果可以构造是否具有正确性?