P7210 [COCI2020-2021#3] Vlak 题解

STARSczyy · 2023-11-12 16:17:45 · 题解

思路：

模拟赛时看了题目后，第一时间想到字典树，因为每一个节点可以表示一个状态，然后再赛事画出样例 1 的图（有点抽象）。如图，黑色的树表示人物以 N 开头的人能够选择的，红色表示人物以 E 开头的人能够选择的,绿色的横向划分表示每一个分岔该哪个人物选择，蓝色表示每一个节点的赢者。当前节点表示的状态只能有一个玩家能够抵达时，那么一定事唯一一个能够抵达该状态的玩家赢；否则就看操作到当前状态的玩家是否能够走到使自己必胜的一个子状态。具体的实现步骤深搜即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int init_(){
    srand(time(0));
//  freopen("vlak.in","r",stdin);
//  freopen("vlak.out","w",stdout);
    return 0;
}
const int maxn=2e5+10,mod=1e9+7,init=init_();
inline int read(){
    int c,w=0,n=0;
    while((c=getchar())<'0'||'9'<c) w=c=='-';
    do n=n*10+c-'0';while('0'<=(c=getchar())&&c<='9');
    return w?-n:n;
}
int write(int n){
    if(n<0) putchar('-'),n=-n;
    if(n>9) write(n/10);
    putchar(n%10+'0');
    return n;
}

int tot=1;
struct node{int p[28],sub/*使用状压表示能够到达的玩家*/;}trie[maxn];//字典树
int nw(int &x){
    if(!x) x=++tot;
    return x;
}
int n,m;
char s[maxn];
int dfs(int x,int flag){
    if(trie[x].sub==1) return 0;
    if(trie[x].sub==2) return 1;//返回唯一能够到达此节点的玩家
    for(int i=0;i<26;++i) if(trie[x].p[i])
        if(dfs(trie[x].p[i],!flag)==flag/*是否能够走到一个子状态使自己必赢*/)
            return flag;
    return !flag;
}

signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        memset(s,0,sizeof s);
        scanf("%s",s+1);
        trie[1].sub|=1;
        for(int i=1,now=1;s[i];++i)
            now=nw(trie[now].p[s[i]-'a']),trie[now].sub|=1;//插入
    }
    m=read();
    for(int i=1;i<=m;++i){
        memset(s,0,sizeof s);
        scanf("%s",s+1);
        trie[1].sub|=2;
        for(int i=1,now=1;s[i];++i)
            now=nw(trie[now].p[s[i]-'a']),trie[now].sub|=2;
    }//同上
    int flag=dfs(1,0);
    if(!flag) puts("Nina");
    else puts("Emilija");
    return 0;
}