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 #include2 #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
后来听别人说这题卡内存,
于是我换成了前向星储存,
然后,
无限TLE,
加了各种常数优化还是无限TLE
1 #include2 #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
然后只好参考别的大神的代码.......
编译速度就秒杀我的代码。。。
1 #include2 #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 }