HDU (1894 String Compare)

spoiler posted @ 2011年5月11日 02:50 in 各种比赛题目收集 , 1791 阅读

题目大意:给你N个单词,让你找出有多少对满足一个单词是另一个单词的前缀

题目分析:这种题目肯定要排序,这样就可以按字典顺序操作了,一个单词是另一个单词的前缀,那么这个单词肯定和他相邻,或者相近,我这里说的是按字典顺序,从小到大,从前面开始往后找,找到不是的那个为止,加上前面已经找到的,然后就这样遍历一遍就OK啦

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
    char s[35];
}sim[50100];
int cmp(struct node a,struct node b){
    if(strcmp(a.s,b.s)<0)
        return 1;
    else
        return 0;
}
bool solve(char a[],char b[]){
    int len1,len2,i;
    len1=strlen(a);
    len2=strlen(b);
    char c[35];
    if(len1==len2)//注意一下这个判断就可以了,
    //因为题目说,没有两个相同的单词
        return false;
    for(i=0;i<len1;i++){
        if(a[i]!=b[i]){
            return false;
        }
    }
    return true;
}
int main(){
    int n,cas,i,j,sum;
    while(scanf("%d",&cas)!=EOF){
        while(cas--){
            sum=0;
            scanf("%d",&n);
            for(i=0;i<n;i++)
                scanf("%s",sim[i].s);
            sort(sim,sim+n,cmp);
            for(i=0;i<n-1;i++){
                for(j=i+1;j<n;j++){
                    if(solve(sim[i].s,sim[j].s))
                        sum++;
                    else
                        break;
                }
        
            }    
            if(sum>11519)
                sum=sum%11519;
            printf("%d\n",sum);
        }
    }
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter