Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这道题不要动态开辟空间,贴个代码,造福后人

Posted by 200842128 at 2011-11-25 16:33:02 on Problem 3630
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator