求问一种思路是否能够过题
查看原帖
求问一种思路是否能够过题
684254
Rain_chr楼主2024/9/29 14:44

赛时思路,想了很久没有进展,求问按这个思路往下想能不能做。

首先可以发现此游戏由Nim扩展,第一反应肯定是先打表输出异或和,发现以下结论:

  1. 初始局面异或和不为零是先手必胜的充分条件

  2. 初始局面异或和为零是先手必败的必要条件

至于为什么这两个结论每一个是充要条件,是因为存在一种特殊局面:异或和为 0 但是先手必胜的局面,比如 1 2 3 这样的局面。

进一步发现,本题判断先手必败的充要条件是所有数出现次数为偶数,于是场上拿到了判断的 20 分,拼了一个Nim游戏的分同时过了第一个点一共拿到 36分。

于是我就开始往特殊局面为什么能够先手必胜这一方面思考,想到之所以其能够胜利是因为这种特殊局面虽然异或和为零,但他能通过让别的堆加石子保持异或和为0 的局面。

但是我始终不会构造保持异或和为 0 的操作,求助这种局面是否能够被构造(时间复杂度不重要,因为赛时我理论最高 n2V2n^2 V^2 的代码没有 TLE),以及如果可以构造是否具有正确性?

2024/9/29 14:44
加载中...