首页 > 代码库 > codeforcesB - A Lot of Games 博弈+dp

codeforcesB - A Lot of Games 博弈+dp

2024-07-17 02:47:19   232人阅读

题意：给你n个字符串，给你一个序列，两个人轮流取一个字符使得现有的字符串是n个字符串里面的前缀，最后谁不能取谁就输掉这局，但是他们要玩K局，谁在K局赢了就等于赢了一整场比赛。

解题思路：字典树找是否有 必输 或者 必赢 的策略，如果同时有必赢或者必输的策略，那必定是first赢，如果只有必赢，那只需要讨论K奇偶，如果只有必输，那一定是second

解题代码：

  1 // File Name: 1.cpp  2 // Author: darkdream  3 // Created Time: 2014年07月12日 星期六 23时30分16秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<climits> 25 #include<queue> 26  27 using namespace std; 28  29 struct node{ 30     int num; 31     int ok; 32     int ok1; 33     struct node *next[30]; 34 }; 35 struct node* newnode(){ 36    struct node * p = (node *)malloc(sizeof(node)); 37    for(int i =0 ;i < 30;i ++) 38        p->next[i] = NULL; 39    p->ok = 0; 40    p->num = 0  ; 41    return p ;  42 } 43 char str[100004]; 44 int len ; 45 void build(struct node * p, int i ) 46 { 47  48    int k = str[i] -‘a‘; 49    if(i == len ) 50        return ; 51   if(p->next[k] == NULL) 52    { 53      struct node * t  = newnode(); 54      t->num ++; 55      p->next[k] =  t;  56      build(p->next[k],i+1); 57    } 58   else { 59       p->next[k]->num += 1; 60       build(p->next[k],i+1); 61    } 62   int tok = 0 ; 63   int nok = 0 ; 64   int t1ok = 0 ; 65   for(int i= 0;i < 30 ;i ++) 66   { 67      if(p->next[i] != NULL) 68      { 69         nok = 1;  70         if(p->next[i]->ok == 0 ) 71             tok = 1; 72         if(p->next[i]->ok1 == 1) 73             t1ok = 1; 74      } 75   } 76   if(!nok || tok) 77       p->ok = 1; 78   else p->ok = 0; 79   if(nok) 80   { 81     if(t1ok) 82      p->ok1 = 0; 83     else p->ok1 =1; 84   }else{ 85      p->ok1 = 0; 86   } 87 } 88 int ans; 89 void find(struct node * p, int i ) 90 { 91    int k = str[i] -‘a‘; 92    if(i == len ) 93     { 94       ans = p->num ; 95       return ;  96     } 97    if(p->next[k] == NULL) 98    { 99       return ; 100    }else find(p->next[k],i+1);101 }102 int main(){103     int n , k;104 105     struct node * head = newnode();106     scanf("%d %d",&n,&k);107     while(n --){108          scanf("%s",str);109          len = strlen(str);110          build(head,0);111     }112    // printf("%d %d\n",head->ok,head->ok1);113     if(head->ok)114     {115       if(!head->ok1)116          printf("First\n");117       else{118         if(k % 2 == 1)119             printf("First\n");120         else printf("Second\n");121       }122     }else{123        printf("Second\n");  124     }125 return 0;126 }
View Code


联系
我们