[ZJOI2013]丽洁体

题目分析

首先分析一下题目,就是给定一个由单词组成的序列,然后,在给出三个字符串序列,要求如何组成 \(A...B...C\)的形式

先注意输入,如果采用不当的方法,就算下面的算法是正确的,也会超时,可以用
\(getchar\),再处理换行

然后,针对一个贪心的想法,找到\(A\)的最位置,然后依次寻找\(B,C\),这样做,似乎是对的,但一个序列的起始位是不一定越靠前,越优

实际上,第一个是满足上诉贪心的,最后一个也是有类似贪心的,于是,就只需要考虑中间位置即可,枚举

注意,要判断匹配是边界的判断

#include<bits/stdc++.h>
using namespace std;
char s;
string ai[500005],a[500005],b[500005],c[500005];
int lena,lenb,lenc,len;
int read_()
{
	char s;
	s=getchar();
	while(s<=32)
	{
		s=getchar();
	}
	int cnt=0;
	while(1)
	{
		++cnt;
		while(s>32){
			ai[cnt]+=s;
			s=getchar(); 
		}
		while(s<=32){
			if(s=='\n'||s==EOF)
			{
				break;
			}
			s=getchar();
		}
		if(s=='\n'||s==EOF)
		{
			break;
		}
	}
	return cnt;
}
int read_a()
{
	char s;
	s=getchar();
	while(s<=32)
	{
		s=getchar();
	}
	int cnt=0;
	while(1)
	{
		++cnt;
		while(s>32){
			a[cnt]+=s;
			s=getchar(); 
		}
		while(s<=32){
			if(s=='\n'||s==EOF)
			{
				break;
			}
			s=getchar();
		}
		if(s=='\n'||s==EOF)
		{
			break;
		}
	}
	return cnt;
}
int read_b()
{
	char s;
	s=getchar();
	while(s<=32)
	{
		s=getchar();
	}
	int cnt=0;
	while(1)
	{
		++cnt;
		while(s>32){
			b[cnt]+=s;
			s=getchar(); 
		}
		while(s<=32){
			if(s=='\n'||s==EOF)
			{
				break;
			}
			s=getchar();
		}
		if(s=='\n'||s==EOF)
		{
			break;
		}
	}
	return cnt;
}
int read_c()
{
	char s;
	s=getchar();
	while(s<=32)
	{
		s=getchar();
	}
	int cnt=0;
	while(1)
	{
		++cnt;
		while(s>32){
			c[cnt]+=s;
			s=getchar(); 
		}
		while(s<=32){
			if(s=='\n'||s==EOF)
			{
				break;
			}
			s=getchar();
		}
		if(s=='\n'||s==EOF)
		{
			break;
		}
	}
	return cnt;
}
int main()
{
	len=read_();
	lena=read_a();
	lenb=read_b();
	lenc=read_c();
	int ans=0;
	int now=1;
	int nowa=1;
	while(nowa<=lena)
	{
		if(ai[now]==a[nowa])
		{
			nowa++;
			now++;
		}
		else
		{
			ans++;
			now++;
		}
	}
	int l=now;
	now=len;
	int nowc=lenc;
	while(nowc>=1)
	{
		if(ai[now]==c[nowc])
		{
			now--;
			nowc--;
		}
		else
		{
			ans++;
			now--;
		}
	 } 
	 int r=now;
	 int minans=0x3f3f3f3f;
	 for(int i=l;i<=r;i++)
	 {
	 	if(ai[i]==b[1])
	 	{
	 		int tot=0;
	 		int sta=i;
	 		int nowb=1;
	 		while(nowb<=lenb&&sta<=len)
	 		{
	 			if(ai[sta]==b[nowb])
	 			{
	 				sta++;
	 				nowb++;
				 }
				 else
				 {
				 	sta++;
				 	tot++;
				 }
			 }
			 if(sta<=len)
			 {
			 	minans=min(minans,tot);
			 }
			
		 }
	 }
	printf("%d",ans+minans);
}
上一篇:Servlet生命周期


下一篇:Luogu P3527 [POI2011]MET-Meteors 整体二分