HDU1305+字典树

为什么暴力过不了这题。。。

AC代码

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 struct tree{
 5     int lev;
 6     tree* next[2];
 7 };
 8 tree root;
 9 
10 void build( char str[] ){
11     int len = strlen( str );
12     tree *p = &root;
13     tree *tmp;
14     for( int i=0;i<len;i++ ){
15         int id = str[i]-'0';
16         if( p->next[ id ]==NULL ){
17             tmp = ( tree* )malloc( sizeof( root ) );
18             tmp->lev = 1;
19             for( int j=0;j<2;j++ ){
20                 tmp->next[ j ] = NULL;
21             }
22             p->next[ id ] = tmp;
23             p = p->next[ id ];
24         }
25         else {
26             p->next[ id ]->lev++;
27             p = p->next[ id ];
28         }
29     }
30 }
31 int find( char str[] ){
32     int len = strlen( str );
33     tree *p = &root;
34     for( int i=0;i<len;i++ ){
35         int id = str[i]-'0';
36         if( p->next[ id ]==NULL ){
37             return -1;
38         }
39         p = p->next[ id ];
40         if( i==len-1 ) {
41             if( p->lev==1 ) return -1;
42             else return 1;
43         }
44     }
45 //    return 1;
46 }
47 int main(){
48     char s[ 1005 ][ 24 ];
49     int ca = 1;
50     while( scanf("%s",s[0])!=EOF ){
51         int cnt = 0;
52         build( s[0] );
53         cnt++;
54         while( scanf("%s",s[cnt])!=EOF ){
55             if( s[cnt][0]=='9' ) break;
56             build( s[cnt] );
57             cnt++;
58         }
59         int f = -1;
60         for( int i=0;i<cnt;i++ ){
61             if( f==1 ) break;
62             if( find( s[i] )==1 ) {
63                 f = 1;
64                 break;
65             }
66         }
67         if( f==-1 ) printf("Set %d is immediately decodable\n",ca++);
68         else printf("Set %d is not immediately decodable\n",ca++);
69     }
70     return 0;
71 }
72     
73     
74     
75     
76     
77     
78     
79     
80     
81

暴力代码：

View Code

 1 /*
 2 字符串
 3 */
 4 #include<stdio.h>
 5 #include<string.h>
 6 #include<stdlib.h>
 7 #include<algorithm>
 8 #include<iostream>
 9 #include<queue>
10 #include<vector>
11 #include<map>
12 #include<math.h>
13 typedef long long ll;
14 //typedef __int64 int64;
15 const int maxn = 1005;
16 const int maxm = 1005;
17 const int inf = 0x7FFFFFFF;
18 const double pi = acos(-1.0);
19 const double eps = 1e-8;
20 using namespace std;
21 
22 char a[ maxn ][ 240 ];
23 
24 int main(){
25     char tmp[ 240 ];
26     int ca = 1;
27     while( scanf("%s",tmp)!=EOF ){
28         int cnt = 0;
29         memset( a,'\0',sizeof(a) );
30         strcpy( a[ cnt ],tmp );
31         cnt++;
32         while( scanf("%s",tmp)!=EOF ){
33             if( tmp[0]=='9' ) break;
34             strcpy( a[ cnt ],tmp );
35             cnt++;
36         }
37         int flag = -1;
38         for( int i=0;i<cnt;i++ ){
39             if( flag==1 ) break;
40             for( int j=0;j<cnt;j++ ){
41                 if( i==j ) continue;
42                 if( flag==1 ) break;
43                 int len = strlen( a[j] );
44                 for( int k = 1;k<len;k++ ){
45                     memset( tmp,'\0',sizeof( tmp ) );
46                     for( int kk = 0;kk<=k;kk++ )
47                         tmp[kk] = a[j][kk];
48                     tmp[k+1]='\0';
49                     if( strcmp(tmp,a[i])==0 ){
50                         flag = 1;
51                         break;
52                     }
53                 }
54             }
55         }
56         if( flag==1 ) printf("Set %d is not immediately decodable\n",ca);
57         else printf("Set %d is immediately decodable\n",ca);
58         ca++;
59     }
60     return 0;
61 }

keep moving...