51NOD 算法马拉松15（脱欧专场） B君的游戏(博弈)

发布时间：2020-12-13 21:11:15 所属栏目：PHP教程来源：网络整理

导读：传送门 B君的游戏 wwwwodddd (命题人) 基准时间限制：1 秒空间限制：131072 KB 分值: 40 B君和L君要玩1个游戏。刚开始有n个正整数 ai 。双方轮番操作。每次操作，选1个正整数x，将其移除，再添加7个数字 x1,x2…x7 。要求对 xi ，满足 0= xi x 且 xxi=xi

传送门

B君的游戏
wwwwodddd (命题人)
基准时间限制：1 秒空间限制：131072 KB 分值: 40
B君和L君要玩1个游戏。刚开始有n个正整数 ai 。

双方轮番操作。每次操作，选1个正整数x，将其移除，再添加7个数字 x1,x2…x7 。要求对 xi ，满足 0<= xi < x 且 x&xi=xi

注意0不能被选取，所以这个游戏1定会结束，而谁没法操作谁就失败。
B君根据自己的经验，认为先手胜率高1点，所以B君是先手。
B君想知道自己是不是必胜。
Input
第1行1个整数n (1 <= n <= 100000)
以下n行n个数ai (0 <= a_i < 2^64)
Output
如果先手必胜，输出”B”，否则输出”L”。
Input示例
4
1
2
3
4
Output示例
B

解题思路（官方题解）：
这是1个简单的SG博弈问题。

注意到每一个数的SG值，只和其中有多少个1有关。

所以我们写1个不太暴力的暴力。可以得到。

a[] = {0,1,2,4,8,16,32,64,128,255,256,512,1024,2048,3855,4096,8192,13107,16384,21845,27306,32768,38506,65536,71576,92115,101470,131072,138406,172589,240014,262144,272069,380556,524288,536169,679601,847140,1048576,1072054,1258879,1397519,2005450,2097152,2121415,2496892,2738813,3993667,4194304,4241896,4617503,5821704,7559873,8388608,8439273,8861366,11119275,11973252,13280789,16777216,16844349,17102035,19984054,21979742,23734709}

a[i]是数x包括i个1的时候的SG值。

然后，直接异或起来所有SG值便可。

My Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 1e5+5;
ULL a[MAXN];
int sg[] = {0,1,2,4,8,16,32,64,128,255,256,512,1024,2048,3855,4096,8192,13107,16384,21845,27306,32768,38506,65536,71576,92115,101470,131072,138406,172589,240014,262144,272069,380556,524288,536169,679601,847140,1048576,1072054,1258879,1397519,2005450,2097152,2121415,2496892,2738813,3993667,4194304,4241896,4617503,5821704,7559873,8388608,8439273,8861366,11119275,11973252,13280789,16777216,16844349,17102035,19984054,21979742,23734709};

int main()
{
    int n;
    while(cin>>n)
    {
        int ans = 0;
        ULL x;
        for(int i=0; i<n; i++)
        {
            cin>>x;
            int sum = 0;
            while(x)
            {
                if(x & 1)
                    sum++;
                x>>=1;
            }
            ans ^= sg[sum];
        }
        if(!ans)
            puts("L");
        else
            puts("B");
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!