#C240802B. 石头

网址（Website）

题目详情 - 石头 - Super

题解 - 石头 - Super

题解（Solution）

$\qquad$拿掉连续 $k$ 个石头，相当于留下 $n - k$ 个石头。因为 $n$ 个石头组成的是 11 个环，所以考虑把输入的字符串倍长。则问题转化为是否存在长度为 $j (j = n - k)$ 的字符串使得相邻两个石头颜色不同，并且第一个和最后一个石头颜色也不同。

$\qquad$首先，相邻两个石头颜色相同肯定不可能被留下来。所以如果相邻两个石头颜色相同，在他们之间画一条分割线。然后把所有相邻两条分割线之间的子串取出来，对于每个 $j\ (1 ≤ j ≤ len)$，判断是否存在长度为 $j$ 的合法方案。

$\qquad$对于每个取出的子串，记它的长度为 $len$，对该子串跑一次 $kmp$ ，令 $j = nxt[j]$，则这个子串内一定不存在留下长度为 $len - j + 1$ 的子串的方案，接着令 $j = nxt[j]$，继续重复上述做法，直到 $j = 0$ 结束。

$\qquad$我直到现在都没有想出来最后是怎么联系到 $\mathrm{kmp}$ 算法的。。。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define fi first
#define se second
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;

int n,ans[N];
char s[N];

int p[N];
void Solve(int l,int r){
	int len = r-l+1;
	int i,j;p[1] = 0;
	for(i=1,j=0;i+l<=r;i++){
		while(j && s[i+l]!=s[j+l]) j = p[j];
		if(s[i+l]==s[j+l]) j++;
		p[i+1] = j;
	}
	
	For(j,1,len) ans[j]++;//假设原先所有子串都可以
	while(j>0){
		ans[len-j+1] --;
		j = p[j];
	}
}

signed main(){
	freopen("stone.in","r",stdin),freopen("stone.out","w",stdout);
	int Tim = clock(), T = 0;
	while(scanf("%s",s+1)!=EOF){
		n = strlen(s+1), T++;
		For(i,1,n) s[i+n] = s[i];//倍长
		For(i,1,n) ans[i] = 0;
		s[2*n+1]=0;
		
		int lst=1;
		For(i,2,n*2) if(s[i]==s[i-1]){
			Solve(lst,i-1);
			lst = i;
		}Solve(lst,2*n);//最后一部分也要搜索
		
		printf("Case %lld:",T);
		For(i,0,n-1)	
			printf("%lld",(int)(ans[n-i]>0));
		printf("\n");
	}
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}