首页 > 代码库 > FAFU 1557

FAFU 1557

构建字典序,模拟二叉树建26叉树

 

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <time.h> 6 #include <ctype.h> 7 #include <string> 8 #include <queue> 9 #include <set>10 #include <map>11 #include <stack>12 #include <vector>13 #include <algorithm>14 #include <iostream>15 #define PI acos( -1.0 )16 using namespace std;17 typedef long long ll;18 19 const int NO = 1e5 + 5;20 char ch[NO];21 int n;22 struct ND23 {24     int win;25     ND *next[26];26 };27 28 int Solve( ND *tree )29 {30     for( int i = 0; i < 26; ++i )31     {32         if( tree->next[i] == NULL ) continue;33         if( Solve( tree->next[i] ) )34         {35             tree->win = 0;36             return 0;37         }38     }39     tree->win = 1;40     return 1;41 }42 43 int main()44 {45     int T;46     scanf( "%d", &T );47     while( T-- )48     {49         ND *tree;50         tree = new ND;51         for( int i = 0; i < 26; ++i )52             tree->next[i] = NULL;53         scanf( "%d", &n );54         for( int i = 0; i < n; ++i )55         {56             scanf( "%s", ch );57             ND *p = tree;58             int len = strlen( ch );59             for( int j = 0; j < len; ++j )60             {61                 int cur = ch[j] - a;62                 if( p->next[cur] == NULL )63                 {64                     p->next[cur] = new ND;65                     p = p->next[cur];66                     p->win = 0;67                     for( int t = 0; t < 26; ++t )68                         p->next[t] = NULL;69                 }70                 else p = p->next[cur];71             }72         }73         if( !Solve( tree ) ) puts( "First." );74         else puts( "Second." );75     }76     return 0;77 }
View Code

 

FAFU 1557