首页 > 代码库 > BZOJ 1174: [Balkan2007]Toponyms
BZOJ 1174: [Balkan2007]Toponyms
Submit: 735 Solved: 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 complexity Lc(T).
Sample Input
7
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi
Sample Output
24
HINT
这题有毒啊，，
思路和算法没什么好说的，
就是建一棵字典树，统计好深度和个数，然后乘起来，取最大值
但是！！！
本蒟蒻一开始写的无限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 }
后来听别人说这题卡内存，
于是我换成了前向星储存，
然后，
无限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 }
然后只好参考别的大神的代码.......
编译速度就秒杀我的代码。。。
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 }
BZOJ 1174: [Balkan2007]Toponyms
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。