首页 > 代码库 > HDU 3032 Nim or not Nim? [Multi-SG]

HDU 3032 Nim or not Nim? [Multi-SG]

传送门

题意:

nim游戏,多了一种操作:将一堆分成两堆


 

Multi-SG游戏规定,在符合拓扑原则的前提下,一个单一游戏的后继可以为多个单一游戏。

仍然可以使用$SG$函数

然后本题规模很大,手动打一下表,发现$%4=3$时$sg(x)=x+1$,$%4=0$时$sg(x)=x-1$,其他不变

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=1e6;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}int n;inline int cal(int a){    int t=a%4;    return t==0 ? a-1 : (t==3 ? a+1 : a);}int main(){    freopen("in","r",stdin);    int T=read();    while(T--){        n=read();        int sg=0;        for(int i=1;i<=n;i++) sg^=cal(read());        if(sg) puts("Alice");        else puts("Bob");    }}

 

HDU 3032 Nim or not Nim? [Multi-SG]