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

。。MLE了N次后79MS飘过

Posted by dahailixuxu at 2013-04-18 17:32:24 on Problem 2408
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gcnt=0,L=0,N=0;
char s[30005][30],tmp[30];

struct GROUP
{
    int cnt,cur;
    char **p;
}*group[30005];

struct Trie
{
    int id;
    Trie *p[27];
}*root,pool[1000000];

int idx(char c)
{
    return c-'a';
}

int search(char *s)
{
    Trie *p=root;
    for(int i=0;s[i]!=0;i++)
    {
        int c=idx(s[i]);
        if(!p->p[c])
            return -1;
        p=p->p[c];
    }
    return p->id;
}

int insert(char *s)
{
    Trie *p=root;
    for(int i=0;s[i]!=0;i++)
    {
        int c=idx(s[i]);
        if(!p->p[c])
        {
            Trie *q=&pool[L++];
            q->id=-1;
            p->p[c]=q;
        }
        p=p->p[c];
    }
    group[gcnt]=new GROUP;
    group[gcnt]->cnt=0;
    group[gcnt]->cur=0;
    return p->id=gcnt++;
}

bool cmp1(char a,char b)
{
    return a<b;
}

bool cmp2(char *a,char *b)
{
    if(strcmp(a,b)<0)
        return 1;
    else
        return 0;
}

bool cmp3(GROUP *a,GROUP *b)
{
    if(a->cnt==b->cnt)
        return cmp2(a->p[0],b->p[0]);
    return a->cnt>b->cnt;
}


int main()
{
    root=&pool[L++];
    root->id=-1;
    while(~scanf("%s",s[++N]))
    {
        strcpy(tmp,s[N]);
        int len=strlen(tmp);
        sort(tmp,tmp+len,cmp1);
        int id=search(tmp);
        if(id==-1)
            id=insert(tmp);
        group[id]->cnt++;
    }
    N--;
    for(int i=0;i<gcnt;i++)
        group[i]->p=new char*[group[i]->cnt];
    for(int i=1;i<=N;i++)
    {
        strcpy(tmp,s[i]);
        int len=strlen(tmp);
        sort(tmp,tmp+len,cmp1);
        int id=search(tmp);
        int t=0;
        for(;t<group[id]->cur;t++)
        {
            if(strcmp(s[i],group[id]->p[t])==0)
                break;
        }
        if(t==group[id]->cur)
        {
            group[id]->p[t]=new char[30];
            strcpy(group[id]->p[t],s[i]);
            group[id]->cur++;
        }
    }
    for(int i=0;i<gcnt;i++)
        sort(group[i]->p,group[i]->p+group[i]->cur,cmp2);
    sort(group,group+gcnt,cmp3);
    for(int i=0,flag=0;i<gcnt && flag<5;i++)
    {
        printf("Group of size %d: ",group[i]->cnt);
        for(int j=0;j<group[i]->cur;j++)
            printf("%s ",group[i]->p[j]);
        printf(".\n");
        flag++;
    }
    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