Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

字符串排序会慢的……

Posted by frkstyc at 2005-08-08 01:14:51 on Problem 1002
In Reply To:你不加排序怎么可能过?可怜我陪你一起写到这么晚。下面是我的,共参考。 Posted by:tengshengbo at 2005-08-08 01:11:22
> 这个程序是我刚写的,以前那个ac的找不到了。
> 我把字符串全变成数,又变回去。
> 我觉得直接字符串存储,把字符串排序可能更快。
> #include<cstdio>
> #include<iostream>
> #include<map>
> #include<string>
> using namespace std;
> char tmp[100];
> int all[100005];
> int cmp(int *a,int *b)
> {
>     return *a-*b;
> }    
> int key[26] = {2,2,2,3,3,3,4,4,4,
>          5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9,};
> int main()
> {
>   
> 
>     int n;
>     scanf("%d",&n);
>     int i;
>     for(i=0;i<n;i++) all[i]=0;
>     for(int x=0;x<n;x++)
>     {
>        scanf("%s",&tmp);
>         int one=0;
>         int j=strlen(tmp);
>         for(i=0;i<j; i++)
>         {
>             if(tmp[i]<='9'&&tmp[i]>='0')
>                 one=one*10+tmp[i]-'0';
>             else
>                 if(tmp[i]<'Z'&&tmp[i]>='A')
>                     one=one*10+key[tmp[i]-'A'];
>         }    
>         all[x]=one;
>     }
>     qsort(all,n,sizeof(all[0]),(int (*)(const void *,const void *))cmp);
>     int x=0;
>     i=0;
>     int j;
>     while(i<n-1)
>     {
>         j=i+1;
>         while((all[j]==all[i])&&(j<n)) j++;
>         if(j>i+1)
>         {
>             x=1;
>             //print(all[i],j-i);
>             int t=all[i];
>             char p[9];
>             p[0]=t/1000000+'0';
>             t=t%1000000;
>             p[1]=(t/100000)+'0';
>             t=t%100000;
>             p[2]=t/10000+'0';
>           t=t%10000;
>             p[3]='-';
>             p[4]=t/1000+'0';
>           t=t%1000;
>             p[5]=t/100+'0';
>           t=t%100;
>             p[6]=t/10+'0';
>           t=t%10;
>             p[7]=t+'0';
>             p[8]=0;
>             cout<<p;
>             cout<<" "<<j-i<<endl;
>             i=j;
>         }
>         else i++;    
>     }    
>     if(x==0) cout<<"No duplicates."<<endl;
>              
>     return 0;
> }  

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator