博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 1174: [Balkan2007]Toponyms
阅读量:6330 次
发布时间:2019-06-22

本文共 2719 字,大约阅读时间需要 9 分钟。

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 735  Solved: 102
[][][]

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
2 #include
3 #include
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
RE

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

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

然后,

无限TLE,

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

 

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
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
TLE

 

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

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

1 #include 
2 #include
3 #include
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 }

 

转载地址:http://fsfoa.baihongyu.com/

你可能感兴趣的文章
我们需要真正的原创内容
查看>>
什么是你的核心竞争力之七弱点让你闪光
查看>>
关闭Windows Server的IE增强安全配置(ESC)
查看>>
SQL Server 2012笔记分享-35:配置客户端网络协议
查看>>
【VMC实验室】在QCloud上创建您的SQL Cluster(2)
查看>>
PHP流程控制的替代语法
查看>>
Exchange 2013 OAB不能下载的解决办法
查看>>
javascript 日期时间函数(经典+完善+实用)
查看>>
发发牢骚,觉得走c#这条路,不该太浮躁
查看>>
第十三章 别忘了我——SignalTap II Logic Analyzer
查看>>
教会你Linux Shell自动交互的三种方法
查看>>
在查询分析器中直接查询Excel中的数据
查看>>
cuteEditor 编码问题
查看>>
放羊挣钱娶媳妇生娃放羊挣钱娶媳妇生娃
查看>>
KMP代码实现
查看>>
Silverlight中服务通信方式的选择(WCF、Data Service、Ria Service)
查看>>
IE7漏洞蔓延 所有IE浏览器均存在高危漏洞
查看>>
OpenMP系列--初次体验多核并行编程
查看>>
校园一卡通系统发展概况及未来趋势
查看>>
在ubuntu下安装rails
查看>>