TOP

BZOJ 1174: [Balkan2007]Toponyms(一)
2017-10-11 15:42:34 】 浏览:10088
Tags:BZOJ 1174: Balkan2007 Toponyms

Time Limit: 10 Sec  Memory Limit: 128 MB
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

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 }
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 E
17 {
18     int u,v,nxt;
19 }edge[MAXN];
20 int head[MAXN];
21 int num=1;
22 struct node
23 {
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  
		
BZOJ 1174: [Balkan2007]Toponyms(一) https://www.cppentry.com/bencandy.php?fid=45&id=139561

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇H5前端之sass的入门 下一篇数组的注意点