| ||||||||||
| 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 | |||||||||
这道题不要动态开辟空间,贴个代码,造福后人#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int Branch = 10;
const int Max = 100010;
bool result;
struct Trie
{
bool tail;
Trie * next[Branch];
}; //字典树结点
struct Phone
{
char num[11];
int len;
friend bool operator <(const Phone &a, const Phone &b)
{
return a.len < b.len;
}
}; //电话号码结构体
Phone p[Max]; //存所有的电话号码
Trie tree[Max * 10]; //字典树
Trie *alloc; // = tree;
void insert(Trie *&root, Phone cur)
{
Trie * p = root;
for(int i=0; i<cur.len; i++)
{
int seq = cur.num[i] - '0';
if(p->next[seq] == NULL)
{
p->next[seq] = alloc ++;
memset(p->next[seq], 0, sizeof(Trie));
}
else
{
if(p->next[seq]->tail) result = false;
}
p = p->next[seq];
}
p->tail = true;
}
int main()
{
int cases, n;
Trie * root;//字典树根节点
cin >> cases;
while(cases --)
{
alloc = tree; //分配指针指向数组首地址
root = alloc ++;
memset(root, 0, sizeof(Trie));
scanf("%d", &n);
for(int i=0; i<n; i++)
{
scanf("%s", p[i].num);
p[i].len = strlen(p[i].num);
}
sort(p, p+n);
result = true;
for(int i=0; i<n && result; i++)
{
insert(root, p[i]);
}
if(result) cout << "YES" << endl;
else cout << "NO" << endl;
}
system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator