csu 1987: 绚丽的手链-白红宇

csu 1987: 绚丽的手链

阅读量：7089 次

发布时间：2019-06-28

本文共 2397 字，大约阅读时间需要 7 分钟。

Time Limit: 6 Sec Memory Limit: 512 Mb Submitted: 13 Solved: 2

Description

小X的妹妹马上就要过生日了，作为哥哥，小X打算买一些手链送给妹妹。

采购完礼物回到家的小X惊奇的发现：每条手链虽然只由两种颜色的珠子串成，但是它们有一个神奇的效果，那就是当多条手链同时放在一起时，会散发出绚丽夺目的光芒。光芒的绚丽程度有强有弱，这取决于手链的最长公共前缀的长度和手链数目的乘积。例如000,001,0011三串手链放在一起会发出绚丽程度为6的光芒。

显然如果将所有手链都送给妹妹，效果未必最好，因此他决定从中挑选一些送给妹妹，使得能够达到最绚丽的效果。你能帮助他吗？

Input

第一行一个整数 T (≤ 20) 表示数据组数。

每组数据第一行一个整数 n(≤ 50000) 代表字符串的数量。接下来N行，每行为一个仅由0,1组成的字符串代表小X购买的手链，手链的最大长度为200。

Output

对于每组数据输出一行，表示小X经过挑选后送给妹妹的手链所能产生的最大绚丽程度。

Sample Input

4400000001101010102010100101010101010101101001010101010101030101010101010000100010100101010101010000100010000101010101010000100010105010101010101000010100100101001010101010101010000101001101010101000001010101010110101000101010101101010100010101010101001

Sample Output

Hint

Source

2017年暑期集训校队选拔

Author

徐戍

题解：

这个题目是真的不好做心累

6次超时还有几次其他的错误

我的第一想法就是构建字典树节点记录下着是几个字符串的公共子串（这个不难）然后就是一次遍历字典树求出答案结果超时

然后我发现建树之后其实不用去遍历了我们在建树的时候就可以得到答案结果还是超时

下面的超时的那个代码各位大佬谁会优化的告诉一下我怎么优化 0.0 （后面有AC代码）

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
           5 #include 
           
             6 #include 
            
              7 using namespace std; 8 char s[205]; 9 int ans;10 struct Trie11 {12 int num;13 struct Trie *nxt[2];14 Trie()15 {16 num=0;17 for(int i=0; i<2; i++)18 {19 nxt[i]=NULL;20 }21 }22 };23 24 void Trie_Inser(Trie *p,char s[])25 {26 int i=0;27 Trie *q=p;28 while(s[i])29 {30 int nx=s[i]-'0';31 if(q->nxt[nx]==NULL)32 {33 q->nxt[nx]=new Trie;34 }35 i++;36 q=q->nxt[nx];37 q->num++;38 ans=max(ans,(q->num)*i);39 }40 }41 int main()42 {43 int n,m;44 scanf("%d",&n);45 while(n--)46 {47 ans=0;48 Trie *p=new Trie;49 scanf("%d",&m);50 getchar();51 while(m--)52 {53 gets(s);54 Trie_Inser(p,s);55 }56 57 printf("%d\n",ans);58 59 }60 return 0;61 }

在我觉得动态字典树的做法没有救了之后我尝试了一下动态字典树的说的简单点就是使用数组去模拟

1 #include 
       
         2 #include 
        
          3 #include 
         
           4  5 using namespace std; 6 int pos,ans; 7 struct node 8 { 9     int num;10     int child[2];11 }tree[10000010];12 13 int add()14 {15     pos++;16     tree[pos].num=0;17     for(int i=0;i<2;i++)18     {19         tree[pos].child[i]=-1;20     }21     return pos;22 }23 24 int inser(char* str)25 {26     int post=0;27     int tmp=0;28     int len=strlen(str);29     for(int i=0;i

转载于:https://www.cnblogs.com/52why/p/7460121.html

你可能感兴趣的文章

《Spring攻略（第2版）》——1.11　用XML配置自动装配Bean