POJ3630 Phone List

思考：先对号码排序，然后一步步插入字典树。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

const int maxn = 100100; // maxn = 10010, Runtime error.
//3630	Accepted	3076K	266MS	C++	1194B	2014-04-03 22:15:46
vector<string> v;
int sz;
int ch[maxn+5][10];
int val[maxn+5];
bool mark;
int idx(char x) {
	return x-‘0‘;
}

void init() {
	sz = 1;
	mark = true;
	memset(ch[0], 0, sizeof(ch[0]));
	memset(val, 0, sizeof(val));
}


void Insert(char* str) {
	int len = strlen(str);
	int u = 0;
	for(int i = 0; i < len; i++) {
		int v = idx(str[i]);
		if(!ch[u][v]) {
			memset(ch[sz], 0, sizeof(ch[sz]));
			ch[u][v] = sz++;
		}
		u = ch[u][v];
		if(val[u]) {
            mark = false;
		}
	}
	val[u] = 1;
}


int main()
{
	int T, n;
	char str[12];
	scanf("%d", &T);
	getchar();
	while(T--) {
		v.clear();
		scanf("%d", &n);
		getchar();
		init();
		while(n--) {
			gets(str);
			string tmp = str;
			v.push_back(tmp);
		}
		sort(v.begin(), v.end());
		for(int i = 0; i < (int)v.size(); i++) {
            int len = v[i].length();
			v[i].copy(str, len);
			str[len] = ‘\0‘; // !!!.
			Insert(str);
		}
		if(mark) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

POJ3630 Phone List,布布扣,bubuko.com

POJ3630 Phone List

原文：http://blog.csdn.net/achiberx/article/details/22898425