首页 > 代码库 > Codeforces Round #418 C

Codeforces Round #418 C

C An impassioned circulation of affection

题意:给一个长度为n的字符串,q个询问,询问若将任意m个字符替换成任意字符,可以得到的最长的连续的c是多少

思路:询问20w,字符串长度1500,其实只有1500*26个询问是有效的,其他询问都是重复的,所以预处理出每个字符1-n的答案,询问时直接输出就可以了,预处理用尺取法,用t表示当前答案,u表示当前还可以替换几个字符,每次往前尺取,若当前字符为c则t++,否则若u>0 则 t++ 且 u--(使用了一次替换操作),若u<=0,则需要将最前头的字符丢弃,若最前头的字符为c,则继续丢弃,直到不为c,这一步的目的是继续往后尺取,因为u==0,不能进行替换操作,且当前字符又不为c,所以只有丢弃一个使用了替换操作的字符才能继续尺取,每次尺取后更新答案

AC代码:

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int N=1e5+100;
int n,q,m,ans[30][1505];
char s[1505],c;
int main(){
    //memset(s,-1,sizeof(s));
    cin>>n>>s>>q;
    int l=strlen(s);
    for(int k=0; k<26; ++k){
        for(int j=1; j<=n; ++j){
            int u=j,t=0;
            for(int i=0; i<l; ++i){
                if(s[i]-a==k){
                    t++;
                }
                else{
                    if(u>0){
                        u--;t++;
                    }
                    else{
                        if(s[i-t]-a==k){
                            t--,i--;
                        }
                    }
                }
                ans[k][j]=max(ans[k][j],t);
            }
        }
    }

    while(q--){
        cin>>m>>c;
        int k=c-a;
        cout<<ans[k][m]<<endl;
    }
    return 0;
}
/*
6
koyomi
3
1 o
4 o
4 m
15
yamatonadeshiko
10
1 a
2 a
3 a
4 a
5 a
1 b
2 b
3 b
4 b
5 b
10
aaaaaaaaaa
2
10 b
10 z
*/

 

Codeforces Round #418 C