首页 > 代码库 > codeforces 455B A Lot of Games（博弈，字典树）

codeforces 455B A Lot of Games（博弈，字典树）

2024-07-17 11:45:07   221人阅读

题目大意：给定n，表示字符串集合。给定k，表示进行了k次游戏，然后是n个字符串。每局开始，字符串为空串，然后两人轮流在末尾追加字符，保证新的字符串为集合中某字符串的前缀，不能操作者输，新一轮由上一句输的人先手。

解题思路：首先对字符集合建立字典树，然后根据博弈的必胜必败性质搜索出先手的决策状态，可决定胜败3，只能胜利2，只能失败1，不可掌控（即对手可决定胜败）0。
对于状态3，为必胜，可以采用前K-1场败，然后保证第K场自己先手，取必胜方案。
对于状态2，无论则们走都是赢的话，肯定是两个人轮流胜局，所以判断K的奇偶性。
对于状态1和0，必败，因为一直输，一直先手。

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6  7 const int maxn=1000010; 8  9 struct Trie //字典树查询字符串10 {11     int ch[maxn][26];12     int sz; //结点总数13     void clear(){sz=1;memset(ch[0],-1,sizeof(ch[0]));}14     int Num(char ch){ return ch-‘a‘;}15     void insert(char *s)16     {17         int len=strlen(s),u=0;18         for(int i=0;i<len;i++)19         {20             int c=Num(s[i]);21             if(ch[u][c]==-1)22             {23                 memset(ch[sz],-1,sizeof(ch[sz]));24                 ch[u][c]=sz++;25             }26             u=ch[u][c];27         }28     }29 }trie;30 31 int solve(int d)32 {33     int ans=0;34     int flag=1;35     for(int i=0;i<26;i++)36     {37         if(trie.ch[d][i] != -1)38         {39             flag=0;40             ans|=solve(trie.ch[d][i]);41         }42     }43     if(flag)44         ans=1;45     return 3-ans;46 }47 48 int main()49 {50     int n,m;char s[maxn];51     while(~scanf("%d%d",&n,&m))52     {53         trie.clear();54         while(n--)55         {56             scanf("%s",s);trie.insert(s);57         }58         int ans = 3 - solve(0);59         if(ans==3) printf("First\n");60         else if(ans==1||ans==0) printf("Second\n");61         else 62         {63             if(m&1) printf("First\n");64             else printf("Second\n");65         }66     }67     return 0;68 }

 


联系
我们