发表更新算法设计

POJ 1847 Tram（单源最短路径）

题意：轨道网，有若干转换器，每个转换器都和其他若干转换器相连，转换器初始指向第一个与其相连的转换器。问要到达终点需要最少转换多少次？

思路：可以用dijkstra单源最短路来做，把轨道网看做有向图（因为1第一个指向2，2的第一个不一定指向1），当前转换器处始指向的那个转换器之间的路径权值为0，其他路径权值为1，求一次起点到终点的最短路，结果就是最少转换次数，注意可能没有路径，这时要输出-1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
poj    1847
264K	0MS
*/
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 105
#define MAX_INT 2147483647

using namespace std;

int n,gra[MAXN][MAXN],dist[MAXN],sta,fin;

void init()
{
	memset(gra , -1 , sizeof(gra));
	cin>>n>>sta>>fin;
	for(int i = 1;i <= n;i ++)
	{
		int m,t;
		cin>>m>>t;
		gra[i][t] = 0;
		for(int j = 1;j < m;j ++)
		{
			scanf("%d",&t);
			gra[i][t] = 1;
		}
	}
	memset(dist , 1 , sizeof(dist));//这样可以整体赋一个较大的值 
	dist[sta] = 0;
}

int dijkstra()
{
	bool mark[MAXN] = {false};
	for(int i = 1;i <= n;i ++)
	{
		int Min = MAX_INT,tj;
		for(int j = 1;j <= n;j ++)
			if(dist[j] < Min && !mark[j])
			{
				Min = dist[j];
				tj = j;
			}
		mark[tj] = true;
		for(int j = 1;j <= n;j ++)
			if(!mark[j] && gra[tj][j] > -1)
				dist[j] = min(dist[j] , dist[tj] + gra[tj][j]);
	}
	if(dist[fin] == dist[0])
		return -1;
	return dist[fin];
}

int main()
{
	init();
	cout<<dijkstra()<<endl;
	return 0;
}
发表更新算法设计

POJ 3268 Silver Cow Party（dijkstra单源最短路）

裸 dijkstra
思路：以x为源点，求到其他点的最短路，之后把邻接矩阵转置，再求一次x源

点的最短路，这样就一次是来的，一次是走的，相加迭代最大值即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
poj    3268
8108K	47MS
*/
#include<cstdio>
#include<iostream>

#define MAXN 1005
#define MAX_INT 2147483647

using namespace std;

int gra_in[MAXN][MAXN],gra_out[MAXN][MAXN],n,m,p,dist_in[MAXN],dist_out[MAXN];

void init()
{
	cin>>n>>m>>p;
	for(int i = 1;i <= m;i ++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		gra_out[a][b] = c;
		gra_in[b][a] = c;
	}
}

void dijkstra(int gra[MAXN][MAXN] , int dist[MAXN])
{
	bool mark[MAXN] = {false};
	for(int i = 1;i <= n;i ++)
		dist[i] = MAX_INT;
	dist[p] = 0;
	for(int i = 1;i <= n;i ++)
	{
		int Min = MAX_INT,tj;
		for(int j = 1;j <= n;j ++)
		{
			if(mark[j])
				continue;
			if(Min > dist[j])
			{
				Min = dist[j];
				tj = j;
			}
		}
		mark[tj] = true;
		for(int j = 1;j <= n;j ++)
		{
			if(mark[j] || !gra[tj][j])
				continue;
			dist[j] = min(dist[j] , dist[tj] + gra[tj][j]);
		}
	}
}

int main()
{
	init();
	dijkstra(gra_in , dist_in);
	dijkstra(gra_out , dist_out);
	int Max = 0;
	for(int i = 1;i <= n;i ++)
		Max = max(Max , dist_in[i] + dist_out[i]);
	cout<<Max<<endl;
	return 0;
}
发表更新算法设计

POJ 2001 Shortest Prefixes 字典树

题意很好理解就不说了，然后这道题其实不用字典树更简单，但是为了练习trie树就写了一下，1A了哈哈，再对比了一下讨论区的大神代码，发现我还是写复杂了。。。

思路：

想到利用字典树，继承字典树原有机制，从底端叶子向上找，每条路径最先找

到的分叉点再往下（从叶子找上来的这条路）一个字符即为所求（特殊情况，

如果节点处单词已结束，那么就输出整个单词好了），也就是从上往下找到的

第一个不是路径重合（has_same_path = true）的情况或者是is_word =

true的情况，用遍历二叉树的方法遍历整个树得到所有前缀。
判断has_same_path的情况很简单，如果当前tmp->next[num]不为空，则

一定has_same_path
，至于pos则是为了让答案按顺序输出用的

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*
poj      2001
11152K	16MS
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

#define MAXN 1005

using namespace std;

struct node
{
	node *next[26];
	bool has_same_path;
	bool is_word;
	int pos;
	node()
	{
		memset(next , 0 , sizeof(next));
		has_same_path = is_word = false;
		pos = -1;
	}
}trie[100005];
int trie_num;

struct out
{
	char s[21];
	int pos;
	out()
	{
		memset(s , 0 , sizeof(s));
		pos = -1;
	}
}ans[MAXN];

int n = 1,id;
char str[MAXN][21],tmp_str[21];

bool cmp(out a , out b)
{
	return a.pos < b.pos;
}

void insert(char *s , int pos)//插入单词 
{
	int len = strlen(s);
	node *now = &trie[0];
	for(int i = 0;i < len;i ++)
	{
		int num = s[i] - 'a';
		if(!now->next[num])
			now->next[num] = &trie[++trie_num];
		else
			now->next[num]->has_same_path = true;
		now = now->next[num];
		if(now->pos == -1)
			now->pos = pos;
	}
	now->is_word = true;
	now->pos = pos;
}

void cons(node *now , int k)//构造答案 
{
	if(!now->has_same_path || now->is_word)
	{
		tmp_str[k] = 0;
		memcpy(ans[++id].s , tmp_str , k);
		ans[id].pos = now->pos;
		now->is_word = false;//防止回溯时再次计入
		if(!now->has_same_path)
			return ;
	}
	for(int i = 0;i < 26;i ++)
	{
		if(now->next[i])
		{
			tmp_str[k] = i + 'a';
			cons(now->next[i] , k + 1);
		}
	}
}

int main()
{
	while(scanf("%s" , str[n]) != EOF)
	{
		insert(str[n] , n);
		n ++;
	}
	n --;
	trie[0].has_same_path = true;
	cons(&trie[0] , 0);
	sort(ans + 1 , ans + n + 1 , cmp);
	for(int i = 1;i <= n;i ++)
		printf("%s %s\n",str[i] , ans[i].s);
	return 0;
}

其实空间没必要开那么大，为了省事就乱开了

发表更新算法设计

POJ 1328 Radar Installation 贪心

version 1

从右到左排序，每次都尽可能的选打击范围内最右边的点安装雷达（由于浮点，所以不要一棒子打死的判断是大是小，给出一个精度范围，一开始范围给打了就WA），拿这个雷达去覆盖其他点，最后雷达总数一定是最少的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
poj    1328
264K	16MS
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>

#define MAXN 1005

using namespace std;
struct node
{
	double x,y,pos;
	node()
	{
		x = y = pos =  -1.0;
	}
}per[MAXN];
int n;
double m;

bool cmp(node a,node b)
{
	return a.pos< b.pos;
}

bool init()
{
	bool flag = true;
	for(int i = 1;i <= n;i ++)
	{
		scanf("%lf %lf",&per[i].x , &per[i].y);
		if(per[i].y > m)
			flag = false;
		per[i].pos = per[i].x + sqrt(m * m - per[i].y * per[i].y);
	}
	if(!flag)
		return false;
	sort(per + 1 , per + n + 1 , cmp);
	return true;
}

int calc()
{
	int cnt = 0,id = 1;
	while(id <= n)
	{
		double now = per[id].pos;
		cnt ++;
		while(id <= n && 
			(fabs(per[id].x - now) * (per[id].x - now) + per[id].y * per[id].y - m * m) <= 0.001)
		{
			id ++;
		}
	}
	return cnt ;
}

int main()
{
	int cnt = 1;
	while(cin>>n>>m && (n || m))
	{
		if(!init())
		{
			printf("Case %d: -1\n",cnt);
			cnt ++;
			continue;
		}
		printf("Case %d: %d\n",cnt , calc());
		cnt ++;
	}
	return 0;
}

version 2

找到以每个岛为圆心的圆与x轴左右交点形成一个区间，按左端点关键字升序排序后，用右端点去覆盖之后的点（如果遇到更小的右端点应该把目前的点更新），遇到不能覆盖的就雷达数目+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
poj     1328
272K	32MS
*/
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>

#define MAXN 1005

using namespace std;

struct node
{
	double x,y,lp,rp;
	node()
	{
		x = y = lp = rp =  -1.0;
	}
}per[MAXN];
int n;
double m;

bool cmp(node a,node b)
{
	return a.lp < b.lp;
}

bool init()
{
	bool flag = true;
	for(int i = 1;i <= n;i ++)
	{
		scanf("%lf %lf",&per[i].x , &per[i].y);
		if(per[i].y > m)
			flag = false;
		per[i].lp = per[i].x - sqrt(m * m - per[i].y * per[i].y);
		per[i].rp = per[i].x + sqrt(m * m - per[i].y * per[i].y);
	}
	if(!flag)
		return false;
	sort(per + 1 , per + n + 1 , cmp);
	return true;
}

int calc()
{
	int cnt = 1,id = 1;
	bool mark[MAXN] = {false};
	double now = per[1].rp;
	for(int i = 1;i <= n;i ++)
	{
		if(per[i].rp < now)
			now = per[i].rp;
		if(per[i].lp > now)
		{
			cnt ++;
			now = per[i].rp;
		}
	}
	return cnt;
}

int main()
{
	int cnt = 1;
	while(cin>>n>>m && (n || m))
	{
		if(!init())
		{
			printf("Case %d: -1\n",cnt);
			cnt ++;
			continue;
		}
		printf("Case %d: %d\n",cnt , calc());
		cnt ++;
	}
	return 0;
}
发表更新算法设计

POJ 1080 Human Gene Functions（动态规划）

一开始用的DFS，无限TLE，贴丑代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//version 1 TLE
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX_INT 2147483647
#define MAXN 105

using namespace std;

int Map[5][5] = {
				{0,-3,-4,-2,-1},
				{-3,5,-1,-2,-1},
				{-4,-1,5,-3,-2},
				{-2,-2,-3,5,-2},
				{-1,-1,-2,-2,5},
				};
int seq1[MAXN],seq2[MAXN],Max,n1,n2;

int ref(char c)
{
	switch (c)
	{
		case 'A':
			return 1;
		case 'C':
			return 2;
		case 'G':
			return 3;
		case 'T':
			return 4;
	}
}

void dfs(int id1,int id2,int sum)
{
	if(id2 <= n2 + 1)
	{
		if(id2 == n2 + 1)
		{
			for(int i = id1;i <= n1;i ++)
				sum += Map[seq1[i]][0];
			Max = max(Max,sum);
			return ;
		}
		int limi = n1 - n2 + id2,tsum = sum;
		for(int i = id1;i <= limi;i ++)
		{
			if(i > id1)
				tsum += Map[seq1[i-1]][0];
			dfs(i + 1 , id2 + 1 , tsum + Map[seq1[i]][seq2[id2]]);
		}
	}
}

int main()
{
	freopen("./1080.in" , "r" , stdin);
	int T,i,j;
	char c;
	cin>>T;
	while(T --)
	{
		scanf("%d%c",&n1,&c);
		for(i = 1;i <= n1;i ++)
		{
			scanf("%c",&c);
			seq1[i] = ref(c);
		}
		scanf("%d%c",&n2,&c);
		for(i = 1;i <= n2;i ++)
		{
			scanf("%c",&c);
			seq2[i] = ref(c);
		}
		if(n1 < n2)
		{
			for(int i = 1;i <= n1;i ++)
				swap(seq1[i] , seq2[i]);
			for(int i = n1 + 1;i <= n2;i ++)
				seq1[i] = seq2[i];
			swap(n1 , n2);
		}
		Max = -MAX_INT;
		dfs(1,1,0);
		cout<<Max<<endl;
	}
	return 0;
}

之后冥思苦想了好久，两个序列，开始没有想到变形的LCS（最长公共子序列），只是试着写状态转移方程，最后就写成了那个dp[i][j] = max(dp[i-1][j-1] `,dp[i-1][j]`````,dp[i][j-1])的样子，这时一看才明白这是LCS思想，但是一开始确实是瞎写的，可能碰巧了吧=。=，最后注意这种情况:dp[0][x]，当一个序列之前都用0补上的话，在循环过程中是没办法得到结果的，只能预先处理，切记！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
poj   1080
268K	0MS	
*/
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 105
#define MAX_INT 2147483647

using namespace std;

int Map[5][5] = {
				{0,-3,-4,-2,-1},
				{-3,5,-1,-2,-1},
				{-4,-1,5,-3,-2},
				{-2,-2,-3,5,-2},
				{-1,-1,-2,-2,5},
				};
int seq1[MAXN],seq2[MAXN],dp[MAXN][MAXN],n1,n2;

int ref(char c)
{
	switch (c)
	{
		case 'A':
			return 1;
		case 'C':
			return 2;
		case 'G':
			return 3;
		case 'T':
			return 4;
	}
}

int calc()
{
	memset(dp , 0 , sizeof(dp));
	for(int i = 1;i <= n1;i ++)
		dp[i][0] = dp[i-1][0] + Map[seq1[i]][0];
	for(int i = 1;i <= n2;i ++)
		dp[0][i] = dp[0][i-1] + Map[0][seq2[i]];
	for(int i = 1;i <= n1;i ++)
		for(int j = 1;j <= n2;j ++)
			dp[i][j] = max(dp[i-1][j-1] + Map[seq1[i]][seq2[j]] ,
				max(dp[i-1][j] + Map[seq1[i]][0] , dp[i][j-1] + Map[0][seq2[j]]) );
	return dp[n1][n2];
}

int main()
{
	int T,i,j;
	char c;
	cin>>T;
	while(T --)
	{
		scanf("%d%c",&n1,&c);
		for(i = 1;i <= n1;i ++)
		{
			scanf("%c",&c);
			seq1[i] = ref(c);
		}
		scanf("%d%c",&n2,&c);
		for(i = 1;i <= n2;i ++)
		{
			scanf("%c",&c);
			seq2[i] = ref(c);
		}
		cout<<calc()<<endl;
	}
	return 0;
}
发表更新算法设计

POJ 1789 Truck History

Prim 最小生成树模板，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
poj 1789
16004K	344MS
*/
#include<cstdio>
#include<iostream>
#include<cstring>

#define MAXN 2005

using namespace std;

int n,gra[MAXN][MAXN],low_cost[MAXN];
char str[MAXN][8];

void init()
{
	for(int i = 1;i <= n;i ++)
	{
		for(int j = i + 1;j <= n;j ++)
		{
			int cnt = 0;
			for(int k = 0;k < 7;k ++)
				cnt += (str[i][k] != str[j][k]);
			gra[i][j] = gra[j][i] = cnt;
		}
	}
	for(int i = 1;i <= n;i ++)
		low_cost[i] = 0xfffffff;
}

int calc()
{
	bool mark[MAXN] = {false};
	int sum = 0,s = 1,m = 1,tmin = 0xfffffff,ti = 0;
	mark[s] = true;
	while(m < n)
	{
		tmin = 0xfffffff; ti = 0;
		for(int i = 2;i <= n;i ++)
		{
			if(!mark[i] && low_cost[i] > gra[s][i])
				low_cost[i] = gra[s][i];
			if(!mark[i] && tmin > low_cost[i])
			{
				tmin = low_cost[i];
				ti = i;
			}
		}
		s = ti;
		mark[s] = true;
		sum += tmin;
		m ++;
	}
	return sum;
}

int main()
{
	while(cin>>n && n)
	{
		memset(gra , 0 , sizeof(gra));
		memset(low_cost , 0 , sizeof(low_cost));
		for(int i = 1;i <= n;i ++)
			scanf("%s",str[i]);
		init();
		printf("The highest possible quality is 1/%d.\n",calc());
	}
	return 0;
}
发表更新随笔杂谈

一些事情

一些事情，看开了一些事情，不算看开吧，只是在事实面前不想做反抗也做不出反抗罢了。

发表更新随笔杂谈

院内 ACM 大赛

今天下午两点到五点，理工配楼二层信息学院ACM大赛，ACMore_txj，ACMore_znc，ACMore_yld，共12道题，三个小时做出四道题，两道一直WA，没过，二等奖。一等奖五道题目。哎，即使不是正规的ACM/ICPC题目，还是感觉到自己太弱了，真的太弱了。仰仗学了不少模板就以为可以变厉害了，其实不是，ACM的题目更多的还是需要思维而不是记忆的，正如ACM朴神说的：“现在ACM模板题目已经不多了，更多的是多种算法思想混杂在一起需要自己去组织”。真的不能再沉迷在POJ排名上了，现实说明你仍然是以前那个蒟蒻，你的实力并没有提高多少，无非就是见得多一点，仅此而已。至于怎么真正提升自己，我不知道，我真的不知道，得过且过？还是由算法研究转向应用呢？真的想要动摇了，毕竟不是ACM队的，又何必？

发表更新随笔杂谈

总结 & 反思

刚刚过掉一道题，这题是上学期接触编程不久后做出来的，但是刚刚在做的时候却一直WA，脑海里一直想着当初是怎么1A的，尽量去揭开那时的记忆拿到算法，但是总想不出来，过了好久还是没过，只能打开以前的文件夹看了一下以前的做法，我现在的做法和那时几乎相同，但是有一步比较关键的没想到。也许是看不起那时的自己，认为那时能A的题目现在一定能A，但是事实说明，目前好像有点自信心过于膨胀了。POJ上连续刷了半个学期的题目，一口气看了很多算法和数据结构，就认为自己已经变牛了，可事实说明，你还是当初那个什么都不懂的你。圣人尚自谦，何况你还不是圣人，何况这一行有那么多的惊才绝艳的天才妖孽，你凭什么飘飘然？脚踏实地才是王道，学院ACM队的大牛现在仍是我不可企及的目标，何况还有国家队的大神呢？

好了，清醒一下，后天就是学院举行的程序设计大赛，争取拿个好成绩吧。

发表更新算法设计 / 技术学习

字典树

字典树，就是一种最大限度的利用单词的公共前缀高效查询单词（但不止是单词，所有有前缀的都可以类似进行查找）的数据结构。节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node
{
    node *next[26];//26个字母，NULL则表示没有相应字母的分支
    bool isWord;//true表示从根节点到当前节点路途中所有字母连成的单词已经在字典中
    int point;//指向单词的信息域（如释义等）
    node()//初始化函数
    {
        for(int i = 0;i < 26;i ++)
            next[i] = NULL;
        isWord = false;
        point = 0;
    }
}

建树和查询都非常方便，删除操作并不常用，比较偷懒的方法就是找到待删除单词的最后一个字母所在节点，把isWord标记置为false即可。代码就不给出了。

需要注意的是，在实际建树过程中，如果动态分配空间无论是new还是malloc都会很慢，一般都会TLE的，所以代码都是静态实现，即先分配一定的空间，需要用新节点时就从空间里拿。

例题:

一、POJ 2503 Babelfish

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
poj  2503
17664K	235MS
*/
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 150005

using namespace std;

struct node
{
	node *next[26];
	bool isWord;
	int point;//不在结构体内设置字符数组而是模拟一个指针指向储存区这样可以节省不少空间 
	node()
	{
		for(int i = 0;i < 26;i ++)
			next[i] = NULL;
		isWord = false;
		point = 0;
	}
}all[MAXN];

int index = 1,size;
char store[100005][11];

void insert(char *str1,char *str2)
{
	node *tmp = &all[0];
	int len = strlen(str1);
	for(int i = 0;i < len;i ++)
	{
		int num = str1[i] - 'a';
		if(!tmp->next[num])
			tmp->next[num] = &all[index++];
		tmp = tmp->next[num];
	}
	tmp->isWord = true;
	size ++;
	tmp->point = size;
	strcpy(store[size] , str2);
}

void find(char *s)
{
	node *tmp = &all[0];
	int len = strlen(s);
	for(int i = 0;i < len;i ++)
	{
		int num = s[i] - 'a';
		if(!tmp->next[num])
		{
			printf("eh\n");
			return ;
		}
		tmp = tmp->next[num];
	}
	if(tmp->isWord)
		printf("%s\n",store[tmp->point]);
	else
		printf("eh\n");
}

int main()
{
	char str1[12] = {0},str2[12] = {0},s[24];
	while(gets(s) && s[0])
	{
		sscanf(s,"%s %s",str1,str2);
		insert(str2,str1);
	}
	while(scanf("%s",s) != EOF)
	{
		find(s);
	}
	return 0;
}

二、POJ 3630、Phone List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
poj 3630
4628K	219MS
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

#define MAXN 100005

using namespace std;

struct alp
{
	char s[11];
}per[MAXN / 10 + 5];

struct node
{
	bool isWord;
	node *next[10];
	node()//初始化函数很重要！ 
	{
		isWord = false;
		for(int i = 0;i < 10;i ++)
			next[i] = NULL;
	}
}all[MAXN];

bool cmp(alp a,alp b)
{
	return strlen(a.s) < strlen(b.s);
}

void doIt()
{
	memset(all , 0 , sizeof(all));
	int n,index = 0;
	cin>>n; node *root, *tmp;
	root = &all[index++];
	for(int i = 1;i <= n;i ++)
		scanf("%s",per[i].s);
	sort(per + 1 , per + n + 1 , cmp);
	//要先按字符串长度从小到大排序，不然对于 12  1之类的数据会出错 
	for(int p = 1;p <= n;p ++)
	{
		tmp = root;
		int len = strlen(per[p].s);
		for(int i = 0;i < len;i ++)
		{
			int num = per[p].s[i] - '0';
			if(tmp->next[num])
			{
				if(tmp->next[num]->isWord)
				{
					printf("NO\n");
					return ;
				}
			}
			else
				tmp->next[num] = &all[index++];
			tmp = tmp->next[num];
		}
		tmp->isWord = true;
	}
	printf("YES\n");
	return ;
}

int main()
{
	int T;
	cin>>T;
	while(T --)
	{
		doIt();
	}
	return 0;
}
关注我

最新文章

分类

标签

三体1
不吐不快4
书单30
分布式1
历史2
同人随笔1
图灵完备1
子夜自话1
容器1
影视评论2
数据库1
算法17
胡思乱想13
计算机学习57
读书笔记133
随笔1

归档

链接

×