hdu 1671 Phone List 字典树

//	hdu 1671 Phone List 字典树
//
// 题目大意:
//
// 有一些电话号码的字符串长度最多是10,问是否存在字符串是其它字符串的前缀
//
//
// 解题思路:
//
// 字典树,先插入第一个字符串,然后依照查询,插入的方式进行訪问,发现了之后
// 就不用再进行字典树的操作了
//
//
// 感悟:
//
// 题目意思非常清楚,我在细节方面思考了非常久,插入方面在每一个串的根节点的时候加
// 上一个val值标记。查询的时候先看是否有标记,有则直接返回true。没找到返回
// false。找到了返回true即可了,还是非常easy的~COME ON ! FIGHTING~ #include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std; const int MAX_N = 300000; int n; struct Trie {
int ch[MAX_N][11];
int sz;
int val[MAX_N]; int idx(char c){
return c - '0';
} void init(){
sz = 1;
memset(ch[0],0,sizeof(ch[0]));
val[0] = 0;
} void insert(char *s,int v){
int n = strlen(s);
int u = 0; for (int i=0;i<n;i++){
int c = idx(s[i]);
if (!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] = v; } bool query(char *s){
int n = strlen(s);
int u = 0; for (int i=0;i<n;i++){
int c = idx(s[i]);
//cout << s[i]; if (val[u]){
return true;
} if (!ch[u][c]){
return false;
} u = ch[u][c];
}
return true;
} }trie; void input(){
trie.init();
scanf("%d",&n);
char s[20];
scanf("%s",s);
trie.insert(s,1); bool flag = false;
for (int i=2;i<=n;i++){
scanf("%s",s);
if (flag)
continue;
flag = trie.query(s);
//cout << endl;
trie.insert(s,i);
//cout << i << endl;
}
if (flag)
puts("NO");
else
puts("YES");
} int main(){
int t;
//freopen("1.txt","r",stdin);
scanf("%d",&t);
while(t--){
input();
}
}
上一篇:simple shell


下一篇:[ACM] hdu 1671 Phone List (字典树)