BZOJ 1174: [Balkan2007]Toponyms

Time Limit:10 SecMemory Limit:128 MBSubmit:735Solved:102[Submit][Status][Discuss]Description

给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.

Input

第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 。保证输入文件不超过10MB

Output

a single line with an integer representing the maximal level of complexityLc(T).

Sample Input7Jora de SusOrheiJora de MijlocJoreniJora de JosJapcaOrheiul VechiSample Output24HINT

这题有毒啊，，

思路和算法没什么好说的，

就是建一棵字典树，统计好深度和个数，然后乘起来，取最大值

但是！！！

本蒟蒻一开始写的无限RE

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int n,sz=1,ans; 6 string ch; 7 int a[500001][53],f[500001]; 8 void insert() 9 {10     int l=ch.length(),now=0;11     for(int i=0;i<l;i++)12     {13         int t;14         if(ch[i]==' ')t=52;15         else if(ch[i]<='Z')t=ch[i]-'A';16         else t=ch[i]-'a'+26;17         if(a[now][t])now=a[now][t];18         else now=a[now][t]=++sz;19         f[now]++;20         ans=max(ans,f[now]*(i+1));21     }22 }23 int main()24 {25     scanf("%d",&n);26     for(int i=1;i<=n;i++)27     {28        getline(cin,ch);29        insert();30     }31     printf("%d",ans);32     return 0;33 }

RE

后来听别人说这题卡内存，

于是我换成了前向星储存，

然后，

无限TLE，

加了各种常数优化还是无限TLE

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #include<queue> 8 using namespace std; 9 const int MAXN=1001;10 inline void read(int &n)11 {12     char c='+';bool flag=0;n=0;13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}14     while(c>='0'&&c<='9')n=n*10+c-48,c=getchar();15 }16 struct E17 {18     int u,v,nxt;19 }edge[MAXN];20 int head[MAXN];21 int num=1;22 struct node23 {24     int bh;25     int num;26     int val;27     node(){num=0;val=0;}28 }trie[MAXN];29 int tot=0;30 char a[MAXN];31 bool vis[MAXN];32 inline void add_edge(int x,int y)33 {34     edge[num].u=x;35     edge[num].v=y;36     edge[num].nxt=head[x];37     head[x]=num++;38 }39 long long int ans=0;40 inline void insert(char *a)41 {42     int l=strlen(a);int now=0;43     for(register int i=0;i<l;i++)44     {45         bool flag=0;46         int debug=a[i];47         for(register int j=head[now];j!=-1;j=edge[j].nxt)48         {49             if(trie[edge[j].v].val==a[i])50                 trie[edge[j].v].num++,51                 flag=1,52                 now=edge[j].v;53         }54         if(flag==0)55             {56                 trie[++tot].bh=tot;57                 trie[tot].num=1;58                 trie[tot].val=a[i];59                 add_edge(now,tot);60                 now=tot;61             }62         ans=max(ans,(long long )(i+1)*trie[now].num);63     }64 }65 int main()66 {67     memset(head,-1,sizeof(head));68     int n;69     read(n);70     for(int i=1;i<=n;i++)71     {72         memset(a,0,sizeof(a));int hh=0;73         char ch=getchar();bool flag2=0;74         while(ch=='\n')    ch=getchar();     75         while(ch!='\n')76             a[hh++]=ch,ch=getchar();    77         insert(a);    78     }79     printf("%lld",ans);80     return 0;81 }

TLE

然后只好参考别的大神的代码…….

编译速度就秒杀我的代码。。。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define N 5000010 5 using namespace std; 6 int tot = 1 , head[N] , to[N] , next[N] , cnt , si[N]; 7 char val[N]; 8 void add(int x , int y , char c) 9 {10     to[++cnt] = y , val[cnt] = c , next[cnt] = head[x] , head[x] = cnt;11 }12 int main()13 {14     int n , i , j , k , t , p;15     char ch;16     long long ans = 0;17     scanf("%d" , &n);18     for(i = 1 ; i <= n ; i ++ )19     {20         ch = getchar();21         while(ch == '\n') ch = getchar();22         for(j = t = 1 ; ch != '\n' ; j ++ , ch = getchar())23         {24             for(p = 0 , k = head[t] ; k ; k = next[k])25             {26                 if(val[k] == ch)27                 {28                     p = to[k];29                     break;30                 }31             }32             if(!p) add(t , p = ++tot , ch);33             t = p , si[t] ++ , ans = max(ans , (long long)j * si[t]);34         }35     }36     printf("%lld\n" , ans);37     return 0;38 }

没有口水与汗水，就没有成功的泪水。