| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
C++静态建树!!
/*
考察了字典树的操作,刚开始我是动态建树的,好遗憾
竟然超时了,所以采取了静态建树的方式
注意输入顺序 假如有 110002 和 110
要考虑两种情况
110002
110
与
110
110002;
这两种情况 其他的就没傻了
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
int Count;
struct Trie
{
Trie * next[10];
bool flag;//标记是否是结尾
int cnt;
Trie()
{
for(int i = 0; i < 10; i++)
next[i] = NULL;
flag = false;
cnt = 0;
}
};
Trie memory[600050];
Trie * root = NULL;//根节点
bool Insert(char msg[])
{
int i = 0;
Trie * cur = root;
int k;
while(msg[i])
{
int k = msg[i] - '0';
if(cur->next[k] == NULL)
cur->next[k] = &memory[Count++];//new Trie();//创建新结点
else
{
cur->next[k]->cnt++;
if(cur->next[k]->flag)
return false;
}
cur = cur->next[k];
i++;
}
cur->flag = true;
if(cur->cnt>=1)
return false;
return true;
}
/*
void Delete(Trie * root)
{
for(int i = 0; i < 10; i ++ )
{
if(root->next[i] != NULL)
Delete(root->next[i]);
}
delete root;
}
*/
int t;
int n;
int main()
{
scanf("%d",&t);
char msg[12];
while(t--)
{
Count = 0;
scanf("%d",&n);
memset(memory,0,sizeof(memory));
root =&memory[Count++];// new Trie();
bool flag = true;
for(int i = 0; i < n; i++)
{
scanf("%s",msg);
if(flag)
flag = Insert(msg);
}
if(!flag)
printf("NO\n");
else
printf("YES\n");
// Delete(root);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator