傳送門
B君的游戲
wwwwodddd (命題人)
基準(zhǔn)時(shí)間限制：1 秒 空間限制：131072 KB 分值: 40
B君和L君要玩1個(gè)游戲。剛開始有n個(gè)正整數(shù) ai 。
雙方輪番操作。每次操作，選1個(gè)正整數(shù)x，將其移除，再添加7個(gè)數(shù)字 x1,x2…x7 。要求對(duì) xi ，滿足 0<= xi < x 且 x&xi=xi
注意0不能被選取，所以這個(gè)游戲1定會(huì)結(jié)束，而誰沒法操作誰就失敗。
B君根據(jù)自己的經(jīng)驗(yàn)，認(rèn)為先手勝率高1點(diǎn)，所以B君是先手。
B君想知道自己是不是必勝。
Input
第1行1個(gè)整數(shù)n (1 <= n <= 100000)
以下n行n個(gè)數(shù)ai (0 <= a_i < 2^64)
Output
如果先手必勝，輸出”B”，否則輸出”L”。
Input示例
4
1
2
3
4
Output示例
B
解題思路（官方題解）：
這是1個(gè)簡(jiǎn)單的SG博弈問題。
注意到每一個(gè)數(shù)的SG值，只和其中有多少個(gè)1有關(guān)。
所以我們寫1個(gè)不太暴力的暴力。可以得到。
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]是數(shù)x包括i個(gè)1的時(shí)候的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;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
