[原创]codeforces #354 div.2 C &&676C Vasya and String

2016-05-31 13:10:56 Tabris_ 阅读数：532

博客爬取于2020-06-14 22:44:25
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51544872

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

C. Vasya and String
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
High school student Vasya got a string of length n as a birthday present. This string consists of letters ‘a’ and ‘b’ only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?

Input
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters ‘a’ and ‘b’ only.

Output
Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.

Examples
input
4 2
abba
output
4
input
8 1
aabaabaa
output
5
Note
In the first sample, Vasya can obtain both strings “aaaa” and “bbbb”.

In the second sample, the optimal answer is obtained with the string “aaaaabaa” or with the string “aabaaaaa”.

题目大意 ：
给你一个长度为n且只有a和b构成的字符串，你可以改变k个字母 ，即a变b b变a。。
问在你操作后 的最长子串的长度是多少。。
子串要求只有一种字母构成 ；

解题思路 ：
分别计算一下 全是a的子串与全是b的自创最长能多长 ，取两个最大值即可；

我就是给字符串标一下号 ，并记录他们的位置 然后找到中间存在

举个栗子：(对的不是很齐 , 表格的话有太影响观看,最后就只能这样了)
aabaabaa
求a的子串的时候记录b的位置
-aabaabaa-
1–2–3–4 <–这是序号
-1 2 5 8 <–这是位置

求b的子串的时候记录a的位置
-aabaabaa-
123-45-678 <–这是序号
-1 0 1 3 4 6 7 8 <–这是位置

然后找中间有m个的区间 求一下开区间内的长度即可

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# include<iostream>
# include<stdio.h>
# include<string.h>
# include<algorithm>
# include<stdlib.h>
using namespace std;

char s[100050];
int posa[100050],posb[100050];

int main()
{

    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",s);

    int na=1,nb=1;
    posa[0]=posb[0]=-1;

    for(int i=0;i<n;i++)
    {
        if(s[i]=='a')
            posa[na++]=i;
        if(s[i]=='b')
            posb[nb++]=i;
    }

    posa[na]=posb[nb]=n;

    int mida=-1,midb=-1;
    for(int i=m;i<na;i++)
    {
        mida=max(mida,posa[i+1]-posa[i-m]-1);
    }

    for(int i=m;i<nb;i++)
    {
        midb=max(midb,posb[i+1]-posb[i-m]-1);
    }
    if(na<=m||nb<=m)  //这个部分主要是看代码如何处理 处理好的话就不需要这里了
        mida=n;
    printf("%d\n",max(mida,midb));

    return 0;
}