题目链接

题目大意

给定一个由abc三种字符组成的长度为n的字符串,进行m次询问。

每次询问给定一个区间[l,r],对于该区间及其区间内的所有子串,若使这些字符串均不成为回文串,求至少需要修改几处。

解题思路

首先若区间长度为1,无需修改;

若区间长度为2,只需两者不同即可;

若区间长度为3,显然也不能有两者相同(aababa都是不符合题目要求的),所以有6种可能(abc,acb,bac,bca,cab,cbaabc的六种全排列)

若区间长度为4,例如为abc串添加一个后缀,发现只能添加aabcbabcc均不符合要求)。同理,所有上述的六种串均只能添加其首字母。

归纳总结:对于查询的串而言必须是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 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注