018（Phone List）（字典树）

题目：http://ybt.ssoier.cn:8088/problem_show.php?pid=1471

题目思路：

这不就是一个超级明显的字典树嘛

字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串(但不仅限于字符串)，所以经常。。。。。。

以单词 will，wet，colorful，colors举例做树

它从一个根节点开始（这边根节点统一为空，因为我们要存的是形形色色百十个字符串，强行做一个根节点显然不太合适）

根节点上分裂出一个字母，这个字母是某个单词的打头字母

第一个单词 will，它的打头字母是w，那么，根节点上出来一个w

紧接着，分裂出来的字母继续向下分裂，第二个字母，亦或者第n个字母就都出来了

那就形成了这样一个格局：根节点的一个孩子是 w，w 的一个孩子是 i，i 的一个孩子是 l，l 还有一个孩子 l 。

接着把下一个单词 wet 打进来，发现，打头字母全是 w

“那你总不可能把他们放在一起去吧！” “对啊” ”。。。。。。”

是的，在字典树里是有公共节点的可能的，而如果公共节点的的下一个节点还相同，那就还是公共的

自此，一个字典树就这么被建立起来了

等等，貌似能直接表示树的结构现在还没出生呢

针对这个，聪明的祖先们想到了用数组模拟的办法

	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0			7																				1
1					5				2
2												3
3												4
4
5																				6
6
7															8
8												9
9															10
10																		11
11						12													15
12																					13
13												14
14

每一个行就是一层节点，这层节点向哪里分叉，是什么由纵列表示

不为零，就代表有东西，而这有了的东西又联系着下一个节点

妙哉妙哉

叨叨了这么久字典树，终于要回到正轨了

其实就是在字典树上加了两个判断

如果前面找的东西出来一个0，代表“路走斜了”，此时改变判断，告诉程序这里可能对不上

如果结尾处对上了，那就是短串与长串对上了，也要跟程序知会一声

但是，f1 和 f2 两个只要其中一个目标达成即可

如果是结尾对上了，那么上面必定对上，如果上面对不上它就不会回到结尾而是会另起一横行

如果上面对上了，结尾对不上，不排除先进短串后进长串的可能性，所以也是可以滴

综上，代码如下

#include<bits/stdc++.h>

using namespace std;

int len,root,tot,trie[1000000][10],f[100000];

int t,n,q,f1,f2;

string s;

//常规操作

int insert(){

	len=s.size();

	root=0;

	for(int i=0;i<len;i++){//建树加判断

	    int id=s[i]-'0';//先把纵列搞出来

	    if(!trie[root][id]){//如果对不上了

			trie[root][id]=++tot;//另起一行

			f1=1;//知会一声

		}

	    root=trie[root][id];//更新子节点

	    if(f[root]==1){//结尾能对上了

			f2=1;//也要知会一声

		}

	}

	f[root]=1;//为以后的“结尾能对上”铺路

	return f1==0||f2==1;//两个条件达成一个即可

	return 0;

}

int main(){

	cin>>t;

	while(t--){

		cin>>n;

		memset(trie,0,sizeof(trie));

		memset(f,0,sizeof(f));

		q=0;tot=0;

		//记得归零

		while(n--){

			cin>>s;

			f1=0;f2=0;

			//记得归零

			if(insert()==1){

				q=1;

			}

		}

		if(q==1){//满足要求了

			cout<<"NO"<<endl;

			//按他的想法输出

		}

		else{//不满足

			cout<<"YES"<<endl;

			//也要按照它的想法输出

			//这题的NO和YES反过来了

			//大家注意一下

		}

	}

	return 0;

}

题目总结：背熟字典树模板
还有就是后面的“两个条件达成一个即可”要捋清楚

巴特西

018（Phone List）（字典树）

最新文章

热门文章

	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0			7																				1
1					5				2
2												3
3												4
4
5																				6
6
7															8
8												9
9															10
10																		11
11						12													15
12																					13
13												14
14

	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0			7																				1
1					5				2
2												3
3												4
4
5																				6
6
7															8
8												9
9															10
10																		11
11						12													15
12																					13
13												14
14

	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0			7																				1
1					5				2
2												3
3												4
4
5																				6
6
7															8
8												9
9															10
10																		11
11						12													15
12																					13
13												14
14