Codeforces 455B A Lot of Games 字典树上博弈-白红宇

Codeforces 455B A Lot of Games 字典树上博弈

阅读量：5856 次

发布时间：2019-06-19

本文共 1449 字，大约阅读时间需要 4 分钟。

题目链接：

题意：

给定n个字符串，k局游戏

对于每局游戏，2个玩家轮流给一个空串加入一个小写字母使得加完后的字符串不是n个字符串的前缀。

输家下一轮先手

问是先手必胜还是后手必胜

思路：

对于第一局游戏，若先手能到达必败态和必胜态，则先手会一直输到倒数第二局然后最后一局必胜

所以此时是first

若先手是必胜态或者是必败态，则是轮流赢。跟k的奇偶有关

#include 
     
      #include 
      
       #include
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            using namespace std;#define Word_Len 100500#define Sigma_size 26#define ll intstruct Trie{ ll ch[Word_Len][Sigma_size]; //Word_Len是字典树的节点数 若都是小写字母Sigma_size=26 ll sz ; //当前节点数 bool win[Word_Len], lost[Word_Len]; ll Newnode(){memset(ch[sz], 0, sizeof(ch[sz])); return sz++;} void init() //初始化字典树 { sz = 0; Newnode();}//初始化 ll idx(char c){return c-'a';} //字符串编号 void insert(char *s){ //把v数字加给 s单词最后一个字母 ll u = 0, len = strlen(s); for(ll i = 0; i < len; i++){ ll c = idx(s[i]); if(!ch[u][c]) //节点不存在就新建后附加 ch[u][c] = Newnode(); u = ch[u][c]; } //如今的u就是这个单词的最后一个位置 } void dfs(int u){ int cnt = 0; for(int i = 0; i < 26; i++)if(ch[u][i]) { cnt++; int v = ch[u][i]; dfs(v); if(win[v]==false)win[u] = true; if(lost[v]==false)lost[u] = true; } if(cnt==0) lost[u] = true; }};Trie ac;int n, k;void input(){ ac.init(); char s[100005]; while(n--) { scanf("%s", s); ac.insert(s); }}int main(){ int i, j; while(~scanf("%d %d",&n,&k)){ input(); ac.dfs(0); if(ac.lost[0]==false && ac.win[0]) puts(k&1 ?