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

Tabris

CSDNcodeforces思维

发布于：2016年5月31日

次浏览

[原创]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;
}

本页文档最后更新于：2021年5月16日

CSDN

string

c语言

codeforces