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

逃离我推掉我的手 2022-03-30 10:14 154阅读 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 条评论，154人围观）

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

相关阅读

相关 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 赞/ 71 阅读

相关 hdu 5011 nim博弈变形

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

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

相关 Misere Nim （Nim博弈）

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

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

相关 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 赞/ 131 阅读

相关 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 赞/ 128 阅读

相关 HDU-3404 Switch lights（NIM积）

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

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

相关 leetcode 292. Nim Game Nim游戏

You are playing the following Nim Game with your friend: There is a heap of stones on th

太过爱你忘了你带给我的痛/ 2022年06月08日 14:29/ 0 赞/ 162 阅读

相关 LeetCode 292 Nim Game（Nim游戏）

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每一步都是最优解

电玩女神/ 2022年05月13日 06:38/ 0 赞/ 180 阅读

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

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

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

相关 HDU3032 Nim or not Nim?

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

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