首先看R和B的数量不等的情况(很多博弈题都是先比较两种物品的数量，相等的情况再用SG函数之类的技巧)，结论是R多Alice必赢，B多Bob必赢。证明：来看R比B多的情况，定义两人的"差距"为当前R的数量减B的数量。发现Alice操作只可能让差距不变或变小，Bob操作只可能让差距不变或变大。定义"一轮游戏"为Alice先操作一次，Bob再操作一次的过程。如果一轮开始前还有"RB"或"BR"，那么Alice就随便找一个RB或BR涂了，这一轮差距就肯定不会变小，Alice仍然保持领先；如果没有RB或BR，就看有没有RW或WR，如果有就随便找一个涂了，由于此时没有RB、BR所以Bob也只能涂BW和WB，因此差距仍然不会减小；只有RR的情况是不存在的，除非整个序列全是R，但是这种情况Alice本来就会赢。对于B比R多的情况也是类似(Alice第一次操作后B显然还比R多，所以就变成和上面一样的情况了)。
R和B相等的情况，两人都只能涂RB或BR，否则会导致R和B不相等，根据上面的结论操作这步的人就输了。所以问题变成：两个人每次可以挑相邻的两个RB或BR涂白，不能操作的人输。把序列分成若干段，每段都是极长的RBRBRB交错的区间。被涂的位置肯定是被完全包含在某个段内部，不可能横跨两个段的，因为这样不可能是RB或BR。发现每一段的内部都构成了一个公平的有向图游戏，可以对每一段求SG函数再异或起来得到答案。一个长为i的段的SG函数为：\(sg_i=mex_{l+r=i-1}(sg_l\bigoplus sg_r)\)，其中\(\bigoplus\)表示异或。这玩意儿看上去像卷积，但其实不太能用多项式技巧求。正确的求法居然是：sg值除了前几项，后面的均以34为循环节，所以暴力求出前若干项(比如1000)就行了。真的是很无聊(不知道这题怎么过cf审核的)，但是也要了解一下，防止以后再出现这种题。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
int sg[500010];
int dfs(int pos)
{
if(sg[pos]>-1) return sg[pos];
if(pos<2) return sg[pos]=0;
map <int,int> mp;
rep(i,pos-1)
{
int l=i,r=pos-l-2;
int val=dfs(l)^dfs(r);
mp[val]=1;
}
rep(i,1000) if(mp.find(i)==mp.end()) return sg[pos]=i;
}
int t,n;
string s;
char c[500010];
int main()
{
fileio();
rep(i,1005) sg[i]=-1;
dfs(1000);
for(int i=1001;i<=500005;++i) sg[i]=sg[i-34];
cin>>t;
rep(tn,t)
{
scanf("%d%s",&n,c);s=c;
int cr=0,cb=0;
rep(i,n) if(s[i]=='R') ++cr;else ++cb;
if(cr>cb) puts("Alice");
else if(cb>cr) puts("Bob");
else
{
int ans=0;
rep(i,n)
{
int p=i;
while(p+1<n&&s[p+1]!=s[p]) ++p;
ans^=sg[p-i+1];i=p;
}
puts(ans ? "Alice":"Bob");
}
}
termin();
}