Auti - nim Game
Nim 游戏变种,认定方式改为谁取走最后一个石头就输。
先手胜当且仅当
(1)所有堆石子数都为 1 且游戏的 SG值为 0 。
(2)存在某堆石头数大于 1 且游戏的 SG 值不为 0 。
证明:
(1)若所有堆石头数都为 1 且 SG 值为 0,则共有偶数堆石头,所以先手胜。
(2)
(i) 只有一堆石头数大于 1 时,我们总 可以对该堆石子操作,使得操作后石子堆数为奇数且所有堆的石子数均为1
(ii)有超过一堆石子数大于 1 时,先手将 SG 值变为 0 即可,且存在某堆石子数大于 1。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 5000; int a[maxn]; int main() { int T; scanf("%d",&T); while(T--) { memset(a,0,sizeof(a)); int n; scanf("%d",&n); for(int i = 0; i < n; i++) scanf("%d",&a[i]); int ans = 0, res = 0; for(int i = 0; i < n; i++) { if(a[i] == 1) ans++; res ^= a[i]; } if((ans == n && !res) || (ans != n && res)) puts("John"); else puts("Brother"); } return 0; }