文档章节

lwyz&tayz胡策

Loi_DL
 Loi_DL
发布于 2016/11/03 07:41
字数 617
阅读 8
收藏 0

lwyz题:

T1

 

English.pas/c/cpp

时间限制 :1s     内存限制:128M

题目描述

小Q作为一名高二党,面临着语数英学业水平考试,但他高一没好好学,非常着急,于是他找到了你,请你来帮助他学习。小Q要学的第一门课是英语,可他连字母都不会写,他打听到了一个地方,叫兔子街,他要在这学英语。这条街上有连续的n所学校,但是一所学校只会教小Q所有小写字母中的一个。小Q只能在连续的一段学校内上学,现在他想写一个单词,所以他请你帮忙,算一下他最少需要在几所学校上学才能写出这个单词。

输入描述

第一行一个数n,表示有n所学校。 接下来一行一个长度为n的仅包含小写字母的字符串,表示这n所学校分别教哪一个字母。第三行一个长度为m仅包含小写字母的字符串,表示小Q想要写的单词。 输出一行一个整数,表示小Q至少在几所学校上学,才能完整的写出这个单词。

样例输入1

7

aabbbcc

abc

样例输出1

 5

样例输入2

11

apllaeelpce

apple

样例输出2

 5

样例解释1

 由于小Q只能在一段连续的学校内上学,所以他可以在第2~6学校学习,才能学到abc三个字母。

样例解释2

小Q可以选择第2~6学校或5~9学校,都可以学到a p l e 四个字母,从而写出apple这个单词。

数据范围

对于20%数据,n,m<=200;

对于50%数据,n,m<=1000;

对于100%数据,n,m<=100,0000;

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1000233];
char b[1000233];
int used[1000233];
int n,xx,z;
int used2[1000233];
bool jc(int x)
{ 	
	for(int i=1;i<=1000;i++) used[i]=0;
	int g=0,t=1,w=x;
	while (w<=n)
	{	
		g=0;
		if(t==1)
		{
			for(int i=1;i<=w;i++)
				used[a[i]-'0']++;
		}
		else
		{
			used[a[w]-'0']++;
			used[a[t-1]-'0']--;
		}
		for(int i=1;i<=xx;i++)
		{
			if(used[b[i]-'0']>=1)
				continue;
			g=1;
		}
		if(g==0) return 1;
		else  t++,w++;
	}
	return 0;
	
}
int main()
{
	freopen("English.in","r",stdin);
	freopen("English.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",a+1);
	scanf("%s",b+1);
	xx=strlen(b+1);	
	int l=0,r=n,mid;
	while (r-l>1)
	{
		mid=(l+r)/2;
		if(jc(mid)==1) r=mid;
		else l=mid;
	}
	cout<<r;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 

 

© 著作权归作者所有

Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
真便宜。买买买!

hello,我票贩子又来了,快上车: 知乎 Live - 全新的实时问答 我就不说通过这个live你能获得什么了,自己感悟吧。嘘 我们这次live请到了以下各位: 科大讯飞执行总裁 @胡郁 (胡郁,中国科学...

军师
2017/12/01
0
0
清数大数据产业联盟成员集体亮相乌镇世界互联网大会

12月3日,为期3天的第四届世界互联网大会在乌镇盛大开幕。清数大数据产业联盟携手优秀会员企业积极参与了互联网创新创业项目系列和互联网之光博览会双创热士两场对接会。这两场对接会是在国家...

enohtzvqijxo00atz3y8
2017/12/13
0
0
通策集团-高薪诚聘【JAVA工程师】待遇:年薪10-50w+项目奖金+出国旅游

通策集团-创业项目新起航,全国各地高新招聘大力水手和A级选手 N枚: JAVA工程师 待遇: 年薪10-50w + 项目奖金 + 出国旅游 地点: 杭州(总部),(北京、上海、广州、深圳)分公司 邮箱:zhaop...

必应珠峰
2011/07/08
2.4K
14
通策集团-高薪诚聘【C/C++(高级)软件工程师】待遇:年薪10-50w+项目奖金+出国旅游

通策集团-创业项目新起航,全国各地高新招聘大力水手和A级选手 N枚: C/C++(高级)软件工程师 待遇: 年薪10-50w + 项目奖金 + 出国旅游 地点: 杭州(总部),(北京、上海、广州、深圳)分公司...

必应珠峰
2011/07/08
2.3K
4
从实习生到研究员:夏应策的转正攻略

     2009年,夏应策进入中国科学技术大学信息学院信息安全专业;2012年,他来到微软亚洲研究院实习; 2013年,他获得工学学士学位,并成为中国科学技术大学—微软亚洲研究院联合培养博士...

微软亚洲研究院
2018/12/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
15分钟前
0
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
23分钟前
0
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
35分钟前
0
0
聊聊Elasticsearch的CircuitBreakerService

序 本文主要研究一下Elasticsearch的CircuitBreakerService CircuitBreakerService elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/indices/breaker/CircuitBreakerService.ja......

go4it
39分钟前
3
0
Spring系列教程六:AOP详细讲解

AOP 概述 什么是 AOP AOP:全称是 Aspect Oriented Programming 即:面向切面编程。 AOP技术是对OOP技术的一种延伸,AOP是面向纵向,OOP是面向横向。简单的说它就是把我们程序重复的代码抽取...

我叫小糖主
53分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部