博弈树¶
例题 #1 清一色¶
Alice 和 Bob 在纸上做游戏，Alice 是先手。
刚开始，纸上有一个长度为 0 的单词（换句话说，就是空的）。
在一个回合里，当前行动的玩家将一个字母加入到当前单词的末尾。下一个回合，另一个玩家行动。
玩家们选择字母时必须遵循这样的原则：每一次添加字母**后**的单词必须是该玩家最喜爱歌曲中某个单词的前缀。如果某个玩家无法继续执行它的回合，那么她就输了。
如果两位玩家选择的策略都是最佳的，请判断谁是赢家。
Input Format
第一行包含一个正整数 n，表示 Alice 最喜爱歌曲中的单词数量。
接下来的 n 行，每一行输入 Alice 最喜爱歌曲中的一个单词。
接下来的一行包含一个正整数 m，表示 Bob 最喜爱歌曲中的单词数量。
接下来的 m 行，每一行输入 Bob 最喜爱歌曲中的一个单词。
Output Format
一行一个字符串，如果 Alice 获胜就输出 Nina，否则输出 Emilija
对于 100% 的数据，单词长度总和不超过 2×105。
单词仅包含小写字母。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 5e5 + 5;
const int INF = 1e3;
const int M = 1e7;
const int MOD = 1e9 + 7;
string s;
struct trie{
struct node{
int s[27];
int cnt;
int sz;
}t[N];
int tot=1;
void insert(string s){
int x=1;
for(auto c:s){
if(!t[x].s[c-'a'])t[x].s[c-'a']=++tot,t[x].sz++;
x=t[x].s[c-'a'];
t[x].cnt++;
// dbg(s,x);
// ell;
}
}
}ta,tb;
int f[N];//1:alice win 2: lose
void dfs(int a,itn b,int op,string s){
int cnta=0,cntb=0;
int cnt1=0,cnt2=0;
for(int i=0;i<26;i++){
if(op==0){
if(!ta.t[ta.t[a].s[i]].cnt)continue;
cnta++;
if(tb.t[tb.t[b].s[i]].sz==0){f[a]=1;return ;}
dfs(ta.t[a].s[i],tb.t[b].s[i],op^1,s+(char)(i+'a'));
if(f[ta.t[a].s[i]]==1){f[a]=1;return ;}
}else{
if(!tb.t[tb.t[b].s[i]].cnt)continue;
cntb++;
if(tb.t[tb.t[b].s[i]].sz==0){f[a]=2;return ;}
dfs(ta.t[a].s[i],tb.t[b].s[i],op^1,s+(char)(i+'a'));
if(f[ta.t[a].s[i]]==2){f[a]=2;return ;}
}
if(f[ta.t[a].s[i]]==1)cnt1++;
if(f[ta.t[a].s[i]]==2)cnt2++;
}
if(op==0&&cnt1)f[a]=1;
if(op==0&&cnta==cnt2)f[a]=2;
if(op==1&&cnt2)f[a]=2;
if(op==1&&cntb==cnt1)f[a]=1;
// dbg(s,f[a]);
// ell;
}
void solve(){
int n=rd;
for(int i=1;i<=n;i++){
cin>>s;
ta.insert(s);
}
int m=rd;
for(int i=1;i<=m;i++){
cin>>s;
tb.insert(s);
}
dfs(1,1,0,"");
// for(int i=1;i<=7;i++)cdbg(f[i]);
if(f[1]==1)puts("Nina");
else puts("Emilija");
}
signed main() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}