【luogu P2580 于是他错误的点名开始了】 题解

题目链接：https://www.luogu.org/problemnew/show/P2580

我真的永远都爱stl

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100001;
map<string,int> a;
int n, m, num[maxn];
string s;
int main()
{
	memset(num,-1,sizeof(num));
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
	{
		cin>>s;
		a[s] = i;
		num[a[s]]++;
	}
	scanf("%d",&m);
	for(int i = 1; i <= m; i++)
	{
		cin>>s;
		if(num[a[s]] ==-1)
		{
			printf("WRONG
");
			continue;//记得continue一下，要不然重复点错名的话会出错
		}
		num[a[s]]++;
		if(num[a[s]] == 1)
		{
			printf("OK
");
		}
		if(num[a[s]] > 1)
		{
			printf("REPEAT
");
		}
	}
	return 0;
}

后来我发现，trie也很棒棒哦qaq

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 500001;
char s[50];
int n, m, v[maxn], trie[maxn][26], opt, tot; 
void insert()
{
	int len = strlen(s);
	int root = 0;
	for(int i = 0; i < len; i++)
	{
		int id = s[i] - 'a';
		if(!trie[root][id])
			trie[root][id]=++tot;
		root = trie[root][id];	
	}
	v[root] = 1;
}
int find()
{
	int len = strlen(s);
	int root = 0;
	for(int i = 0; s[i]; i++)
	{
		int now = s[i] - 'a';
		if(trie[root][now] == 0) return false;
		root = trie[root][now];
	}
	if(v[root] == 1)
	{
		v[root] = 2;
		return 1;
	}
	else
	return 2;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		cin>>s;
		insert();
	}
	cin>>m;
	for(int i = 1; i <= m; i++)
	{
		cin>>s;
		opt = find();
		if(opt == 0) printf("WRONG
");
		if(opt == 1) printf("OK
");
		if(opt == 2) printf("REPEAT
");
	}
}