HY 的惩罚 (Trie 树，博弈论)

【问题描述】

hy 抄题解又被老师抓住了,现在老师把他叫到了办公室。老师要 hy 和他玩一个游

戏。如果 hy 输了,老师就要把他开除信息组;

游戏分为 k 轮。在游戏开始之前,老师会将 n 个由英文字母组成的字符串放入箱子。

每局开始,字符串为空串,然后两人轮流在末尾追加字符,保证新的字符串为箱子中某

字符串的前缀,直到有一个人不能操作,不能操作的那个人就输掉当前的一轮。新一轮

由上一句输的人先手。最后一局赢的人获胜。

假定老师和 hy 都能采取最优的策略,且老师为了彰显自己的大度让 hy 先手,求 hy 能否

获胜。

【输入格式】

输入包括多组数据,输入以文字流结尾(EOF)为结束。

每组数据的第一行包含两个整数 n, k,分别表示放入箱子字符串的数量和游戏的轮

数。

接下来 n 行,每行一个字符串表示由英文字母组成的句子。

【输出格式】

每组数据第一行,输出 hy 是否能赢,若能赢输出”HY wins!“,否则输出”Teacher

wins!”。

【样例输入 1】

2 3

a

b

3 1

a

b

c

【样例输出 1】

HY wins!

HY wins!

【样例输入 2】

1 2

ab

【样例输出 2】

Teacher wins!【评测用例规模与约定】

对于 40%的评测用例,1≤n≤10,1≤k≤10 4 ;

对于 100%的评测用例,1≤n≤10 5 ,1≤k≤10 9 ,保证所有字符串总长度不超过 10 5 ,数据组

数不超过 10

Solution

先把所有的字符串插入 Trie 树，然后就是博弈论了。

博弈论分为三种情况:

1.若先手无必胜策略即先手必败则先手一直先手,最后一局后手胜;

2.若先手有必胜策略则下一局成后手,即为胜败交替,此时,最后一句的胜败决定于 k 的奇

偶性;

3.先手有必胜策略有必败策略,则先手前 k-1 局败,最后一局先手胜。

考虑 \(dp\) 转移，\(f[i]\) 代表当前节点是否能肯定赢，\(F[i]\) 代表当前节点是否能肯定输。

对于深度为偶数的节点，那么只要子节点中有任意一个满足，即可使当前 \(f[x]\) 或者 \(F[x]\) 为 \(1\) 。

因为此时为 HY 做决定的时间。
对于深度为奇数的节点，即此时由 Teacher 做决定，那么此时只有当其所有子节点都为肯定输或者肯定赢是才能计数。

然后按部就班转移即可。

Code

#include<bits/stdc++.h>

#define N 100001

#define ll long long

using namespace std;

int ch[N][26],cnt;

void insert(string s)

{

    int u=0,n=s.length();

    for(int i=0;i<n;i++)

    {

        if(!ch[u][s[i]-'a'])

        ch[u][s[i]-'a']=++cnt;

        u=ch[u][s[i]-'a'];

    } return;

}

int pd[N],Pd[N],sum[N];

void dfs(int x,int dep,int zm)

{

    sum[x]=1;

    for(int i=0;i<26;i++)

    if(ch[x][i])

    {

        dfs(ch[x][i],dep+1,i);

        sum[x]+=sum[ch[x][i]];

    }

    if(sum[x]==1)

	{

        if(dep%2==1)pd[x]=1;

		else Pd[x]=1;

    	return;

	}

	if(dep%2!=1)

    {

        for(int i=0;i<26;i++)

        if(ch[x][i])

        {

            pd[x]=max(pd[x],pd[ch[x][i]]);

            Pd[x]=max(Pd[x],Pd[ch[x][i]]);

        }

    }else

    {

        int pp=1,qq=1;

        for(int i=0;i<26;i++)

        if(ch[x][i])

        {

           if(!pd[ch[x][i]])pp=0;

           if(!Pd[ch[x][i]])qq=0;

        }pd[x]=pp,Pd[x]=qq;

    }

	return;

}

int n,k;

int main()

{

	freopen("amerce.in","r",stdin);

    freopen("amerce.out","w",stdout);

	while(scanf("%d",&n)!=EOF)

    {

        memset(pd,0,sizeof(pd));

		memset(Pd,0,sizeof(Pd));

        memset(sum,0,sizeof(sum));

        memset(ch,0,sizeof(ch));

        scanf("%d",&k); cnt=0;

        for(int i=1;i<=n;i++)

        {

            string s;

            cin>>s; insert(s);

        }

        dfs(0,0,0);

		if(pd[0]!=1){cout<<"Teacher wins!"<<endl;continue;}

		if(pd[0]==1&&Pd[0]==0)

		{

			if(k%2==1)cout<<"HY wins!"<<endl;

			else cout<<"Teacher wins!"<<endl;

			continue;

		}

		if(pd[0]==1&&Pd[0]==1)

		cout<<"HY wins!"<<endl;

	}

	return 0;

}

巴特西

HY 的惩罚 (Trie 树，博弈论)

Solution

Code

最新文章

热门文章