当前位置: 代码迷 >> 综合 >> Anti-nim博弈 John poj3480
  详细解决方案

Anti-nim博弈 John poj3480

热度:90   发布时间:2023-12-14 03:35:07.0

传送门:点击打开链接

题意:和nim游戏一样,只不过取最后一个石子的人输。

思路:有一个SJ定理,是专门用来求Anti-nim游戏的,如下

SJ定理
SG函数的求法一模一样,最后如果只有一堆,也能用SJ定理
如果为Anti-Nim游戏,如下情况先手胜
SG异或和为0,且单个游戏的SG全部<=1
SG异或不为0,且存在单个游戏的SG>1,即<=1的个数不等于独立游戏个数

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt
  相关解决方案