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

逃离我推掉我的手 2022-03-30 10:14 215阅读 0赞

[传送门][Link 1]

题意：

nim游戏，多了一种操作：将一堆分成两堆

--------------------

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

仍然可以使用$SG$函数，**分成多个游戏的后继$SG$值为多个游戏的异或和**

然后本题规模很大，手动打一下表，发现$\\mod 4=3$ 时$sg(x)=x+1$，$\\mod 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");
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3032

发表评论取消回复

表情：

评论列表（有 0 条评论，215人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu1849 Nim博弈

<table style="font-family:'Times New Roman'; word-wrap:break-word"> <tbody>

ゝ一纸荒年。/ 2024年02月18日 14:13/ 0 赞/ 50 阅读

相关 HDU 3032 Nim or not Nim?(SG打表找规律)

题意：给你n堆石子，你每次只能操作一堆石子 1、拿去任意个，最少1个 2、把这一堆分成两堆，没有要求对半分解析+代码： 1 //解题思路：

Myth丶恋晨/ 2023年10月11日 09:36/ 0 赞/ 17 阅读

相关 hdoj3032 Nim or not Nim?（可分解尼姆）

Nim or not Nim? Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768

电玩女神/ 2022年08月26日 00:54/ 0 赞/ 127 阅读

相关 hdu 5011 nim博弈变形

Game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java

约定不等于承诺〃/ 2022年08月08日 14:51/ 0 赞/ 144 阅读

相关 Misere Nim （Nim博弈）

Misere Nim （Nim博弈）：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620\problem

- 日理万妓/ 2022年07月28日 09:46/ 0 赞/ 188 阅读

相关 HDU 2311-Nim or not Nim?（Nim博弈-打sg表找规律）

Nim or not Nim? Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (J

爱被打了一巴掌/ 2022年07月24日 04:07/ 0 赞/ 197 阅读

相关 PE 301 Nim （Nim博弈）

Nim Problem 301 Nim is a game played with heaps of stones, where two players take

骑猪看日落/ 2022年07月13日 05:55/ 0 赞/ 199 阅读

相关 HDU-3404 Switch lights（NIM积）

Switch light [HDU - 3404 ][HDU - 3404] lxhgww is

小鱼儿/ 2022年06月10日 06:09/ 0 赞/ 115 阅读

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

[传送门][Link 1] 题意： nim游戏，多了一种操作：将一堆分成两堆 -------------------- Multi-SG游戏规定，在符合拓扑原则的前提下

逃离我推掉我的手/ 2022年03月30日 10:14/ 0 赞/ 216 阅读

相关 HDU3032 Nim or not Nim?

![1332167-20190318144402305-108867769.png][] 解：使用sg函数打表发现规律，然后暴力异或起来即可。 ![Contracte

向右看齐/ 2021年12月22日 16:41/ 0 赞/ 227 阅读