Trie的应用题目。

本题有两个难点了：

1 动态建立Trie会超时，须要静态建立数组，然后构造树

2 推断的时候注意两种情况： 1） Tire树有133，然后插入13333556的时候。2）插入顺序倒转过来的时候

改动一下标准Trie数的插入函数就能够了：

#include <stdio.h>

#include <string.h>

const int MAX_NODE = 100001;

const int MAX_WORD = 11;

const int ARR_SIZE = 10;

struct Node

{

	int n;

	Node *arr[ARR_SIZE];

};

void clearNode(Node *p)

{

	p->n = 0;

	for (int i = 0; i < ARR_SIZE; i++)

	{

		p->arr[i] = NULL;

	}

}

Node pool[MAX_NODE];

int poolId;

bool insertTrie(Node *trie, char nums[])

{

	Node *pCrawl = trie;

	int len = strlen(nums);

	for (int i = 0; i < len; i++)

	{

		int j = nums[i] - '0';

		//推断1： 情况： Trie有31199，插入311

		if (i + 1 == len && pCrawl->arr[j]) return false;//注意这个easy遗忘条件

		if (!pCrawl->arr[j])

		{

			pCrawl->arr[j] = &pool[poolId++];

			clearNode(pCrawl->arr[j]);

		}

		pCrawl = pCrawl->arr[j];

		if (pCrawl->n) return false;

	}

	for (int i = 0; i < ARR_SIZE; i++)

	{//推断2： 情况： Trie有31199，插入311，和推断1是一样的，删除一个也可。

if (pCrawl->arr[i]) return false;

	}

	pCrawl->n++;

	return true;

}

int main()

{

	int T, n;

	scanf("%d", &T);

	char word[MAX_WORD];

	Node *trie = &pool[0];

	while (T--)

	{

		clearNode(trie);

		poolId = 1;

		scanf("%d", &n);

		getchar();

		bool consistent = true;

		for (int i = 0; i < n; i++)

		{

			gets(word);

			if (consistent)

			{

				consistent = insertTrie(trie, word);

			}

		}

		if (consistent) puts("YES");

		else puts("NO");

	}

	return 0;

}