发表更新算法设计

POJ 3255 Roadblocks （次短路问题）

解法有很多奇葩的地方，比如可以到达终点再跳回去再跳回来（比如有两个点）。。。。反正就是不能有最短路，不过没关系，算法都能给出正确结果

思想：和求最短路上的点套路一样，spfa先正着求一次，再反着求一次最短路，然后枚举每条边<i,j>找dist_zheng[i] + len<i,j> + dist_fan[j]的第二小值即可！注意不能用邻接矩阵，那样会MLE，应该用邻接表

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
/*
poj    3255
3808K	266MS
*/

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>

#define MAXN 200005
#define MAX_INT 2147483647

using namespace std;

int last[5005], dist_1[5005], dist_2[5005], n, m, gra[5005][5005];
bool mark[MAXN];

struct node
{
	int u;
	int v;
	int w;
	int next;
	node()
	{
		u = v = w = next = 0;
	}
}edge[MAXN];

void spfa( int dist[5005], int s )
{
	queue<int>myQueue;
	dist[s] = 0;
	memset(mark, false, sizeof(mark));
	mark[s] = true;
	myQueue.push(s);
	while( !myQueue.empty() )
	{
		int x = myQueue.front();
		myQueue.pop();
		mark[x] = false;
		int t = last[x];
		while( t )
		{
			if( dist[ edge[t].v ] > dist[x] + edge[t].w  )
			{
				dist[ edge[t].v ] = dist[x] + edge[t].w;
				if( !mark[ edge[t].v ] )
					myQueue.push( edge[t].v );
			}
			t = edge[t].next;
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i ++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		edge[i].u = edge[i + m].v = a;
		edge[i].v = edge[i + m].u = b;
		edge[i].w = edge[i + m].w = c;
		edge[i].next = last[a];
		last[a] = i;
		edge[i + m].next = last[b];
		last[b] = i + m;
	}
	memset( dist_1, 1, sizeof(dist_1) );
	spfa( dist_1, 1 );
	memset( dist_2, 1, sizeof(dist_2) );
	spfa( dist_2, n );
	int ans = MAX_INT, tmp = MAX_INT;
	for(int i = 1;i <= n;i ++)
	{
		int t = last[i];
		while( t )
		{
			if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < tmp )
			{
				ans = tmp;
				tmp = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
			}
			else if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < ans 
					&& dist_1[i] + dist_2[ edge[t].v ] + edge[t].w != tmp )
				ans = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
			t = edge[t].next;
		}
	}
	cout << ans << endl;
	return 0;
}
发表更新算法设计

POJ 3093 Margaritas on the River Walk（0-1背包变形）

这题目的思路很巧妙，什么情况下剩下的所有物品都放不下呢？就是当前剩余物品中最小的那个也放不下。所以，先把物品按照容量从小到大排序，依次枚举当前背包为放不下的最小物品的情况。

对于当前物品i，必有1到i-1的所有物品都放进去，这时候比i大的物品谁放谁不放是不确定的。转换成0-1背包问题：把前i-1个物品都放进去以后，得到空间为tsum – sum[i-1]（前缀和）的包，只要从第i+1到第n个物品中拿出一个方案填充这个包使得剩余体积小于第i个物品的体积就可以了，把总方案数累加就是结果！

注意特殊情况：当排序后最小的物品也无法放入时，直接返回0，因为dp[0]初始化为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
/*
poj     3093
232K	0MS
*/
#include<cstdio>
#include<algorithm>
#include<iostream>

#define MAXN 1005

using namespace std;

int n, m, wei[35], dp[MAXN], sum[MAXN];

__int64 Bag()
{
	memset(sum, 0, sizeof(sum));
	sort( wei + 1, wei + n + 1 );
	if(wei[1] > m)	//因为很可能有最小的也放不下这种情况，而dp【0】是初始化为1的，会输出1 
		return 0;
	for(int i = 1;i <= n;i ++)
		sum[i] = sum[i-1] + wei[i];
	__int64 ans = 0;
	for(int i = 1;i <= n;i ++)
	{
		if(sum[i - 1] > m)
			break;
		memset(dp, 0, sizeof(dp));
		dp[sum[i-1]] = 1;
		for(int j = i + 1;j <= n;j ++)
			for(int k = m; k >= sum[i - 1] + wei[j]; k --)
				dp[k] += dp[k - wei[j]];

		for(int j = m - wei[i] + 1;j <= m;j ++)
			ans += dp[j];
	}
	return ans;
}

int main()
{
	int Cases;
	cin>>Cases;
	for(int cnt = 1; cnt <= Cases; cnt ++)
	{
		cin >> n >> m;
		for(int i = 1;i <= n;i ++)
			cin>> wei[i];
		cout << cnt << " " << Bag() <<endl;
	}
	return 0;
}
发表更新算法设计

POJ 2676 Sudoku（数独）

经典搜索问题，主要是时间上的优化，我用了三个辅助数组记录信息 row[i][k] = 1表示第i行数字k已经被使用，col[j][k] = 1表第j列数字k已经被使用，blo[i][k]表示第i个小九宫格中数字k已经被使用

还有很重要的一个优化（没有优化的话可能会超时，或者非常慢，像POJ讨论区里有很多说正着搜超时，倒着搜0ms，这的确是一个可以用的方法，但是有一定的随机性），每次填数字时，先扫描一遍整个矩阵，找出可选数字情况最少的那个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
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
103
104
105
106
107
/*
poj    2676
236K	0MS
*/ 

#include<cstdio>
#include<iostream>

#define MAXN 10
#define MAX_INT 2147483647

using namespace std;

bool flag = false;
int matrix[MAXN][MAXN], row[MAXN][MAXN], col[MAXN][MAXN], blo[MAXN][MAXN];
//用int判断比bool判断要快！ 
int area[MAXN][MAXN] = {
						{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
						{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
						{0, 7, 7 ,7, 8, 8, 8, 9, 9, 9}
						};

void solve(int cnt)
{
	if(flag)
		return ;
	if( !cnt )
	{
		flag = true;
		for(int i = 1;i <= 9;i ++)
		{
			for(int j = 1;j <= 9;j ++)
				cout<<matrix[i][j];
			cout<<endl;
		}
		return ;
	}
	int tx, ty, Min = MAX_INT;
	for(int i = 1;i <= 9;i ++)	//扫描矩阵，找到可选数字情况最少的那个0 
	{
		for(int j = 1;j <= 9;j ++)
		{
			if( !matrix[i][j] )
			{
				int times = 0;
				for(int k = 1;k <= 9;k ++)
					if( !row[i][k] && !col[j][k] && !blo[area[i][j]][k] )
						times ++;
				if(times < Min)
				{
					Min = times ;
					tx = i;
					ty = j;
				}
			}
		}
	}
	for(int k = 1;k <= 9;k ++)
	{
		if( !row[tx][k] && !col[ty][k] && !blo[area[tx][ty]][k] )
		{
			row[tx][k] = col[ty][k] = blo[area[tx][ty]][k] = 1;
			matrix[tx][ty] = k;
			solve(cnt - 1);
			matrix[tx][ty] = 0;
			row[tx][k] = col[ty][k] = blo[area[tx][ty]][k] = 0;
		}
	}
}

int main()
{
	int cases = 0, cnt = 0;
	cin>>cases;
	while(cases --)
	{
		memset(row, 0, sizeof(row));
		memset(col, 0, sizeof(col));
		memset(blo, 0, sizeof(blo));
		memset(matrix, 0, sizeof(matrix));
		flag = false;
		cnt = 0;
		for(int i = 1;i <= 9;i ++)
		{
			for(int j = 1;j <= 9;j ++)
			{
				char ch;
				cin>>ch;
				matrix[i][j] = ch - '0';
				row[i][matrix[i][j]] = 1;
				col[j][matrix[i][j]] = 1;
				blo[area[i][j]][matrix[i][j]] = 1;
				if( !matrix[i][j] )
					cnt ++;
			}
		}
		solve(cnt);
	}
	return 0;
}
发表更新技术学习

数据结构学习之二叉排序树

介绍：二叉排序树是以一定的规则排列树中元素，因而可以进行快速的排序和查询的树状数据结构，一般规则是：对于树中任意一个节点，左孩子严格小于根，根严格小于右孩子，有点像大根堆。（只是大根堆中左右孩子关系并不确定，且和根的关系是统一的，而且有上浮和下沉操作使得大根堆总是一棵完全二叉树，其不断弹出堆顶形成有序列的过程叫做堆排序。虽然二叉排序树中也有旋转操作使得树尽量平衡，但是由于数值大小分明的左右孩子，在进行平衡操作时远不如大根堆方便快捷。）对于一棵已经构造完成的排序二叉树，它的中序遍历序列即为升序排列的有序列，这就是二叉排序树的排序方法。

基本操作：二叉排序树的基本操作为查找、插入和删除。查找操作以及插入操作过程同二分查找类似，用待处理节点和当前节点进行数值比较，如果待处理节点的值小于当前节点的值，则进入当前节点的左子树进行操作，否则进入当前节点的右子树进行操作，直到到达叶子节点或者操作完成。删除操作有好几种实现方法，我是用的是“替罪羊节点法”，即从待删除节点的左子树中找到最大的一个节点（即“替罪羊节点”），用它的值覆盖待删除节点的值，然后删除替罪羊节点即可。在具体操作中还有许多需要注意的细节，在代码注释中有详细介绍。

一些想法：在最初的代码实现中，曾使用静态树，因为考虑到在处理大型数据时，重复的new或者malloc操作会使得程序慢的令人发指（并不是说指针慢，只是申请空间的过程耗费时间），所以一开始就开一段长度合适的空间，另外设置一个指针指示当前数组中可以用的节点，然后new操作在这里的实现就可以这样写：tmp->lc = &Tree[++index]，如果当前序列空间不够时，再用malloc或new申请另一段空间，有点类似内存池的概念。这样的静态操作经在线评测系统（POJ）测试，在进行最基本的操作来处理100，000左右的数据量时会快上两个甚至更多的数量级。静态树的查找和插入操作都可以正常进行，但是在进行删除操作时，我自己写的回收空间算法（为了节省空间，删除的节点重新归到可用空间中，想法是把待删除节点和当前排序树二叉树用的最后一个节点进行交换，再把上文提到的指针前移一位即可，代码实现可以写成：swap(*tmp , Tree[index–])。）总是不能正确执行，调了一段时间未果就先放在一边，写现在这个用指针操作实现的排序二叉树。

代码：（内置测试数据，并对于测试数据保证代码正确）

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<iostream>
#include<algorithm>

#define MAXN 10005
#define MAX_INT 2147483647
#define LC(x) (x << 1)
#define RC(x) ((x << 1) | 1)
#define MID(x,y) ( (x + y) >> 1 )
#define TIME_BEGIN double t1 = clock()
#define TIME_END double t2 = clock();printf("\n%.2fms\n",t2-t1)

using namespace std;

struct node	//结构体定义
{
	int data;
	node *lc , *rc , *fa;
	node()//初始化 
	{
		data = -1;
		lc = rc = fa = NULL;
	}
};
node *root = new node;;

int ary[15] = {0,213,5,12,45,65,2,1,4,8,6,554,52,-1},n = 12;

void myFind(int now , node *&tmp)//查询函数（从参数节点返回信息） 
{
	tmp = root;
	while(tmp)
	{
		if(now > tmp->data)	//查询值大于当前节点值，进入右子树 
			tmp = tmp->rc;
		else if(now < tmp->data)//查询值小于当前值，进入左子树 
			tmp = tmp->lc;
		else	//找到查询值，返回 
			return ;
	}
}

void myInsert(int now)//插入函数 
{
	node *tmp = root;
	while(1)
	{
		if(now > tmp->data)	//若待插入节点大于当前节点的值，则进入右子树 
		{
			if(!tmp->rc)//当前节点右子树为空，则将待插入节点插入到此位置 
			{
				tmp->rc = new node;
				tmp->rc->data = now;
				tmp->rc->fa = tmp;
				return ;
			}
			tmp = tmp->rc;
		}
		else if(now < tmp->data)//若待插入节点小于当前节点的值，则进入左子树 
		{
			if(!tmp->lc)//当前节点左子树为空，则将待插入节点插入到此位置 
			{
				tmp->lc = new node;
				tmp->lc->data = now;
				tmp->lc->fa = tmp;
				return ;
			}
			tmp = tmp->lc;
		}
		else	//树中已有待插入节点，则直接返回 
			return ;
	}
}

void myDelete(node *&tmp)//删除函数  （通过节点） 
/*
若想通过数值删除，则只需先调用一次myFind函数 
*/ 
/*
删除函数的思想是“替罪羊节点”思想：即在待删除节点左子树中
找到最大的节点p（即替罪羊），用它的值覆盖待删除节点的值，然后删除
p即可，其中有很多细节需要注意 
*/ 
{
	node *ano = tmp->lc;
	if(!ano)//若待删除节点没有左子树 
	{
		if(tmp == tmp->fa->lc)//若带删除节点是其父节点的左子树 
			tmp->fa->lc = tmp->rc;
		else					//若带删除节点是其父节点的右子树 
			tmp->fa->rc = tmp->rc;
		if(tmp->rc)	//不能直接访问tmp->rc的父节点，需要先判断tmp->rc是否为空 
			tmp->rc->fa = tmp->fa;
		free(tmp);
	}
	else
	{
		while(ano->rc)	//寻找左子树中的最大节点 
			ano = ano->rc;
		tmp->data = ano->data;//值覆盖 
		if(ano->lc)	//若“替罪羊”有左孩子 
		{
			if(ano->fa->data < ano->lc->data)	
			//判断“替罪羊”的左孩子和替罪羊父亲节点的大小关系 
				ano->fa->rc = ano->lc;
			else
				ano->fa->lc = ano->lc;
			ano->lc->fa = ano->fa;
		}
		else
		{
			if(ano->fa == tmp)	//判断替罪羊是左子树根还是左子树的其他节点 
				ano->fa->lc = NULL;
			else
				ano->fa->rc = NULL;
		}
		free(ano);
	}
}

void myInit()//初始化整棵树 
{
	root->data = MAX_INT;
	for(int i = 1;i <= n;i ++)
		myInsert(ary[i]);
}

void myPrint(node *tmp)//中序遍历方式输出整棵树，形成有序列 
{
	if(!tmp)
		return ;
	myPrint(tmp->lc);
	cout<<tmp->data<<" ";
	myPrint(tmp->rc);
}

void myInit_test()	//myInit测试函数
{
	cout<<endl; 
	cout<<"====myInit函数测试开始==========="<<endl;
	cout<<endl;
	myInit();
	cout<<endl;
	cout<<"====myInit函数测试结束==========="<<endl;
	cout<<endl;
}

void myPrint_test() //myPrint测试函数 
{
	cout<<endl;
	cout<<"====myPrint函数测试开始==========="<<endl;
	cout<<endl;
	myPrint(root->lc);
	cout<<endl;
	cout<<endl;
	cout<<"====myPrint函数测试结束==========="<<endl;
	cout<<endl;
}

void myFind_test() //myFind测试函数 
{
	cout<<endl;
	cout<<"====myFind函数测试开始==========="<<endl;
	cout<<endl;
	for(int i = 1;i <= n;i ++)
	{
		node *tmp;
		myFind(ary[i] , tmp);
		cout<<tmp->data<<" ";
	}
	cout<<endl;
	cout<<endl;
	cout<<"====myFind函数测试结束==========="<<endl;
	cout<<endl;
}

void myDelete_test() //myDelete测试函数 
{
	cout<<endl;
	cout<<"====myDelete函数测试开始==========="<<endl;
	cout<<endl;
	for(int i = 1;i <= n;i ++)
	{
		node *tmp;
		myFind(ary[i] , tmp);
		myDelete(tmp);
		myPrint(root->lc);
		cout<<endl;
		myInsert(ary[i]);
	}
	cout<<endl;
	cout<<"====myDelete函数测试结束==========="<<endl;
	cout<<endl;
}

int main()
{
	TIME_BEGIN; 
	myInit_test();			//myInit函数测试 
	myPrint_test();			//myFind函数测试
	myFind_test();			//myFind函数测试
	myDelete_test();		//myDelete函数测试 
	TIME_END;
}
发表更新算法设计

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;
}
关注我

最新文章

分类

标签

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

归档

链接

×