F. Colouring Game（博弈论/sg函数）

题目
参考

题意

给定一个RB字符串序列。
Alice和Bob轮流操作，
Alice可以选择两个相邻的、至少有一个R字符的字符子串，并把它们染成白色；
Bob可以选择两个相邻的、至少有一个B字符的字符子串，并把它们染成白色。

最终哪方无路可走，则输了。
Alice和Bob都按最优思路去走。问最终谁是赢家。

思路

经典的博弈题，sg函数不太熟，感兴趣可以看看这篇介绍
sg函数介绍

直接套着公式就可以求解这道题了。
我们用W表示被染过的、白色的点。

对于R数量大于B数量的场景，Alice必赢。假如Bob去染RB，BR这两种状态的，则Alice也去染这种状态的；假如Bob去染WB，BW这两种状态的，则Alice也去染RW，WR这两种状态的。一直耗下去，最终由于R比B多出至少一个数量，Bob无路可走。

对于R数量小于B数量的场景，我们也可以做类似分析，此时Bob必胜。

对于R和B数量一致的场景，我们可以应用SG函数。
我们把原字符串划分为若干个、相邻字符不同的子字符串。
比如字符串RBRRBBBR，我们可以划分为RBR,RB,B,BR这几个子字符串。
则答案即为$SG(RBR)\oplus SG(RB)\oplus SG(B)\oplus SG(BR)$

至于不同长度的、相邻字符不同的字符串，它们的SG怎么求，就可以套SG公式了

sg(i)=mex(sg(i)^sg(i-j-2)),0<=j<=i-2
1

代码

#include
using namespace std;
const int maxn = 500010;
//const int N=500005;
int n;
int sg[maxn], vis[maxn];
char s[maxn];
int f[maxn];
void init() {
	// sg函数初始化 
	for (int i = 1; i <= 100; ++i) {
		// sg[i] = mex(sg[j] ^ sg[i-j-2]) 
		for (int j = 0; j <= i - 2; ++j) {
			vis[sg[j]^sg[i-j-2]] = 1;
		}
		int j = 0;
		while (vis[j]) ++j;
		sg[i] = j;
		for (int j = 0; j <= i; ++j) {
			vis[j] = 0;
		}
	}
	/*
	for (int i = 1; i <= 500; ++i) {
		printf("%d ", sg[i]);
		if (i % 17 == 0) {
			printf("\n");
		}
	}*/
	// 打表可以发现 循环节是34 
	for (int i = 101; i < maxn; ++i) {
		sg[i] = sg[i-34];
	}
	
}

void solve() {
	scanf("%d", &n);
	scanf("%s", s);
	int res = 0;
	for (int i = 0; i < n; ++i) {
		char c = s[i];
		if (c == 'R') {
			++res;
		} else {
			--res;
		}
	}
	if (res != 0) {
		printf("%s\n", res > 0 ? "Alice" : "Bob");
		return;
	}
	
	int ans = 0;
	for (int i = 1, j; i <= n;) {
		j = i + 1;
		while (j <= n && s[j-1] != s[j-2]) {
			++j;
		}
		ans ^= sg[j-i];
		i = j;
	}
	printf("%s\n", ans ? "Alice" : "Bob");
}

int main() {
	init();
	int t; 
    scanf("%d", &t);
    while (t--) {
    	solve();
    }
}
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

最后

weixin gongzhonghao搜 对方正在debug，关注下，一起快乐刷题吧~