51 NODアルゴリズムマラソン15(EU離脱専用場)B君のゲーム(ゲーム)
5837 ワード
トランスファゲート
B君のゲームwwwwodddd(命題者)基準時間制限:1秒空間制限:131072 KBスコア:40 B君とL君はゲームをします.最初はn個の正の整数aiがありました.
双方が交代で操作する.操作のたびに、正の整数xを選択して削除し、7つの数値x 1,x 2...x 7を追加します.要求はxiに対して0<=xi注意0は選択できないので、このゲームは必ず終わり、誰が操作できないかは失敗します.B君は自分の経験から、先手の勝率が高いと思っているので、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
解題構想(公式問題解):これは簡単なSGゲームの問題である.
各数のSG値は,その中にどれだけの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:
B君のゲームwwwwodddd(命題者)基準時間制限:1秒空間制限:131072 KBスコア:40 B君とL君はゲームをします.最初はn個の正の整数aiがありました.
双方が交代で操作する.操作のたびに、正の整数xを選択して削除し、7つの数値x 1,x 2...x 7を追加します.要求はxiに対して0<=xi
解題構想(公式問題解):これは簡単なSGゲームの問題である.
各数のSG値は,その中にどれだけの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;
}