首页 > ACM题库 > HDU-杭电 > hdu 2572 终曲-模拟-[解题报告]C++
2014
02-10

hdu 2572 终曲-模拟-[解题报告]C++

终曲

问题描述 :

最后的挑战终于到了!
站在yifenfei和MM面前的只剩下邪恶的大魔王lemon一人了!战胜他,yifenfei就能顺利救出MM。
Yifenfei和魔王lemon的挑战很简单:由lemon给出三个字符串,然后要yifenfei说出第一串的某个子串,要求该子串长度最小,并且同时包含第2个串和第3个串。
特别地,如果有多个这样的子串,则请输出字母序最小的一个。

输入:

输入数据首先是一个整数C,表示测试数据有C组;
接着是C组数据,每组包含三行字符串,第一个字符串长度大于1小于100
后面两个串的长度大于1且小于10

输出:

输入数据首先是一个整数C,表示测试数据有C组;
接着是C组数据,每组包含三行字符串,第一个字符串长度大于1小于100
后面两个串的长度大于1且小于10

样例输入:

2
abcd
ab
bc
abc
ab
bd

样例输出:

abc
No

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=100+10;
char a[MAX],b[15],c[15];
int s,t,len;

bool Strcmp(int i,int j,int x,int y){
    while(i<=j){
        if(a[x]<a[i])return true;
        if(a[x]>a[i])return false;
        ++i,++x;
    }
    return false;
}

void PP(int B,int lenb,int C,int lenc){
	if(B<C && B+lenb<=C+lenc){
		if(C+lenc-B<len)s=B,t=C+lenc-1,len=C+lenc-B;
		else if(C+lenc-B == len && Strcmp(s,t,B,C+lenc-1))s=B,t=C+lenc-1;
	}
	if(B>=C && B+lenb<=C+lenc){
		if(lenc<len)s=C,t=C+lenc-1,len=lenc;
		else if(lenc == len && Strcmp(s,t,C,C+lenc-1))s=C,t=C+lenc-1;
	}
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>a>>b>>c;
        int lena=strlen(a),lenb=strlen(b),lenc=strlen(c);
		int B=-1,C=-1,flagb=0,flagc=0;//B,C分别代表上一次a串中出现b,c的起始位置 
        s=-1,t=-1,len=INF;//s,t表示最短包含字串b,c的起始位置和终止位置 
        for(int i=0;i<lena;++i){
            flagb=flagc=0;
			if(a[i] == b[0]){
            	int k=0;
            	while(k<lenb && a[i+k] == b[k])++k;
            	if(k == lenb){
	            	flagb=1;
	            	if(C != -1)PP(C,lenc,i,lenb);//B有新的出现位置,判断是否可以更新更短的字串 
	            }
            }
            if(a[i] == c[0]){
            	int k=0;
            	while(k<lenc && a[i+k] == c[k])++k;
            	if(k == lenc){
	            	flagc=1;
	            	if(B != -1)PP(B,lenb,i,lenc);//C有新的出现位置,判断是否可以更新更短的字串 
	            }
            }
            if(flagb){
            	if(C != -1)PP(i,lenb,C,lenc);//用本次更新的B位置去更新更短字串 
            	if(flagc)PP(i,lenb,i,lenc);//用本次更新的B和C去更新更短字串 
            }
            if(flagc){
            	if(B != -1)PP(i,lenc,B,lenb);//用本次更新的C位置去更新更短字串 
            	if(flagb)PP(i,lenc,i,lenb);//用本次更新的C和B去更新更短字串 
            }
            if(flagb)B=i;//更新出现的B位置 
            if(flagc)C=i;//更新出现的C位置 
        }
        if(s != -1){
            for(int i=s;i<=t;++i)cout<<a[i];
            cout<<endl;
        }
        else cout<<"No"<<endl;
    }
    return 0;
}

解题转自:http://blog.csdn.net/xingyeyongheng/article/details/9879359


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  3. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  4. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!