题目大意
给定一个由a
、b
、c
三种字符组成的长度为n的字符串,进行m次询问。
每次询问给定一个区间[l,r],对于该区间及其区间内的所有子串,若使这些字符串均不成为回文串,求至少需要修改几处。
解题思路
首先若区间长度为1,无需修改;
若区间长度为2,只需两者不同即可;
若区间长度为3,显然也不能有两者相同(aab
和aba
都是不符合题目要求的),所以有6种可能(abc
,acb
,bac
,bca
,cab
,cba
即abc
的六种全排列)
若区间长度为4,例如为abc
串添加一个后缀,发现只能添加a
(abcb
、abcc
均不符合要求)。同理,所有上述的六种串均只能添加其首字母。
归纳总结:对于查询的串而言必须是abcabcabc...
/bcabca...
/cabcab...
/acbacb...
/cbacba...
/bacbac...
六种中的一种
因此可以在查询前对整个串进行预处理,将六种模式串和原串进行对比。记录需要修改的位置的数量(前缀和)。之后进行查询。
代码实现
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5+7;
const int eps = 1e-8;
const int inf = 0x7f7f7f7f;
const int mod = 1e9+7;
int T;
int n,m,k;
char s[N],t[N];//原串和模式串
int sum1[N],sum2[N],sum3[N],sum4[N],sum5[N],sum6[N];
void make_chars(char x,char y,char z){//定义模式串
for(int i=1;i<=n;i++){
t[i] = i%3==1 ? x:(i%3==2 ? y : z);
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m;
cin>>s+1;
make_chars('a','b','c');
for(int i=1;i<=n;i++) sum1[i] = s[i]==t[i]? sum1[i-1] : sum1[i-1]+1;
make_chars('a','c','b');
for(int i=1;i<=n;i++) sum2[i] = s[i]==t[i]? sum2[i-1] : sum2[i-1]+1;
make_chars('b','a','c');
for(int i=1;i<=n;i++) sum3[i] = s[i]==t[i]? sum3[i-1] : sum3[i-1]+1;
make_chars('b','c','a');
for(int i=1;i<=n;i++) sum4[i] = s[i]==t[i]? sum4[i-1] : sum4[i-1]+1;
make_chars('c','a','b');
for(int i=1;i<=n;i++) sum5[i] = s[i]==t[i]? sum5[i-1] : sum5[i-1]+1;
make_chars('c','b','a');
for(int i=1;i<=n;i++) sum6[i] = s[i]==t[i]? sum6[i-1] : sum6[i-1]+1;
int l,r;
while(m--){
cin>>l>>r;
cout<<min({sum1[r]-sum1[l-1],sum2[r]-sum2[l-1],sum3[r]-sum3[l-1],sum4[r]-sum4[l-1],sum5[r]-sum5[l-1],sum6[r]-sum6[l-1]})<<endl;
}
return 0;
}
0 条评论