hdu1536 博弈模板

傷城~ 2022-08-18 15:26 3阅读 0赞

题意就是给出一个数组s。为每次可以取石子的数目。 然后给你n堆石子每堆si。求解先手能不能赢！标准的sg函数用法题目。

#include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
    
    int s[101];//存放每次可以取得石子，即可以进行的步骤
    
    int sg[10001]; //每个石子堆的sg函数值
    
    int k;  //每次可以取石子的个数总和
    
    int getsg(int m) 
    { 
        int hash[101]={0}; 
        int i; 
        for(i=0;i<k;i++){ 
            if(m-s[i]<0) 
            {
                break;
            }
            if(sg[m-s[i]]==-1) 
            {
                sg[m-s[i]]=getsg(m-s[i]); 
            }
            hash[sg[m-s[i]]]=1; 
        } 
        for(i=0;;i++)
        {
            if(hash[i]==0)
            {
                return i;
            }
        }
    } 
    
    
    int main(){
        while (cin>>k && k)
        {
            for (int i = 0; i < k;i++)
            {
                cin>>s[i];
            }
            sort(s,s+k);
            memset(sg,-1,sizeof(sg));
            sg[0] = 0;
            int t;
            cin>>t;
            while (t--)
            {
                int n,m;
                cin>>n;
                int ans = 0;
                while (n--)
                {
                    cin>>m;
                    if (sg[m]==-1)
                    {
                        sg[m]=getsg(m);
                    }
                    ans ^= sg[m];
                }
                if (ans == 0)
                {
                    cout<<"L";
                }
                else cout<<"W";
            }
            cout<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 hdu1849 Nim博弈

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

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

相关 HDU 3389 Game (阶梯博弈)

题意：给你n个盒子，从1---n，你每次要找出来两个盒子下表分别是a，b；它们要满足(a+b)%2==1 && (a+b)%3==0,找到盒子之后要从b向a中拿过去至少1个

╰半橙微兮°/ 2023年10月11日 09:37/ 0 赞/ 3 阅读

相关博弈论--巴什博弈——HDU1846

/\巴什博弈：HDU--1846\/ \ include<iostream> using namespace std; int main() \{ int

以你之姓@/ 2022年08月27日 09:52/ 0 赞/ 196 阅读

相关博弈之sg函数（模板）

组合博弈的通解就是sg函数，学习了sg函数之后一直没有咋用过。学习博弈的可以在nyoj上面做10道取石子题目，作为了对博弈也就有一定理解了。用的时候注意初始的时候只要初

亦凉/ 2022年08月26日 00:41/ 0 赞/ 176 阅读

相关 hdu1536 博弈模板

题意就是给出一个数组s。为每次可以取石子的数目。然后给你n堆石子每堆si。求解先手能不能赢！标准的sg函数用法题目。 include <iostream>

傷城~/ 2022年08月18日 15:26/ 0 赞/ 4 阅读

相关 hdu 5011 nim博弈变形

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

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

相关尼姆博弈 HDU2176

有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，

àì夳堔傛蜴生んèń/ 2022年08月07日 06:53/ 0 赞/ 130 阅读

相关巴什博弈 HDU2188

巴什博弈是个很经典的游戏。就是只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。那么我们可以找到一

素颜马尾好姑娘i/ 2022年08月07日 06:37/ 0 赞/ 159 阅读

相关 hdu 1846 博弈

十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。

迷南。/ 2022年08月03日 14:39/ 0 赞/ 137 阅读

相关 hdu 1564 博弈

其实是瞎猜的，尽然猜对了。。看网上的做法，可以给n\n的地面上铺上2\1的地面砖，如果n是偶数的话可以全部竖着铺满，如果是奇数的话最后一行要横着铺一些，只剩下起始位置没

Love The Way You Lie/ 2022年08月03日 14:37/ 0 赞/ 5 阅读