Broken Keyboard SDUTOJ

2024-08-25 08:32
文章标签 sdutoj broken keyboard

本文主要是介绍Broken Keyboard SDUTOJ,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

Bruce Force\'s keyboard is broken, only a few keys are still working. Bruce has figured out he can still type texts by switching the keyboard layout whenever he needs to type a letter which is currently not mapped to any of the m working keys of the keyboard.

You are given a text that Bruce wishes to type, and he asks you if you can tell him the maximum number of consecutive characters in the text which can be typed without having to switch the keyboard layout. For simplicity, we assume that each key of the keyboard will be mapped to exactly one character, and it is not possible to type other characters by combination of different keys. This means that Bruce wants to know the length of the largest substring of the text which consists of at most m different characters.

输入

The input contains several test cases, each test case consisting of two lines. The first line of each test case contains the number m (1 ≤ m ≤ 128), which specifies how many keys on the keyboard are still working. The second line of each test case contains the text which Bruce wants to type. You may assume that the length of this text does not exceed 1 million characters. Note that the input may contain space characters, which should be handled like any other character.

The last test case is followed by a line containing one zero.

输出

 

示例输入

5
This can\'t be solved by brute force.
1
Mississippi
0

示例输出

7
2

提示

Hint: The largest substring for the first test case is "_by_bru", where _ stands for a space character.

题意:
给定几个字符的数目,一个字符串,求这个字符串中连续出现n个字符的最长子串长度

从头到尾遍历,借助标记法,不需要回溯

#include <stdio.h>
#include <string.h>char mapp[1000009];
int bj[1000];
int main()
{int n,len,left,right,slong,n1,m_long;while(~scanf("%d",&n),n){getchar();gets(mapp);memset(bj,0,sizeof(bj));len = strlen(mapp);left = right = slong = n1 = m_long = 0;while(left <= right && right < len){while(n1 <= n && right < len)//子串中不同字符的个数不能超过规定的字符数{if(bj[mapp[right]] == 0)//该字符没有出现过{bj[mapp[right]] = 1;//标记为已出现n1++;//字符种类数增加if(n1 > n)break;}elsebj[mapp[right]]++;right++;slong++;//子串长度增加}if(slong > m_long)m_long = slong;if(right >= len)break;while(1)//实现左区间向前移{//如果作为左端点的字符出现过的次数不是一次,则肯定不会是最长的字符串,所以无需遍历bj[mapp[left]]--;if(bj[mapp[left]] == 0)break;left++;slong--;}left++;n1--;right++;}printf("%d\n",m_long);}return 0;
}


这篇关于Broken Keyboard SDUTOJ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

Log,Toast,SPUtil,Density,SDCard,ScreenUtil,AppVersion,KeyBoard,NetWork,HttpUtil工具类

转载请标明出处:http://blog.csdn.net/lmj623565791/article/details/38965311,本文出自【张鸿洋的博客】 最近统一整理下工具类,以下是栏目,慢慢的就会越来越丰富 http://blog.csdn.net/u013210620/article/category/6251289 1、LogUtil package com.exampl

leetcode500 Keyboard Row Java

Description Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below. Example 1: Input: [“Hello”, “Alaska”,

hdu Broken Keyboard(模拟)

http://acm.hdu.edu.cn/showproblem.php?pid=2369 题意:给出一个字符串,求出含有n个不同字母且长度最长的长度。 比赛时脑残的以为是DP,想了很久。。愣是没发现字符串长度1million。直接模拟,设置一个st,记录从st开始的最长的长度,长度大于n时,就要从st开始删除直到含有n个不同字母为止。 #include <stdio.h>#i

SDUTOJ 2073 —— 活动选择问题 贪心

题目描述  sdut 大学生艺术中心每天都有n个活动申请举办,但是为了举办更多的活动,必须要放弃一些活动,求出每天最多能举办多少活动。 输入  输入包括多组输入,每组输入第一行为申请的活动数n,从第2行到n+1行,每行两个数,是每个活动的开始时间b,结束时间e; 输出  输出每天最多能举办的活动数。 示例输入 1215 2015 198 1810 15

SDUTOJ 1018 骨牌铺方格 递推

题目描述 在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图: 输入 输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。 输出 对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。 示例输入 132

SDUTOJ 2072 删数问题 贪心

删数问题 Time Limit: 1000MS Memory limit: 65536K 题目描述  键盘输入一个高精度的正整数n(≤100位),去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s,寻找一种方案,使得剩下的数字组成的新数最小。 输入   输入有多组 每组包括原始数n,要去掉的数字数s;

SDUTOJ 2077 迷瘴 贪心

迷瘴 Time Limit: 1000MS Memory limit: 65536K 题目描述  通过悬崖的yifenfei,又面临着幽谷的考验—— 幽谷周围瘴气弥漫,静的可怕,隐约可见地上堆满了骷髅。由于此处长年不见天日,导致空气中布满了毒素,一旦吸入体内,便会全身溃烂而死。 幸好yifenfei早有防备,提前备好了解药材料(各种浓度的万能药水)。现在只

SDUTOJ 2074 区间覆盖问题 贪心

区间覆盖问题 Time Limit: 1000MS Memory limit: 65536K 题目描述  用i来表示x坐标轴上坐标为[i-1,i]的长度为1的区间,并给出n(1≤M≤200)个不同的整数,表示n个这样的区间。 现在要求画m条线段覆盖住所有的区间, 条件是:每条线段可以任意长,但是要求所画线段的长度之和最小, 并且线段的数目不超过N(1≤

SDUTOJ 3115 小鑫找基友 ——素数筛

小鑫找基友 Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述 小鑫身上有一个特殊的光环,就是吸引基友的光环。小鑫身上有一个能力值,小鑫能吸引基友的数量为能力值内的质因子的个数。 例如: 小鑫的能力值为12,12 = 2^2*3,那么12包含两个质因子2和3,所以小鑫可以吸引2个基友。