洛谷P2580 - 于是他錯誤的點名開始了（字典樹模闆題）

題目大意：

第一行輸入一個 n 表示有 n 個人，接下來輸入 n 個人的名字，再輸入一個q 表示有 q 次詢問，接下來輸入q行人名，對于每個詢問，如果該人名是第一次被點到，則輸出 ok ，如果之前點過了，則輸出repeat ，如果查無此人就輸出 wrong （均為大寫）。

解題思路：

Trie樹模闆題，根據輸入的串建樹，字典樹實質上也可以了解為26叉樹，然後詢問時隻需要看是否比對就可以了，如果第一次比對則比對到以後改一下cnt值，如果不存在（比對不到）就直接wrong就可以了。

Code（Trie樹做法）：

#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 50;
int ch[N * 32][26], cnt[N * 32], tot = 1;
void insert(string s)//建樹的過程
{
	int u = 0;
	for (int i = 0; i < s.size(); i ++)
	{
		int v = s[i] - 'a';
		if (!ch[u][v]) ch[u][v] = tot++;
		u = ch[u][v];
	}
	cnt[u] = 1;
}
void solve(string s)//在字典中檢索的過程
{
	int u = 0;
	for (int i = 0; i < s.size(); i ++)
	{
		int v = s[i] - 'a';
		if (! ch[u][v])  break;
		u = ch[u][v];
	}
	if (cnt[u] == 1)
	{
		puts("OK");
		cnt[u] = 2;
	}
	else if (cnt[u] == 2)
	    puts("REPEAT");
	else
		puts("WRONG");
}
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	string s;
	while (n--)
	{
		cin >> s;
		insert(s);
	}
	cin >> n;
	while (n--)
	{
		cin >> s;
		solve(s);
	}
	return 0;
}
           

這道題還有STL做法，即用map存一下，出現過的指派1，點過名的指派2，不存在的預設為0，用map映射一下也可以

Code（STL做法）：

#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 150;
map<string , int > mp;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string a;
		cin >> a;
		mp[a] = 1;
	}
	cin >> t;
	while (t--)
	{
		string a;
		cin >> a;
		if (mp[a] == 1)
		{
			mp[a] = 2;
			cout << "OK" << endl;
		}
		else if (mp[a] == 2)
			cout << "REPEAT" << endl;
		else
			cout << "WRONG" << endl;
	}
	return 0;
}