【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\n");

			continue;//记得continue一下，要不然重复点错名的话会出错

		}

		num[a[s]]++;

		if(num[a[s]] == 1)

		{

			printf("OK\n");

		}

		if(num[a[s]] > 1)

		{

			printf("REPEAT\n");

		}

	}

	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\n");

		if(opt == 1) printf("OK\n");

		if(opt == 2) printf("REPEAT\n");

	}

}