[2021.11.19]UPC-2021级新生个人训练赛第4场-19276 Problem B ok 字符串

2024-04-14 18:32

本文主要是介绍[2021.11.19]UPC-2021级新生个人训练赛第4场-19276 Problem B ok 字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

商场中展示了这么多玩具,乐乐爱不释手。现在游戏环节开始,只要你能解决一个问题,就能够挑选一件精美的玩具。此时,乐乐需要你们这帮“牛娃”的帮助,请你帮助乐乐解决这个问题。 
现在给你一个长度为 n 的字符串,该字符串只包含字符’o’和’k’。你最多可以修改 t 个字符(将字符’o’改为字符’k’或将字符’k’改为字符’o’),使得某一段连续相同的字符个数是最多的。
例如:  ‘ooooo’或’kkkkk’像这样的连续相同字符都可以。 
请你经过不多于t次地合理修改,帮助乐乐求出字符串某一段连续相同的字符最多个数。

输入

第一行输入整数 n 和 t,分别表示字符串的总长度和最多可以修改的字符数。 
第二行输入一行字符串,仅包含字符‘o‘或‘k‘。

输出

输出一个整数,表示经过不多于 t 次地合理修改,字符串某一段连续相同的字符最多个数

样例输入 Copy

【样例1】
4 2 
okko 
【样例2】
8 3 
ookookoo 

样例输出 Copy

【样例1】
4
【样例2】
8

提示

样例一:通过 2 次修改后,可以获得字符串‘oooo‘或‘kkkk‘,所以连续的字符个数是 4。 
样例二:虽然 t 是 3,但只需通过 2 次修改后,可以获得字符串‘oooooooo‘,连续的字符个数是 8。 

对于 80%的数据,保证 1<=n<=10000,0<=t<=n。 
对于另外 20%的数据,保证 n<=1000000, 0<=t<=10000,并保证字符‘o‘的总个数<=10000
或字符‘k‘的总个数<=10000。 

我这个做法属实复杂了!: ( 

但好像大家思路都大致相同~:从前到后遍历字符串,(我这个是从后到前)记录o和k出现的次数

如果修改次数足以让当前所遍历的字符串变成连续的,就继续往下遍历,记录下当前字符串长度,再与所记录的最大长度进行比较。

如果不能让当前字符串变为连续的,就从前往后缩减字符串长度,直至修改次数可以使当前字符串变为连续的,记录下当前字符串长度,再与所记录的最大长度进行比较。

通过这个思路,大家应该能轻松编出比我简单得多得多的代码 ;),或者直接在CSDN里搜往届学长的代码也行~

以下是我的代码 : )

#include <cstdio>
using namespace std;
int c[1000010];    //c[i]用于记录从0到i为止o和k字符出现的次数
int main(){char a;int n,j,k,i,ans=1;scanf("%d %d",&n,&k);scanf(" %c",&a);if(a=='o')c[0]=1;        //若为o  则为1elsec[0]=-1;        //若为k  则为-1for(i=1;i<n;i++){scanf("%c",&a);if(a=='o')c[i]=c[i-1]+1;elsec[i]=c[i-1]-1;  }for(i=n-1;i>=ans;i--)    //当i<=当前所记录的最大的经修改后的连续字符串长度时退出循环for(j=-1;j<i;j++){    //因为不可能得到更长的连续字符串了if (j == -1) {    //j为-1时 说明不需要缩减长度,if (c[i]+2*k>=i+1 || c[i]- 2*k<=-(i+1)){  //判断是否可以修改为连续字符串if (i - j + 1 > ans){  ans = i + 1;}break;}}else {    if (c[i] - c[j] + 2*k >= i - j|| c[i] - c[j] - 2*k <= -(i-j)) {if (i - j > ans){ans = i - j;}break;};}}printf("%d ",ans);return 0;
}

U

这篇关于[2021.11.19]UPC-2021级新生个人训练赛第4场-19276 Problem B ok 字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/903690

相关文章

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3