upc-魔法石01字符串ab字符串变换问题——尺取

魔法石

题目描述

你习得了魔法，并学会了熟练运用魔法石。

你得到了n颗魔法石，魔法石有两种属性，分别为火属性和水属性。你一开始得到的是这n颗魔法石的一个排列。定义这n颗魔法石释放出来的能量，为最长的属性相同的魔法石连续段的长度。

作为一名熟练的魔法师，你还可以至多修改k个魔法石的属性。你现在想知道这n颗魔法石最多可以释放出多少能量。

输入

第一行为两个正整数n,k，表示魔法石的个数和最多可以修改的魔法石数量。

接下来一行为一个长度为n的 字符串 ,第i个字符表示第i颗魔法石的属性，a为火属性，b为水属性。

输出

输出为一行一个正整数，表示这n颗魔法石最多可以释放出的能量大小。

样例输入

【样例1】

4 2
abba

【样例2】

8 1
aabaabaa

样例输出

【样例1】

4

【样例2】

5

提示

对于30%的数据，满足n≤20。

对于60%的数据，满足n≤1000。

对于另外20%的数据，满足所有魔法石属性均相同。

对于100%的数据，满足1≤k≤n≤105。

牛客的这个题：

题目描述

nozomi看到eli在字符串的“花园”里迷路了，决定也去研究字符串问题。

她想到了这样一个问题：

对于一个 “01”串而言，每次操作可以把 0 字符改为 1 字符，或者把 1 字符改为0 字符。所谓“01”串，即只含字符 0 和字符 1 的字符串。

nozomi有最多 次操作的机会。她想在操作之后找出一个尽可能长的连续子串，这个子串上的所有字符都相同。

nozomi想问问聪明的你，这个子串的长度最大值是多少？

注： 次操作机会可以不全部用完。

如果想知道连续子串的说明，可以去问问eli，nozomi不想再讲一遍。

输入描述:

第一行输入两个正整数 和

输入仅有一行，为一个长度为 的、仅由字符 \mathit00 和 \mathit11 组成的字符串。

输出描述:

一个正整数，为满足条件的子串长度最大值。

示例1

输入

5 1
10101

输出

3

说明

只有 次操作机会。

将第二个位置的 0 改成 1 ，字符串变成 11101，可以选出 “111”子串，长度为3 。

如果修改第三个或者第四个位置的字符也可以选出长度为 3的子串。

题目大意：可以将01字符串的0变成1或者是将1变成0，允许变换有限次，询问经过操作之后最长的01字符串长度是多少，同理，ab字符串是可以将a变成b将b变成a,经过有限次的操作之后，询问可以得到的最长的ab字符串的长度，原理都极为相似，可以用尺取来做

尺取做法

    int n, k;
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; i++) a[i] = (int) (s[i] == '1');
    for(int i = 1; i <= n; i++) c[i] = c[i - 1] + a[i];
    int L = 1, R = n + 1, m;
    while(R - L > 1) {
        m = (L + R) >> 1;
        bool flag = false;
        for(int i = 0; !flag && i <= n - m; ++i) {
            int d = c[i + m] - c[i];
            if(d <= k || m - d <= k) flag = true;
        }
        if(flag) L = m;
        else R = m;
    }
    printf("%d", L);

这是我的代码：

将代码中的0改成a既适用于ab字符串

int n,m;
    string str;
    n=read;m=read;
    cin>>str;
    vector<int> vet(2,0);
    for(int i=0,j=0;j<str.size();j++){
        vet[str[j]-'0']++;
        maxn = max(maxn, vet[str[j]-'0']);
        while(j-i+1-maxn>m)
            vet[str[i++]-'0']--;
        res = max(res,j-i+1);
    }
    cout<<res<<endl;

开发者涨薪指南