# F. Colouring Game (game theory/sg function)

2022-08-06 09:23:58Luo gkv

## 题意

Alice和Bob轮流操作,
AliceTwo adjacent ones can be selected、至少有一个RA substring of characters,and dye them white;
BobTwo adjacent ones can be selected、至少有一个BA substring of characters,and dye them white.

In the end there is no way out,则输了.
Alice和BobGo with the best idea.Ask who is the winner in the end.

## 思路

Classic game problem,sgThe function is not familiar,If you are interested, you can read this introduction
sg函数介绍

This problem can be solved directly by applying the formula.

We divide the original string into several pieces、Substrings with different adjacent characters.

As for different lengths、Strings with different adjacent characters,它们的SG怎么求,can be setSG公式了

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


## 代码

#include<bits/stdc++.h>
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();
}
}


## 最后

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