current position:Home>F. Colouring Game (game theory/sg function)

F. Colouring Game (game theory/sg function)

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

题目
参考

题意

给定一个RB字符串序列.
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.
我们用WIndicates dyed、白色的点.

对于R数量大于Bnumber of scenes,Alice必赢.假如Bobto dyeRB,BR这两种状态的,则Alicealso to dye this state;假如Bobto dyeWB,BW这两种状态的,则AliceAlso to dyeRW,WR这两种状态的.一直耗下去,最终由于R比BAt least one more quantity,Bob无路可走.

对于R数量小于Bnumber of scenes,我们也可以做类似分析,此时Bob必胜.

对于R和BA consistent number of scenes,我们可以应用SG函数.
We divide the original string into several pieces、Substrings with different adjacent characters.
比如字符串RBRRBBBR,我们可以划分为RBR,RB,B,BRthese substrings.
则答案即为 S G ( R B R ) ⊕ S G ( R B ) ⊕ S G ( B ) ⊕ S G ( B R ) SG(RBR)\oplus SG(RB)\oplus SG(B)\oplus SG(BR) SG(RBR)SG(RB)SG(B)SG(BR)

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,关注下,一起快乐刷题吧~

copyright notice
author[Luo gkv],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/218/202208060918144432.html