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

题目链接：

题目大意：

给出n个字符串，进行k次游戏，每次游戏输家下次作为先手，游戏规则为每次放一个字母，导致当前构造的字符串是给定的任意一个字符串的前缀，不能操作时为输，赢得第k次比赛的人会取得最终的胜利，问两人都采取最优策略的情况下，谁会赢得比赛。

题目分析：

• 首先针对这种字符串的问题我们很容易会想到利用字典树来解决，方便多模式匹配。
• 然后我们就能想到，这其实就是一个在树上的博弈，那么我们就可以通过dp知道先手是否有必胜策略和必败策略。
• 这个树上的博弈很基础，就是对于某一个节点，如果当前是先手决策，那么只要它的儿子中有一个是必胜态，那么它就是必胜态，如果当前是后手决策，那么必须它的所有儿子都是必胜态，当前节点才是必胜态。
• 然后就是讨论这个组合游戏的玩法。
  • 首先如果先手没有必胜策略，那么后手有策略让先手输，而且先手一直在进行游戏，一直输到第k场。
  • 如果先手有必胜策略，也有必败策略，那么先手一定有策略让自己赢，因为他可以让自己一直树到第k-1场，然后在第k场取得胜利。
  • 如果先手有必胜策略，但是没有必败策略，那么后手就能决定先手的输赢，所以最后的胜负就只和k的奇偶性有关了。

    ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 100007using namespace std;int n,k,cc;char s[MAX];struct Node{    int branch[26];    Node ( )    {        memset ( branch , -1 , sizeof ( branch));    }    int win,lose;}p[MAX<<1];void add ( ){    int u = 0;    int m = strlen ( s );    for ( int i = 0 ; i < m ; i++ )    {        int x = s[i]-'a';        if ( p[u].branch[x] == -1 )            p[u].branch[x] = cc++;        u = p[u].branch[x];    }}void dfs ( int u , int d ){    int temp1,temp2;    temp1 = temp2 = (d&1)?0:1;    bool flag = false;    for ( int i = 0 ; i < 26 ; i++ )    {        int v = p[u].branch[i];        if ( v == -1 ) continue;        flag = true;        dfs ( v , d+1 );        if ( d&1 )        {            temp1 = temp1||p[v].win;            temp2 = temp2||p[v].lose;        }        else        {            temp1 = temp1&&p[v].win;            temp2 = temp2&&p[v].lose;        }    }    if ( !flag )    {        p[u].win = p[u].lose = 0;        if ( d&1 ) p[u].lose = 1;        else p[u].win = 1;    }    else    {        p[u].win = temp1;        p[u].lose = temp2;    }}int main ( ){    while ( ~scanf ( "%d%d" , &n , &k ))    {        cc = 1;        for ( int i = 0 ; i < n ; i++ )        {            scanf ( "%s" , s );            add ( );        }        dfs ( 0 , 1 );        int win = p[0].win;        int lose = p[0].lose;        if ( !win ) puts ( "Second");        else if ( lose ) puts ("First");        else        {            if ( k&1 ) puts ("First");            else puts ("Second");        }    }}
      
     
    
   

转载地址：http://fqvjn.baihongyu.com/