BZOJ 1174: [Balkan2007]Toponyms

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 }

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

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

然后,

无限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 }

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

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

 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏偏前端工程师的驿站

基础野:细说无符号整数

Brief                                 本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

2046
来自专栏静默虚空的博客

排序四 希尔排序

要点 希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。 该方法因DL.Shell于1959年提出而得名。 希尔...

2549
来自专栏前端杂谈

前端算法-基本排序算法比较

36613
来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

3175
来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

6105
来自专栏五分钟学算法

每天一算:Odd Even Linked List

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

1063
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2262
来自专栏数据小魔方

左右用R右手Python9——字符串合并与拆分

在文本处理和数据清洗阶段,对字符串或者字符型变量进行分割、提取或者合并虽然谈不上什么高频需求,但是往往也对很重要的。 接下来跟大家大致盘点一下在R语言与Pyh...

3465
来自专栏章鱼的慢慢技术路

解密回文——栈

1473
来自专栏Bingo的深度学习杂货店

Q155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element ...

2776

扫码关注云+社区

领取腾讯云代金券