文章目录
  1. 1. 原题重现
    1. 1.1. Description
    2. 1.2. Input
    3. 1.3. Output
    4. 1.4. Sample Input
    5. 1.5. Sample Output
  2. 2. 解题思路
  3. 3. 打表器代码
  4. 4. AC代码

引言:问题越积越多,感觉自己药丸。


原题重现

Description

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"。

Sample Input

4
1
2
3
4

Sample Output

B

解题思路

  • 题中新添的数要求是比之前的数小,并且与原数位与后不变。举个例子来讲把,就比如说11,它的二进制是1011,因此它可以转化为1010,1001,1000,0011,0010,0001,0000,其实就是2312^3-1种,减的1就是1011,它自己不可取。也就是说其实状态跟这个数是多少无关,只跟这个数的二进制中1的个数有关。根据例子就是说把二进制1的个数为3的数11转化为二进制1的个数为2或1或0的数,新转换的数和原数适用于同一个游戏规则。

  • 根据题意,这很像上次的Cutting Game。根据上面的逻辑推理,这个又是一个把一个父游戏转化为若干个子游戏的题目,所以它是SG博弈。

  • 我们回顾一下上次SG博弈笔记中所记:


    • SG博弈中,父游戏可以转若干个子游戏,并且有几种转化子游戏的方式,每种转化方式都对应一个Grundy值,记为G1,G2,...,GnG_1,G_2,...,G_n,其中任意某个Grundy值的求法是将该种转化方式下的子游戏的Grundy值异或。最终父游戏的Grundy值为mex{G1,G2,...,Gn}mex \lbrace G_1,G_2,...,G_n \rbrace

    • mexmex是指集合中无法取到的最小的自然数(包括0在内),如mex{0,1,3,5}=2mex \lbrace 0,1,3,5 \rbrace = 2


  • 我们把避免我下棋的局面找到,很明显是所有数都为0的局面。这和我们上次SG笔记中所讲有点矛盾了,因为所有数为0的局面是很明显的局面。实际上上次SG笔记所写的方法是最保险的选G值为0的方法,但在本题似乎有些困难。本题之所以可以选择这种题目告诉你的胜利局面为G值为0的局面是因为,你必须把所有数都拆成0,而不是单单把某个数拆成0就结束了。Cutting Game因为拆一个1x1就结束,因此将(1,1)作为游戏的基础点是不可靠的,不能通过(1,1)推到整个游戏结果, 基础不稳地动山摇 嘛。我们这个的游戏就很稳了。

  • 本题一个父游戏有很多很多种拆成子游戏的方法,就比如说之前讲的11吧,它可以拆成7个1010,或者6个1010,1个1001,或者1个1000,2个0011,3个0001,1个0000……所有这些情况都是它的子游戏的拆法。因为之前讨论过了,状态只和二进制中1的个数有关。意思是Grundy(11)和Grundy(7),Grundy(28672)是一样的,那么我们不这么表示,我们把前面的都记为Grundy(3),意为二进制中1的个数为3的数的Grundy值。我们算Grundy(3)就要算出mex{一个情况的子游戏间的异或得到一个G值,所有G值构成此集合},求这个集合的mex就是Grundy(3)。

  • 一共64种Grundy值,而且算的极其慢,是不可能交上去慢慢算的,所以必须打表。就算是打表我这个辣鸡AMD笔记本也跑了400多秒,用set数据小的时候跑的比数组快,但数据大的时候就很慢很慢了,推荐用数组。数组是稳稳O(n)O(n)的,vector+sort+binary_searchvector+sort+binary\_searchO(nlog2n)O(nlog_2^n)的。

  • 另外……我试了一下vector结果……
    悲剧啊!!

打表器代码

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
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define MOD (ll)(1e9+7)
int sg[65];
int vis[100000000];
//vector<int> vec;
void dfs(int maxn,int step,int now,int ans)
{
if(step==7)
{
vis[ans]=1;
//vec.push_back(ans);
return ;
}
for(int i=now;i<maxn;i++)
dfs(maxn,step+1,i,ans^sg[i]);

}
void init()
{
sg[0]=0;
for(int i=1;i<=64; i++)
{
memset(vis,0,sizeof(vis));
//vec.clear();
dfs(i, 0, 0, 0);
for(int j=0;;j++)
if(!vis[j])
{
sg[i]=j;
break;
}
/*sort(vec.begin(),vec.end());
for(int j=0;;j++)
if(!binary_search(vec.begin(),vec.end(),j))
{
sg[i]=j;
break;
}*/
printf("%d\n", sg[i]);
}
}
int main()
{
init();
puts("over");
}

AC代码

打表万岁!!!
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#include<set>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define MOD (ll)(1e9+7)

inline int read()
{
int a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
inline ll read2()
{
ll a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
ll dp[100];
ll 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
};
ll c(ll n)
{
ll cnt=0;
while(n)
{
n&=n-1;
cnt++;
}
return cnt;
}
int main(void)
{
ll n=read2(),r=0;
while(n--)
{
r^=sg[c(read2())];
}
if(r)puts("B");
else puts("L");
return 0;
}
文章目录
  1. 1. 原题重现
    1. 1.1. Description
    2. 1.2. Input
    3. 1.3. Output
    4. 1.4. Sample Input
    5. 1.5. Sample Output
  2. 2. 解题思路
  3. 3. 打表器代码
  4. 4. AC代码