首页 > 代码库 > 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 }
FAFU 1557
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。