题意
有一个首尾相连的环 , 元素依次是 \(a_1 \cdots a_n\) .
对于每个 \(0\le k< n\) , 回答是否存在删除 \(k\) 个相邻元素的方案 , 使得删除后的环相邻元素不相等 ( 包括首尾元素 ) .
\(n\le 10^6\) .
题解
必要地简化一下问题 , 先把原串复制一遍接在后面表示环 , 删除 \(k\) 个相当于在新的串上保留一个 \(n-k\) 的区间 . 因此只考虑是否能找出长为 \(k\) 的子区间使相邻元素不相等 .
先考虑除了首尾之外不相等 , 发现原来串上相邻相等的位置不可能出现在同一个区间里 , 在这样的位置分段 , 可以把原串分成若干段 , 保证在这些段内取除首尾之外相等 .
然后只需保证首尾的元素不相等 , 发现对于长度 \(k\) , 所有长度 \(k\) 的首尾都相等 , 相当于长度为 \(len-k+1\) 的前后缀相等 , 于是转化成 $\mathrm{KMP} $ 问题 .
点击查看代码
#include<bits/stdc++.h>
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define ll long long
#define INF 0x7fffffff
#define INF64 1e18
using namespace std;
constexpr int N=2e6+5;
int n,f[N];
string s;
int res[N];
void check(int l,int r){
f[1]=0;
int j=0;
for(int i=2;i<=r-l+1;i++){
while(j&&s[l-1+j]!=s[l+i-2]) j=f[j];
if(s[l-1+j]==s[l+i-2]) j++;
f[i]=j;
}
for(int i=1;i<=r-l+1;i++) res[i]++;
while(j) res[r-l+1-j+1]--,j=f[j];
}
int cnt;
void solve(){
memset(res,0,sizeof res);
n=s.length();
s=s+s;
int last=1;
for(int i=1;i<2*n;i++){
if(s[i]==s[i-1]){
check(last,i);
last=i+1;
}
}
check(last,2*n);
cout<<"Case "<<cnt<<": ";
for(int i=0;i<n;i++)
if(res[n-i]) cout<<1;
else cout<<0;
cout<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
while(cin>>s){ cnt++;solve();}
}
总结
- 进行一切能简化问题的转化 , 以给后面看出真正的做法做铺垫 .
- 先考虑简单的不包含首尾的部分 , 然后只研究首尾相等 , 得出正确的方法 .