51nod 1714 B君的游戏(Nim博弈,SG函数打表)

1.0 秒 131,072.0 KB 40 分 4级题

B君和L君要玩一个游戏。刚开始有n个正整数 𝑎𝑖 。

双方轮流操作。每次操作,选一个正整数x,将其移除,再添加7个数字 𝑥1,𝑥2…𝑥7 。要求对于 𝑥𝑖 ,满足 0<=𝑥𝑖<𝑥 且 𝑥&𝑥𝑖=𝑥𝑖

注意0不能被选取,所以这个游戏一定会结束,而谁无法操作谁就失败。
B君根据自己的经验,认为先手胜率高一点,所以B君是先手。
B君想知道自己是否必胜。


不会写,,唉,sg值算不来

n个正整数,要满足0<=𝑥𝑖<𝑥且𝑥&𝑥𝑖=𝑥𝑖,那这个问题只和x的二进制的1的个数num有关,设sg[num]表示有num个1的时候的sg函数值,可以看成一个nim博弈,一个数就是一堆石子,这个数的二进制的1的个数就是石子数,把所有子问题的sg函数值异或求解

一开始是必败态0,共可以操作7次,枚举第7-deep次的数剩i个1的情况


这是一种思路,然后还看了神仙的另一种思路,还没参透那个结论咋来的ORZ先记录下来mark

b[i]表示有i个1的数字的个数,当所有的b[i]都为偶数的时候,先手必败,先手一次最多可以把8个奇数改为8个偶数,所以当且仅当先手面对的局面有九个或者9的倍数个奇数,那么后手一直跟他博弈剩9的倍数的奇数,先手就输了

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<vector>
using namespace std;

#define LL long long
// const int N=7e7;
int sg[65]={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 vis[N];
// void dfs(int numr,int deep,int res,int numl){
// if(deep==0){
// vis[res]=1;
// return;
// }
// for(int i=numl;i<numr;i++){
// dfs(numr,deep-1,res^sg[i],i);
// }
// }
// void get(){
// sg[0]=0;
// int tmp=0;
// for(int i=1;i<=64;i++){
// memset(vis,0,tmp);
// dfs(i,7,0,0);
// for(int j=0;j<N;j++){
// if(!vis[j]){
// sg[i]=j;
// break;
// }
// }
// printf("%d,",sg[i]);
// }
// }
int main(){
// get();
int n,ans=0;
LL c;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&c);
int num=0;
while(c){
num+=(c%2);
c/=2;
}
ans^=sg[num];
}
if(ans)puts("B");
else puts("L");
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信