频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu2572
2013-08-12 09:35:10      个评论      
收藏   我要投稿

终曲
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1095    Accepted Submission(s): 315


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

 

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

 

Output
请对应每组输入数据输出满足条件的最短子串;
如果没有,请输出 No

 

Sample Input
2
abcd
ab
bc
abc
ab
bd

Sample Output
abc
No


这道题我WA了无数次。。尼玛原来是把输出No看成了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;  
}  

#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;
}

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 hdu2572
上一篇:HDU4607+BFS
下一篇:CF 336C(Vasily the Bear and Sequence-贪心-不满足单调性)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站