CF1037G A Game on Strings Sol

有趣题。

首先"分成若干个互不相干的子串"是子游戏的定义，可以用 SG 函数处理。

然而接下来试着打了半个多小时的表，没有找到任何规律。

但是发现 SG 函数的状态转移是很简单的。一般 SG 函数难以优化的点在于 \(\text{MEX}\) 操作不太平易近人，这道题中让你取 \(\text{MEX}\) 的只有 26 个数完全可以暴力去做。

进一步地，我们想到这道题中能够成为”子游戏“的子区间是很有限的，对于删去某个字符形成的若干段字符串，只有这些串的前缀后缀是需要计算 SG 函数的。

所以我们只需要按照这些串的长度从小到大计算 SG 值即可。

TLE submission

然而事情并不是那么美好，如果没注意好实现细节直接拿 std::map 维护 SG 值会多 \(\log\)，复杂度达到了 \(O(n|\Sigma|^2\log n)\)。

于是重构了一遍代码，考虑按右端点和串长度双关键字的顺序计算这些区间，并且用合适的数组替换掉数据结构，复杂度 \(O(n|\Sigma|^2)\)。

这道题实现还是很有技巧的，应该要有 implementation 的标签。

#include <bits/stdc++.h>

using namespace std;

const int N=100003;

char s[N];

int n,q;

int a[N][26],fa[N][26];

int b[N][26],fb[N][26];

int f[N],cur[26];

int calc(int l,int r){

	if(l>r) return 0;

	unsigned int st=0;

	for(int c=0;c<26;++c){

		int pl=a[l][c],pr=b[r][c];

		if(pl<=pr) st|=1u<<(f[pl]^f[pr]^fa[l][c]^fb[r][c]);

	}

	return __builtin_ctz(~st);

}

int stk[26];

int main(){

	scanf("%s",s+1);

	n=strlen(s+1);

	for(int c=0;c<26;++c) a[n+1][c]=n+1;

	for(int i=n;i;--i){

		memcpy(a[i],a[i+1],104);

		a[i][s[i]-97]=i;

	}

	for(int c=0;c<26;++c) b[0][c]=0;

	for(int i=1;i<=n;++i){

		memcpy(b[i],b[i-1],104);

		b[i][s[i]-97]=i;

	}

	for(int c=0;c<26;++c) stk[c]=c;

	for(int i=1;i<=n;++i){

		int c=s[i]-97;

		f[i]=f[cur[c]]^fb[i-1][c];cur[c]=i;

		sort(stk,stk+26,[&](int x,int y){return b[i][x]>b[i][y];});

		for(int t=0;t<26;++t){

			int o=stk[t];

			if(b[i][o]<i) fb[i][o]=calc(b[i][o]+1,i);

		}

		if(i<n){

			int cc=s[i+1]-97;

			for(int j=i;j>cur[cc];--j) fa[j][cc]=calc(j,i);

		}

	}

	scanf("%d",&q);

	while(q--){

		int l,r;

		scanf("%d%d",&l,&r);

		if(calc(l,r)) puts("Alice");

		else puts("Bob");

	}

	return 0;

}

CF1037G A Game on Strings Sol的相关教程结束。