自动搬运

查看原文

来自洛谷，原作者为

	determination 敬不完美的明天。

搬运于2025-08-24 22:27:42，当前版本为作者最后更新于2023-11-12 17:20:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析题目，看到前缀，联想到字典树。看到输赢，联想到博弈。

我们建好字典树，并且开数组存储这个字符串是谁的前缀。现在我们设计状态。

显然，叶子结点是必败态，然后 dfs 往下跑，找到叶子返回，剩下的节点直接跑即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e18
#define endl '\n'
#define debug puts("IAKIOI")
int t[200010][30],tot,flag[200010][30][2];
bool SG[200010][2];
void insert(string s,int op)
{
	int node=0;
	for ( int i = 0 ; i < s.size() ; i++ )
	{
		SG[node][op]=1;
		flag[node][s[i]-'a'][op]=1;
		if(t[node][s[i]-'a']==0)
		{
			t[node][s[i]-'a']=++tot;
		}
		node=t[node][s[i]-'a'];
	}
	SG[node][op]=0;
}
string str[2]={"Emilija","Nina"};
void dp(int x,int op)
{
//	printf("dp %d %d:\n",x,op);
	if(SG[x][op]==0)
	{
//		printf("return 0\n");
		return;
	}
	for ( int i = 0 ; i < 26 ; i++ )
	{
		if(!flag[x][i][op])
		{
			continue;
		}
		dp(t[x][i],op^1);
		if(SG[t[x][i]][op^1]==0)
		{
//			printf("=1\n");
			SG[x][op]=1;
			return;
		}
	}
//	printf("=0\n");
	SG[x][op]=0;
}
signed main()
{
	freopen("vlak.in","r",stdin);
	freopen("vlak.out","w",stdout);
	int n,m;
	cin >> n ;
	for ( int i = 1 ; i <= n ; i++ )
	{
		string s;
		cin >> s;
		insert(s,0);
	}
	cin >> m;
	for ( int i = 1 ; i <= m ; i++ )
	{
		string s;
		cin >> s;
		insert(s,1);
	}
	dp(0,0);
	cout << str[SG[0][0]];
	return 0;
}