首页 > 代码库 > BZOJ1174: [Balkan2007]Toponyms
BZOJ1174: [Balkan2007]Toponyms
1174: [Balkan2007]Toponyms
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 117 Solved: 16
[Submit][Status]
Description
给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.
Input
第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 总输入不超过20000字符
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
Source
题解：
写了个trie树果然RE不停，trie树貌似是最明显的做法吧，还有什么神犇的做法呢？
挖坑待填
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 50000026 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline int read()48 49 {50 51 int x=0,f=1;char ch=getchar();52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57 return x*f;58 59 }60 int n,tot,f[maxn],t[maxn][53];61 ll ans;62 63 int main()64 65 {66 67 freopen("input.txt","r",stdin);68 69 freopen("output.txt","w",stdout);70 71 n=read();72 for1(i,n)73 {74 int now=0,len=0;char ch;75 while((ch=getchar())!=‘\n‘)76 {77 len++;78 int x;79 if(ch==‘ ‘)x=52;else if(ch<=‘z‘&&ch>=‘a‘)x=ch-‘a‘;else x=ch-‘A‘+26;80 if(!t[now][x])t[now][x]=++tot;81 now=t[now][x];82 f[now]++;83 ans=max(ans,(ll)f[now]*(ll)len);84 }85 }86 printf("%lld\n",ans);87 88 return 0;89 90 }
BZOJ1174: [Balkan2007]Toponyms
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。