codeforces 354 div2 C Vasya and String 前缀和
1 second
256 megabytes
standard input
standard 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 denotesbeauty 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?
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.
Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.
4 2
abba
4
8 1
aabaabaa
5
题意:一个只由'a','b'组成的字符串,长度为n,可以改变k个,求连续最长;
思路:找出连续a的长度,包括0,同样的b也是,求前缀和,求出以k为长度最长的子串;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 999999999
#define pi 4*atan(1)
//#pragma comment(linker, "/STACK:102400000,102400000")
int flaga[],jia;
int flagb[],jib;
int disa[];
int disb[];
int suma[];
int sumb[];
char a[];
int main()
{
int x,y,z,i,t;
scanf("%d%d",&x,&y);
scanf("%s",a+);
flaga[]=;
jia=;
flagb[]=;
jib=;
for(i=;i<=x;i++)
{
if(a[i]=='a')
flaga[jia++]=i;
else
flagb[jib++]=i;
}
flaga[jia++]=x+;
flagb[jib++]=x+;
for(i=;i<jib;i++)
disa[i]=flagb[i]-flagb[i-]-;
for(i=;i<jia;i++)
disb[i]=flaga[i]-flaga[i-]-;
for(i=;i<=;i++)
suma[i]+=suma[i-]+disa[i];
for(i=;i<=;i++)
sumb[i]+=sumb[i-]+disb[i];
int ans=;
for(i=;i<jia;i++)
ans=max(ans,sumb[i+y]-sumb[i-]);
int ans1=;
for(i=;i<jib;i++)
ans1=max(ans1,suma[i+y]-suma[i-]);
if(min(jia,jib)-<=y)
printf("%d\n",x);
else
{
printf("%d\n",max(ans1,ans)+y);
}
return ;
}
最新文章
- 关于js单线程(转载)
- 元组tuple
- iOS @try @catch简单应用举例
- PHP自定义函数使用外部变量
- 在非MFC程序中引用CString
- 【转】补充说明:关于Beaglebone black上debian无图形界面的问题及QT的窗口示例
- 关于css样式line-height的应用
- poj 2531 Network Saboteur(经典dfs)
- mac下使用命令行打包出现bash gradle command not found的解决方案
- Material Theme 文件名的标签(tab)被大写了
- C++对象模型(二):The Semantics of Copy Constructors(拷贝构造函数之编译背后的行为)
- 居中 html css
- [error] - Build path is incomplete. Cannot find class file for org/aspectj/weaver/refl
- selenium模拟登陆淘宝
- wildfly 10上使用最新的 Hibernate ORM OGM
- bzoj 2186
- saltstack学习之一:服务架构以及相关配置安装运行
- Bootstrap插件概述
- MongoDB学习笔记(一)安装配置
- asp.net错误记录