第四周 9.20-9.26

竟然忘记开文章了Orz

9.20

北京OL。

9.21

补题。

9.22

好久没敲题了。希望学校办事效率高些。

早点安定下来。早些找回节奏感。

拖了很久的Trie。

本来想找个板就好。后来发现Trie很多变。

几乎都要在附加信息上进行修改。所以更多的是理解而不是套板。

紫薯板。

 1 const int maxnode=20000,sigma_size=26;
 2 
 3 struct Trie
 4 {
 5     int ch[maxnode][sigma_size];
 6     int val[maxnode];
 7     int sz;
 8     Trie() {sz=1; memset(ch[0],0,sizeof(ch[0]));}
 9     int idx(char c) {return c-'a';}
10 
11     void insert(char *s,int v)
12     {
13         int u=0,n=strlen(s);
14         for(int i=0;i<n;i++)
15         {
16             int c=idx(s[i]);
17             if(!ch[u][c])
18             {
19                 memset(ch[sz],0,sizeof(ch[sz]));
20                 val[sz]=0;
21                 ch[u][c]=sz++;
22             }
23             u=ch[u][c];
24         }
25         val[u]=v;
26     }
27 };

Aguin

POJ 2001 Shortest Prefixes

板子题。

记录每个前缀出现次数。找到次数为1的即可。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxnode=20000,sigma_size=26;
 6 
 7 struct Trie
 8 {
 9     int ch[maxnode][sigma_size];
10     int val[maxnode];
11     int sz;
12     Trie() {sz=1; memset(ch[0],0,sizeof(ch[0]));}
13     int idx(char c) {return c-'a';}
14 
15     void insert(char *s)
16     {
17         int u=0,n=strlen(s);
18         for(int i=0;i<n;i++)
19         {
20             int c=idx(s[i]);
21             if(!ch[u][c])
22             {
23                 memset(ch[sz],0,sizeof(ch[sz]));
24                 val[sz]=0;
25                 ch[u][c]=sz++;
26             }
27             u=ch[u][c];
28             val[u]++;
29         }
30     }
31     
32     int search(char *s)
33     {
34         int u=0,n=strlen(s);
35         printf("%s ",s);
36         for(int i=0;i<n;i++)
37         {
38             putchar(s[i]);
39             int c=idx(s[i]);
40             u=ch[u][c];
41             if(val[u]==1) break;
42         }
43         puts("");
44     }
45 } trie;
46 
47 int main(void)
48 {
49     char s[2000][30];
50     int cnt=0;
51     while(~scanf("%s",s[++cnt])) trie.insert(s[cnt]);
52     for(int i=1;i<=cnt;i++) trie.search(s[i]);
53     return 0;
54 }

Aguin

HDU 1075 What Are You Talking About

附加信息改为字符串。随手开爆M。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxnode=10000000,sigma_size=26;
 6 char E[]="END",a[30],b[30],str[4000];
 7 
 8 struct Trie
 9 {
10     int ch[maxnode][sigma_size];
11     char tr[maxnode][15];
12     int sz;
13     Trie()
14     {
15         sz=1;
16         memset(ch[0],0,sizeof(ch[0]));
17         memset(tr,0,sizeof(tr));
18     }
19     int idx(char c) {return c-'a';}
20 
21     void insert(char *s,char *r)
22     {
23         int u=0,n=strlen(s);
24         for(int i=0;i<n;i++)
25         {
26             int c=idx(s[i]);
27             if(!ch[u][c])
28             {
29                 memset(ch[sz],0,sizeof(ch[sz]));
30                 ch[u][c]=sz++;
31             }
32             u=ch[u][c];
33         }
34         strcpy(tr[u],r);
35     }
36 
37     bool search(char *s)
38     {
39         int u=0,n=strlen(s);
40         for(int i=0;i<n;i++)
41         {
42             int c=idx(s[i]);
43             if(!ch[u][c]) return false;
44             u=ch[u][c];
45         }
46         if(!strlen(tr[u])) return false;
47         printf("%s",tr[u]);
48         return true;
49     }
50 } trie;
51 
52 bool is_alp(char c)
53 {
54     return c>='a'&&c<='z';
55 }
56 
57 int main(void)
58 {
59     gets(str);
60     while(~scanf("%s",a))
61     {
62         if(!strcmp(E,a)) break;
63         scanf("%s",b);
64         trie.insert(b,a);
65     }
66     getchar();
67     gets(str);
68     while(1)
69     {
70         gets(str);
71         if(!strcmp(E,str)) break;
72         int len=strlen(str);
73         for(int i=0;i<len;i++)
74         {
75             if(!is_alp(str[i])) {putchar(str[i]); continue;}
76             char w[30]; int j;
77             for(j=0;i+j<len&&is_alp(str[i+j]);j++) w[j]=str[i+j];
78             w[j]=0; i+=j-1;
79             if(trie.search(w)) continue;
80             printf("%s",w);
81         }
82         puts("");
83     }
84     return 0;
85 }

Aguin

9.23

HDU 1004 Let the Balloon Rise

水题。纯练字典树。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxnode=20000,sigma_size=26;
 6 char s[1005][20];
 7 
 8 struct Trie
 9 {
10     int ch[maxnode][sigma_size];
11     int val[maxnode];
12     int sz;
13 
14     Trie()
15     {
16         sz=1;
17         memset(ch[0],0,sizeof(ch[0]));
18         memset(val,0,sizeof(val));
19     }
20 
21     void clear(void)
22     {
23         sz=1;
24         memset(ch[0],0,sizeof(ch[0]));
25         memset(val,0,sizeof(val));
26     }
27 
28     int idx(char c) {return c-'a';}
29 
30     void insert(char *s)
31     {
32         int u=0,n=strlen(s);
33         for(int i=0;i<n;i++)
34         {
35             int c=idx(s[i]);
36             if(!ch[u][c])
37             {
38                 memset(ch[sz],0,sizeof(ch[sz]));
39                 ch[u][c]=sz++;
40             }
41             u=ch[u][c];
42         }
43         val[u]++;
44     }
45 
46     int search(char *s)
47     {
48         int u=0,n=strlen(s);
49         for(int i=0;i<n;i++)
50         {
51             int c=idx(s[i]);
52             u=ch[u][c];
53         }
54         return val[u];
55     }
56 } t;
57 
58 int main(void)
59 {
60     int N;
61     while(~scanf("%d",&N)&&N)
62     {
63         t.clear();
64         for(int i=0;i<N;i++)
65         {
66             scanf("%s",s[i]);
67             t.insert(s[i]);
68         }
69         int m=0,pos;
70         for(int i=0;i<N;i++)
71         {
72             int tmp=t.search(s[i]);
73             if(tmp>m) {m=tmp; pos=i;}
74         }
75         printf("%s
",s[pos]);
76     }
77     return 0;
78 }

Aguin

HDU 1251 统计难题

水水字典树。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxnode=5000000,sigma_size=26;
 6 
 7 struct Trie
 8 {
 9     int ch[maxnode][sigma_size];
10     int val[maxnode];
11     int sz;
12 
13     Trie()
14     {
15         sz=1;
16         memset(ch[0],0,sizeof(ch[0]));
17         memset(val,0,sizeof(val));
18     }
19 
20     int idx(char c) {return c-'a';}
21 
22     void insert(char *s)
23     {
24         int u=0,n=strlen(s);
25         for(int i=0;i<n;i++)
26         {
27             int c=idx(s[i]);
28             if(!ch[u][c])
29             {
30                 memset(ch[sz],0,sizeof(ch[sz]));
31                 ch[u][c]=sz++;
32             }
33             u=ch[u][c];
34             val[u]++;
35         }
36     }
37 
38     int search(char *s)
39     {
40         int u=0,n=strlen(s);
41         for(int i=0;i<n;i++)
42         {
43             int c=idx(s[i]);
44             if(!ch[u][c]) return 0;
45             u=ch[u][c];
46         }
47         return val[u];
48     }
49 } trie;
50 
51 int main(void)
52 {
53     char s[20];
54     while(1)
55     {
56         gets(s);
57         if(s[0]==0) break;
58         trie.insert(s);
59     }
60     while(~scanf("%s",s)) printf("%d
",trie.search(s));
61     return 0;
62 }

Aguin

9.24

HDU 1800 Flying to the Mars

这题用字典树做也是sbsb。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 const int maxnode=100000,sigma_size=10;
 7 
 8 struct Trie
 9 {
10     int ch[maxnode][sigma_size];
11     int val[maxnode];
12     int sz;
13 
14     Trie()
15     {
16         sz=1;
17         memset(ch[0],0,sizeof(ch[0]));
18         memset(val,0,sizeof(val));
19     }
20 
21     void clear(void)
22     {
23         sz=1;
24         memset(ch[0],0,sizeof(ch[0]));
25         memset(val,0,sizeof(val));
26     }
27 
28     int idx(char c) {return c-'0';}
29 
30     void insert(char *s)
31     {
32         int u=0,n=strlen(s);
33         for(int i=0;i<n;i++)
34         {
35             int c=idx(s[i]);
36             if(!ch[u][c])
37             {
38                 memset(ch[sz],0,sizeof(ch[sz]));
39                 ch[u][c]=sz++;
40             }
41             u=ch[u][c];
42         }
43         val[u]++;
44     }
45 
46     int search(void)
47     {
48         int ret=0;
49         for(int i=1;i<sz;i++) ret=max(ret,val[i]);
50         return ret;
51     }
52 } t;
53 
54 int main(void)
55 {
56     int N;
57     while(~scanf("%d",&N))
58     {
59         t.clear();
60         for(int i=0;i<N;i++)
61         {
62             char s[40];
63             scanf("%s",s);
64             for(int j=0;;j++) if(s[j]!='0'||j==strlen(s)-1)
65             {
66                 t.insert(s+j); break;
67             }
68 
69         }
70         printf("%d
",t.search());
71     }
72     return 0;
73 }

Aguin

HDU 1671 Phone List

水题wa了好多发。。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 const int maxnode=200000,sigma_size=10;
 7 
 8 struct Trie
 9 {
10     int ch[maxnode][sigma_size];
11     int val[maxnode];
12     int sz;
13 
14     Trie()
15     {
16         sz=1;
17         memset(ch[0],0,sizeof(ch[0]));
18         memset(val,0,sizeof(val));
19     }
20 
21     void clear(void)
22     {
23         sz=1;
24         memset(ch[0],0,sizeof(ch[0]));
25         memset(val,0,sizeof(val));
26     }
27 
28     int idx(char c) {return c-'0';}
29 
30     bool insert(char *s)
31     {
32         int u=0,n=strlen(s),ok=0;
33         for(int i=0;i<n;i++)
34         {
35             int c=idx(s[i]);
36             if(!ch[u][c])
37             {
38                 ok=1;
39                 memset(ch[sz],0,sizeof(ch[sz]));
40                 ch[u][c]=sz++;
41             }
42             u=ch[u][c];
43             if(val[u]) return false;
44         }
45         val[u]=1;
46         return ok;
47     }
48 } t;
49 
50 int main(void)
51 {
52     int T; cin>>T;
53     while(T--)
54     {
55         t.clear();
56         int N; scanf("%d",&N);
57         bool ok=1;
58         for(int i=0;i<N;i++)
59         {
60             char s[40];
61             scanf("%s",s);
62             if(!t.insert(s)) ok=0;
63         }
64         puts(ok?"YES":"NO");
65     }
66     return 0;
67 }

Aguin

HDU 1247 Hat’s Words

水果。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 const int maxnode=5000000,sigma_size=26;
 7 char s[50000][100];
 8 
 9 struct Trie
10 {
11     int ch[maxnode][sigma_size];
12     bool val[maxnode];
13     int sz;
14 
15     Trie()
16     {
17         sz=1;
18         memset(ch[0],0,sizeof(ch[0]));
19         memset(val,0,sizeof(val));
20     }
21 
22     int idx(char c) {return c-'a';}
23 
24     void insert(char *s)
25     {
26         int u=0,n=strlen(s);
27         for(int i=0;i<n;i++)
28         {
29             int c=idx(s[i]);
30             if(!ch[u][c])
31             {
32                 memset(ch[sz],0,sizeof(ch[sz]));
33                 ch[u][c]=sz++;
34             }
35             u=ch[u][c];
36         }
37         val[u]=1;
38     }
39 
40     bool search(char *s)
41     {
42         int u=0,n=strlen(s);
43         for(int i=0;i<n;i++)
44         {
45             int c=idx(s[i]);
46             if(!ch[u][c]) return false;
47             u=ch[u][c];
48         }
49         return val[u];
50     }
51 
52     bool hat(char * s)
53     {
54         int u=0,n=strlen(s);
55         for(int i=0;i<n-1;i++)
56         {
57             int c=idx(s[i]);
58             u=ch[u][c];
59             if(val[u]&&search(s+i+1)) return true;
60         }
61         return false;
62     }
63 } t;
64 
65 int main(void)
66 {
67     int cnt=0;
68     while(~scanf("%s",s[cnt++])) t.insert(s[cnt-1]);
69     for(int i=0;i<cnt;i++) if(t.hat(s[i])) printf("%s
",s[i]);
70     return 0;
71 }

Aguin

UVA 1401 Remember the Word

白薯题。dp还是弱弱弱。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 const int maxnode=1000000,sigma_size=26;
 7 const int mod=20071027;
 8 char o[300005],s[200];
 9 int l,dp[300005];
10 
11 struct Trie
12 {
13     int ch[maxnode][sigma_size];
14     bool val[maxnode];
15     int sz;
16 
17     Trie()
18     {
19         sz=1;
20         memset(ch[0],0,sizeof(ch[0]));
21         memset(val,0,sizeof(val));
22     }
23 
24     void clear()
25     {
26         sz=1;
27         memset(ch[0],0,sizeof(ch[0]));
28         memset(val,0,sizeof(val));
29     }
30 
31     int idx(char c) {return c-'a';}
32 
33     void insert(char *s)
34     {
35         int u=0,n=strlen(s);
36         for(int i=0;i<n;i++)
37         {
38             int c=idx(s[i]);
39             if(!ch[u][c])
40             {
41                 memset(ch[sz],0,sizeof(ch[sz]));
42                 ch[u][c]=sz++;
43             }
44             u=ch[u][c];
45         }
46         val[u]=1;
47     }
48 
49     void solve(void)
50     {
51         dp[0]=1;
52         for(int i=0;i<l;i++)
53         {
54             int u=0;
55             for(int j=1;i+j<=l;j++)
56             {
57                 int c=idx(o[i+j]);
58                 if(!ch[u][c]) break;
59                 u=ch[u][c];
60                 if(val[u])
61                 {
62                     dp[i+j]+=dp[i];
63                     if(dp[i+j]>=mod) dp[i+j]-=mod;
64                 }
65             }
66         }
67     }
68 } trie;
69 
70 int main(void)
71 {
72     int kase=0;
73     while(~scanf("%s",o+1))
74     {
75         trie.clear();
76         l=strlen(o+1);
77         memset(dp,0,sizeof(dp));
78         int n;scanf("%d",&n);
79         for(int i=0;i<n;i++)
80         {
81             scanf("%s",s);
82             trie.insert(s);
83         }
84         trie.solve();
85         printf("Case %d: %d
",++kase,dp[l]);
86     }
87     return 0;
88 }

Aguin

9.25

重温exkmp。

9.26

HDU 4333 Revolving Digits

exkmp。通过把自身复制一遍。可以O(2n)搞定自身循环匹配。

同时扫到第一个Next[i]>=len (i>0)的位置是循环节长度。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 # define maxn 100010
 7 int m,Next[maxn*2];
 8 char b[maxn*2];
 9 
10 void getNext(void)
11 {
12     int P=1,j; Next[0]=m;
13     for(int i=Next[1]=0;i<m-1&&b[i]==b[i+1];) Next[1]=++i;
14     for(int i=2;i<m;i++)
15     {
16         if(Next[i-P]+i<Next[P]+P) Next[i]=Next[i-P];
17         else
18         {
19             j=max(Next[P]+P-i,0);
20             while(i+j<m&&b[j]==b[j+i]) j++;
21             Next[i]=j; P=i;
22         }
23     }
24     return;
25 }
26 
27 int main(void)
28 {
29     int T; cin>>T;
30     for(int kase=1;kase<=T;kase++)
31     {
32         scanf("%s",b);
33         int n=strlen(b); m=n<<1;
34         for(int i=n;i<m;i++) b[i]=b[i-n];
35         getNext();
36         int l=0,g=0;
37         for(int i=1;i<n;i++)
38         {
39             if(Next[i]>=n) break;
40             if(b[i+Next[i]]<b[Next[i]]) l++;
41             else g++;
42         }
43         printf("Case %d: %d 1 %d
",kase,l,g);
44     }
45     return 0;
46 }

Aguin

魔都ol出线了感动哭。