Codeforces 814C An impassioned circulation of affection

题目链接:http://codeforces.com/problemset/problem/814/C

题意:给一个全是小写字母的字符串,q个询问,最多改变m个字母,问改变后字母c的最大连续长度。

思路:两种方法可做。第一种是用尺取法,不断将非字母c的位置改变成字母c,用ans来更新区间长度即可。第二种方法是用预处理,会比尺取法快很多,以下摘自官方题解:

The first thing to notice is that we are only changing other colours to Koyomi's favourite one. Furthermore, we won't create disconnected segments of that colour, for that's no better than painting just around the longest among them.

This leads us to a straightforward approach: when faced with a query (m, c), we check each segment [l, r] and determine whether it's possible to fill this segment with letter c, within at most m replacements. This can be done by finding the number of times c occurs in that segment (denote it by tc), and checking whether (r - l + 1) - t ≤ m. But this O(n2·q) solution would be too slow.

Since the number of different queries is 26n, we can calculate all answers beforehand. For each letter c and a segment [l, r], we'll be able to fill the whole segment with c within (r - l + 1) - tc moves. Use this information to update the answers, and employing a "prefix max" method gives us a time complexity of O(n2·|Σ| + q), where |Σ| equals 26. Refer to the code for a possible implementation.

Bonus. Find out the O(n2  +  n·|Σ|  +  q) solutions and the O(nq) solutions (some of them may get TLE — remember to check against maximum data next time!).

尺取法代码:

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,q;
char s[1500+5];
int cal(int k,const char *f);
int main(){
    read(n);
    scanf("%s",s);
    for (read(q);q;q--){
        int k;
        char f[2];
        scanf("%d%s",&k,f);
        printf("%d\n",cal(k,f));
    }
    return 0;
}

int cal(int k,const char *f){
    int l,r;
    l=r=0;
    int ans=0,cnt=0;
    while (l<n || r<n){
        while (r<n && ((cnt<k) || (s[r]==f[0]))){
            if (s[r]!=f[0]) cnt++;
            r++;
        }
        ans=max(ans,r-l);
        if (s[l]!=f[0]){
            cnt--;
        }
        l++;
    }
    return ans;
}

预处理代码:

#include <bits/stdc++.h>
using namespace std;
template
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,q;
char s[1500+5];
int ans[26][1500+5];
int main(){
    read(n);
    scanf("%s",s);
    for (int alp=0;alp<26;alp++){
        for (int i=0;i<n;i++){
            int cnt=0;
            for (int j=i;j<n;j++){
                if ((s[j]-'a')!=alp) cnt++;
                ans[alp][cnt]=max(ans[alp][cnt],j-i+1);
            }
        }
        for (int i=1;i<=n;i++){//因为题目要求改变字母数可以小于m,所以可以以此来更新ans[alp][i]的最大值
            ans[alp][i]=max(ans[alp][i],ans[alp][i-1]);
        }
    }
    for (read(q);q;q--){
        int k;
        char f[2];
        scanf("%d%s",&k,f);
        printf("%d\n",ans[f[0]-'a'][k]);
    }
    return 0;
}

发表评论

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