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

HDU1671能过,,,poj这就过不了了。。。。

Posted by lvweihua at 2017-08-21 10:48:22 on Problem 3630
#include<cstdio>
#include<cstring>
int N;
struct Node {
	char c;
	int fre, isend;         //fre是出现频率,isend为是否是最后一个号码,只要最后一个号码的频率>1,就出现重复的
	struct Node *son, *bro; //儿子和兄弟结点
	Node() { son = bro = NULL; isend = fre = 0; c = '\0'; }
}*Tire;
bool Create(Node* &root) {
	int M;
	root = new Node;
	scanf("%d", &M);
	getchar();
	char s[11];
	bool flag = false;
	for (int i = 0; i<M; i++) {
		scanf("%s", s);
		if (flag)continue;   //已经找到重复的,后面的就不用再判断
		Node* tmp = root;
		int l = strlen(s);
		for (int j = 0; j<l; j++) {
            if(flag)break;
			Node* p = tmp->son;
			if (p == NULL) {
				p = new Node;
				p->c = s[j];
				tmp->son = p;
			}
			else {
				Node* pre = p;
				while (p != NULL&&p->c != s[j]) { pre = p; p = p->bro; }
				if (p == NULL) {
					p = new Node;
					p->c = s[j];
					pre->bro = p;
				}
			}
			tmp = p;
			p->fre++;
			if (j == l - 1)tmp->isend = 1;  //先判断重复的
			if (tmp->isend&&tmp->fre>1) {
				flag = true;  //有重复的
			}
		}
	}
	return flag;
}
void Del(Node* &root) {
	if (root == NULL)return;
	Del(root->son);
	Del(root->bro);
	root->fre = root->isend = 0;
	delete root;
	root->son = root->bro = NULL;
}
int main() {
	scanf("%d", &N);
	while (N--) {
		if (Create(Tire))puts("NO");
		else puts("YES");
	//	Del(Tire);
	}
	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