发表更新算法设计

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;
}
发表更新算法设计

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

最新文章

分类

标签

Android6
BFS1
Bilibili1
Brainfuck1
DFS1
Docker1
Hadoop1
Hibernate2
JMeter1
Java4
Java Swing2
JavaScript1
Jupyter Notebook1
MySQL1
PHP1
POJ15
Prime 算法1
Python4
Python Web1
Spark1
Spring1
WAMP1
Windows API2
Windows Server1
三体1
不吐不快1
个人网站1
书单18
二叉排序树1
二叉树2
五星出东方利中国1
交通卡1
优先级队列1
停机问题1
先轸1
农奴制1
分页1
动态规划1
单调队列1
历史2
同人1
咪蒙1
哈夫曼树1
国家宝藏1
图灵完备1
图论3
堆1
堆排序1
多线程2
大作业8
子夜自话1
字典树2
容器1
市场调研1
幼稚病1
异步编程1
影评1
思考4
技术栈1
数独1
文件2
晋文公1
最小生成树1
最短路2
次短路1
水平切分1
狼曋1
理中客1
盗墓笔记1
知乎1
科幻随想1
羊斟1
背包1
胡思乱想2
藏密1
计算机学习3
读书笔记93
贪心算法2
随想2
需求分析1

归档

链接

×