P7210 [COCI2020-2021#3] Vlak题解

· · 题解

分析

因为它要求必须是为喜欢的歌的前缀，那么我们就很容易想到建一个字典树记录所有歌。

在记录所有歌的同时，再用一个变量来表示这一段前缀是公共的，还是只有 Nina 或 Emilija 有。

例如样例数据：

2
aaa
bbb
3
aab
aba
bbb

建出的字典树如图:

这里的 1 表示的是 Nina 的前缀，2 表示的是 Emilija 的前缀，3 表示是公共前缀。

因为是回合制的游戏，所以字典树的相邻两层是由不同的人来选择的。

我们只需要在字典树上跑一个 dfs，每一次来判断上一层的人的选择是否可行。

即如果第 i 层的第 j 个字符，如果这个人可以通过选下一层的一个字符获胜，那么就说明另一个人不应该选择第 i 层的第 j 个字符。

反之如果这个人怎么选都不可以获胜，那么就说明另一个人可以通过第 i 层的第 j 个字符获胜。

可能有点绕，细节请看代码。

Code

#include<bits/stdc++.h>
#define N 200005
#define Mod 1000000007
#define int long long
#define For(i,j,k) for(int i=j;i<=k;++i)
#define FoR(i,j,k) for(int i=j;i<k;++i)
#define FOR(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
struct Node{
    int i,k;
};
int n,m,tot,ans;
Node ch[N<<1][30];
string s;

void make(int k){//建字典树 
    int len=s.size(),u=0;
    For(i,0,len-1){
        int c=s[i]-'a';
        if(!ch[u][c].i)ch[u][c].i=++tot;
        if(ch[u][c].k==0)ch[u][c].k=k;//如何没有出现过，那就只有这一个人 
        if(ch[u][c].k!=k)ch[u][c].k=3;//如何另一个人也有这个前缀，那这就是公共的 
        u=ch[u][c].i;
    }
    return;
}

bool dfs(int u,int p){
    int k=0;
    For(i,0,25)
    if(ch[u][i].i!=0){
        if(ch[u][i].k==3)k=dfs(ch[u][i].i,!p);
        if(ch[u][i].k==1&&p==0)return 0; 
        if(ch[u][i].k==2&&p==1)return 0;
        if(k)return 0;
        //如果p这个人可以获胜，即另一个人不应选u，返回0 
    }
    return 1;
    //如果p这个人怎么选都获胜不了，那么另一个人就可以选u，返回1 
}

signed main(){
    cin>>n;
    For(i,1,n){
        cin>>s;
        make(1);//1表示 Nina 
    }

    cin>>m;
    For(i,1,m){
        cin>>s;
        make(2);//2表示 Emilija 
    }

    For(i,0,25)
    if(ch[0][i].i!=0){
        ans=dfs(ch[0][i].i,1);
        //0表示 Nina 
        //1表示 Emilija 

        if(ans){//如何可以获胜就输出 Nina 
            cout<<"Nina";
            return 0;
        }
    }
    //如何 Nina怎么选都不能获胜，就输出 Emilija 
    cout<<"Emilija";
    return 0;
}