首页 > 代码库 > HDU 1894 String Compare （排序）

HDU 1894 String Compare （排序）

2024-08-07 10:38:41   220人阅读

String Compare

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3124    Accepted Submission(s): 740


Problem Description
Maybe there are 750,000 words in English and some words are prefix of other words, for example: the word "acm" can be treat as one prefix of "acmicpc". What‘s more, most of such pairs of words have relationship between them. Now give you a dictionary, your work is to tell me how many such pairs. 


There may be other characters in the word, for example ‘_‘,‘-‘,and so on. 
Pay attention that ‘A‘ and ‘a‘ are not the same character! 
 

Input
In the first line of the input file there is an Integer T, which means the number of test cases. Followed by T test cases. 
For each test case, in the first line there is an integer N(0<N<=50000), followed N lines, each contains a word whose length is less than 30 and no space appears in any word. There are no same words in two different lines. 
 

Output
For each test case, tell me how many such pairs. If the number is larger than 11519, just divide it by 11519 and only output the remainder. 
 

Sample Input
2
2
acmicpc
acm
3
a
abc
ab
 

Sample Output
1
3
 
这道题败在了超时上面，一开始是用vector，string，很显然，是得用cin，结果超时了

后来，改用cin，结果还是超时，原因是既然是排好序了，那么一旦不匹配了，后面的字符串，都不需要比较了

结果，不超时了，改WA了，又是怎么回事呢？

 If the number is larger than 11519, just divide it by 11519 and only output the remainder.

问题在上面，不该直接ans%11519 。。。擦好好读题以后

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct node{
    char a[50];
}node;
node s[50010];
void swap(node *a,node *b){
    char t[50];
    strcpy(t,a->a);
    strcpy(a->a,b->a);
    strcpy(b->a,t);
}
int partition(node a[],int l,int h){
    int i=l;
    int j=h+1;
    node v=a[l];
    while(true){
        while(strcmp(a[++i].a,v.a)<0)if(i==h)break;
        while(strcmp(a[--j].a,v.a)>0)if(j==l)break;
        if(i>=j)break;
        swap(&a[i],&a[j]);
    }
    swap(&a[l],&a[j]);//i停留的位置是比partition大的，j是小的
    return j;
}
void quick_sort(node a[],int l,int h){
    if(h<=l)return ;
    int j= partition(a,l,h);
    quick_sort(a , l , j-1);
    quick_sort(a , j+1 , h);
}
bool cmp(node a1,node b1)
{
    return strcmp(a1.a,b1.a)<0;
}
int main(int argc, char *argv[])
{
    //freopen("1894.in","r",stdin);
    int T;
    int N;
    scanf("%d",&T);
    int ans=0;
    int len;
    int k;
    while(T--){
        ans=0;
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",s[i].a);
        }
        //sort(s,s+N,cmp);
        quick_sort(s , 0, N-1);
        for(int i=0;i<N;++i)
        {
            len=strlen(s[i].a);
            for(int j=i+1;j<N;++j)
            {
                for(k=0;k<len;++k)
                {
                    if(s[i].a[k]!=s[j].a[k])break;
                }
                if(k==len)
                    ans++;
                else break;//后面的都不可能匹配了
            }
        }
         if(ans>11519) ans=ans%11519;
         printf("%d\n",ans);
    }
    return 0;
}
再次比较下自己写的快排和STL的sort的差距

自己写的：

STL的：



HDU 1894 String Compare （排序）


联系
我们