BZOJ 1174: [Balkan2007]Toponyms
2018-06-18 04:00:23来源:未知 阅读 ()
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
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi
Sample Output
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:【Zigbee】终端设备入网过程
下一篇:C语言实现斐波那契数列(非递归)
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- HihoCoder 1174 2020-02-15
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash