51Nod 1714 B君的游戏 - dblank

51Nod 1714 B君的游戏

1714 B君的游戏
基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 收藏 关注
B君和L君要玩一个游戏。刚开始有n个正整数 ai 。

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

注意0不能被选取,所以这个游戏一定会结束,而谁无法操作谁就失败。
B君根据自己的经验,认为先手胜率高一点,所以B君是先手。
B君想知道自己是否必胜。
Input
第一行一个整数n (1 <= n <= 100000)
以下n行n个数ai (0 <= a_i < 2^64)
Output
如果先手必胜,输出"B",否则输出"L"。
Input示例
4
1
2
3
4
Output示例
B
对于一个数字,我们可以暴力打出它的sg值,这个游戏和数本身没有太大关系,有关系的是这个数含有1的个数,另外把一个x变成7个xi其实也可以变成7个子游戏,总的就是这七个的sg异或和,离线打出这个表,然后n个数直接异或和就好了。
打表代码:

include<iostream>

include<cstdio>

include<algorithm>

include<map>

include<cstring>

include<map>

include<set>

include<queue>

include<stack>

include<cmath>

pragma comment(linker, "/STACK:102400000,102400000")

define endl 'n'

define debug puts("yes")

include<bits/stdc++.h>

typedef unsigned long long ll;
using namespace std;
const int N = 6400000 + 10, Mod = 1000000007;
int sg[100], maxs;
bool vis[N];
void dfs(int up, int m, int ans, int last)
{

if(m == 0)
{
    vis[ans] = true;
    return ;
}
for(int i = last; i<up; i++)
{
    dfs(up, m-1, ans ^ sg[i], i);
}

}
int main()
{

//freopen("D:\\out.txt", "W", stdout);
int n;
int cnt[100];
for(int i = 0; i<=63; i++)
{
    memset(vis, 0, sizeof(vis));
    dfs(i, 7, 0, 0);
    for(int j = 0; j<N; j++)
    {
        if(vis[j] == false){
            sg[i] = j;
            break;
        }
    }
    printf("%d,", sg[i]);
}
return 0;

}

AC代码:

include<iostream>

include<cstdio>

include<algorithm>

include<map>

include<cstring>

include<map>

include<set>

include<queue>

include<stack>

include<cmath>

pragma comment(linker, "/STACK:102400000,102400000")

define endl 'n'

define debug puts("yes")

include<bits/stdc++.h>

typedef unsigned long long ll;
using namespace std;
const int N = 1000000 + 10, Mod = 1000000007;
int sg[100], maxs;
ll a[N];

int main()
{
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};

int n;
scanf("%d", &n);
ll ans = 0;
for(int i = 0; i<n; i++){
    scanf("%llu", &a[i]);
    int num = 0;
    for(int j = 0; j<64; j++)
    {
        if(a[i]  & (1LL<<j))
            num++;
    }
    ans ^= sg[num];
}
if(ans == 0)
    printf("L\n");
else printf("B\n");
return 0;

}

发表新评论