发表更新随笔杂谈

院内 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;
}
发表更新转载文章

注做好一件事

作者: JACK ALTMAN 来源: 36氪

1
2
人们对机会的估值过高，这是我在下棋的时候学到的一点。你其实只需要一个好的选择就行，没必要同时去追求 A、B、C、D
——Peter Thiel

是让你的选择尽可能开放，还是全心全意抓住一个选择，专心做好一件事情——可以说这两者之间的权衡，是我们生活中经常会碰到的。我们自打上学起，就一直被教育不要去做那些可能会断了某条路的决定。

这种让未来保持开放，让自己未来拥有更多选择和出路也是可以理解的。握在手中的成功机会越多，你的未来也就会越成功，不是吗？

不细想可能会觉得保持开放的确很好，但我认为事情并非看上去那么简单，原因如下：

  1. 明星效应。很简单，在一个领域保持顶尖水平，比在一两个领域保持领先水平和五六个领域保持一般水准都要更有价值、并且收益更好。
  2. 有悖常识的真相：让未来更开放的方式，正是专注的去做好一件事情。这个世界上最成功的人，他们在某一领域获得成功之后，可通过经营杠杆进入任何他们想要涉足的领域。而这都得依赖于他们曾极致的专注在做好一件事情上。

我时常会将这个权衡同创业公司连系起来思考。在创立一家公司时，创始人也会面临这个权衡，究竟是让未来更加多元，更开放，同时追求好几个选择，还是专注的做好其中一个。而通常，最好的创业公司都会选定一个，然后寻找一切方法让它成为现实。自然，也有很多创业公司他们并不清楚未来的路，他们相信手中握有的诸多好的选择中，总有一两个能行得通。

记住，在某一个水平上，你一次只能做好一件事情。能够拿到你最想去的学校和公司的 Offer，比拿到在你 Reference 排名中名列 2-5 位的 Offer 要好。而在一件事情上能够做到 99%，也比在 2 件事情上都能做到 90%，或者 3 件事情上做到 80% 要强很多。

如果你可以在不失专注的情况下够获得一些机会，那就抓住它们。这里我并不是宣扬你得故意同机会保持距离。我要做的就是让人们开始重视专注，因为同 Peter Thiel 一样，我也认为人们普遍高估了机会的价值。

发表更新算法设计

POJ 2251 Dungeon Master(BFS例题)

用STL的queue实现BFS，最基础的题目了，不多说上代码

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
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 35

using namespace std;

int lv,n,m,sta_x,sta_y,sta_z;
char maze[MAXN][MAXN][MAXN];
int op[7][3] = {{0,0,0},{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
bool mark[MAXN][MAXN][MAXN];

struct node
{
	int z;
	int x;
	int y;
	int step;
};

void find_point()
{
	for(int i = 0;i < lv;i ++)
	{
		for(int j = 0;j < n;j ++)
		{
			for(int k = 0;k < m;k ++)
			{
				if(maze[i][j][k] == 'S')
				{
					sta_x = j; 
					sta_y = k;
					sta_z = i;
				}
			}
		}
	}
}

void bfs()
{
	bool flag = false;
	memset(mark , false , sizeof(mark));
	mark[sta_z][sta_x][sta_y] = true;
	queue<node>myQueue;
	node st;
	st.z = sta_z; st.x = sta_x; st.y = sta_y; st.step = 0;
	myQueue.push(st);
	while(!myQueue.empty())
	{
		node tmp = myQueue.front();
		myQueue.pop();
		for(int i = 1;i <= 6;i ++)
		{
			int tz = tmp.z + op[i][0];
			int tx = tmp.x + op[i][1];
			int ty = tmp.y + op[i][2];
			if(tz >=0 && tz < lv && tx >=0 && tx < n && ty >=0 && ty < m && !mark[tz][tx][ty])
			{
				if(maze[tz][tx][ty] != '#')
				{
					if(maze[tz][tx][ty] == 'E')
					{
						printf("Escaped in %d minute(s).\n",tmp.step + 1);
						return ;
					}
					mark[tz][tx][ty] = true; node now;
					now.z = tz; now.x = tx; now.y = ty;
					now.step = tmp.step + 1;
					myQueue.push(now);
				}
			}
		}
	}
	printf("Trapped!\n");
}

int main()
{
	while(cin>>lv>>n>>m && (lv || n || m))
	{
		for(int i = 0;i < lv;i ++)
			for(int j = 0;j < n;j ++)
				scanf("%s",maze[i][j]);
		find_point();
		bfs();
	}
	return 0;
}
发表更新算法设计 / 技术学习

由二叉树的两个遍历序列求另一个遍历序列

二叉树的重要的遍历序列有三种：先序遍历，中序遍历，后序遍历。其中中序遍历可以由其他两种遍历序列定位的根来划分出左右两棵子树，所以已知的两种遍历序列中必须有中序遍历。

示意图（先序+中序->后序）

示意图

对于先序遍历序列，树根一定是第一个元素（后序遍历的根则是最后一个），知道树根后在中序遍历中找到树根，则根前面的就是左子树，后面的就是右子树，再递归的对左右子树执行上述操作直到序列为空，输出序列就是另一种序列。对于求先序序列，每次都是找到树根就输出，而求后序序列时是先递归处理完左右子树后再输出根。

代码：

输入中序和后序，求先序

输入：

DBKFIAHEJCG
DKIFBHJEGCA

输出：

ABDFKICEHJG

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
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 150

using namespace std;

char in[MAXN],post[MAXN];

void make_pre(char *a,char *b,int len)
{
	cout<<b[len-1];
	int le1 = 0,le2 = 0;
	for(int i = 0;i < len;i ++,le1 ++)
		if(a[i] == b[len-1])
			break;
	le2 = len - le1 - 1;
	if(le1 > 0)
		make_pre(a,b,le1);
	if(le2 > 0)
		make_pre(&a[le1+1],&b[le1],le2);
}

int main()
{
	freopen("./tree_trans.in" , "r" , stdin);
	cin>>in>>post;
	make_pre(in,post,strlen(in));
	return 0;
}

输入中序和先序，求后序

输入：

DBKFIAHEJCG
ABDFKICEHJG

输出：

DKIFBHJEGCA

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
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 150

using namespace std;

char in[MAXN],pre[MAXN];

void make_post(char *a,char *b,int len)
{
	int le1 = 0,le2 = 0;
	for(int i = 0;i < len;i ++,le1 ++)
		if(a[i] == b[0])
			break;
	le2 = len - le1 - 1;
	if(le1 > 0)
		make_post(a,&b[1],le1);
	if(le2 > 0)
		make_post(&a[le1+1],&b[le1+1],le2);
	cout<<b[0];
}

int main()
{
	freopen("./tree_trans.in" , "r" , stdin);
	cin>>in>>pre;
	make_post(in,pre,strlen(in));
	return 0;
}
发表更新算法设计

堆和堆排序

所谓堆，就是一棵完全二叉树，对于二叉树的任意一个节点node,它的左右孩子（如果有的话）都和node满足同一种关系，如都大于node（小根堆）或都小于node（大根堆），但是左右孩子之间的关系没有要求。通常用数组来实现一个堆，对于每一个节点，它的下标2就是左孩子（如果有的话），左孩子下标再加一就是右孩子（如果有的话），操作起来很方便。堆的构造是每插入一个元素都对元素进行适当的上浮调整，使之满足堆的条件，时间复杂度为O(nlogn)。如果每次删除堆顶并输出，并将堆的最后一个元素移到堆顶后再对其进行下沉调整重新形成一个堆，循环操作直到堆为空，那么最后输出的序列一定是有序的，这就是堆排序。

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
/*
堆和堆排序
*/
#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<iostream>
#include<algorithm>

#define MAXN 100005
#define MAX_INT 2147483647
#define FA(x) (x>>1) 
#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%.2lfms\n",t2-t1)

using namespace std;

int size,top = 1;
int heap[MAXN];

bool cmp(int a,int b)//关键字比较函数，目前是构造小根堆 
{
	return a < b;
}

void up(int id)//上浮操作 
{
	if(id == 1)
		return ;
	if(!cmp(heap[FA(id)] , heap[id]))
	{
		swap(heap[FA(id)] , heap[id]);
		up(FA(id));
	}
}

void down(int id)//下沉操作 
{
	if(RC(id) <= size)//当前节点有左右孩子 
	{
		if(cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
		else if(!cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[RC(id)] , heap[id]))
		{
			swap(heap[RC(id)] , heap[id]);
			down(RC(id));
		}
	}
	else if(LC(id) <= size)//当前节点只有左孩子 
	{
		if(cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
	}
}

void insert(int t)//插入新元素 
{
	heap[++size] = t;
	up(size);//上浮调整堆 
}

int dele()//删除并返回堆顶 
{
	int tmp = heap[top];
	heap[top] = heap[size--];
	down(top);//下沉调整堆 
	return tmp;
}

void print(int num)//按层遍历 
{
	int k = 1,cnt = 0,kk = 0;
	while(num)
	{
		num -= k;
		while(kk < k)
		{
			cnt ++; kk ++;
			cout<<heap[cnt]<<" ";
		}
		kk = 0;
		cout<<endl;
		k = min(k<<1, num);
	}
}

int main()
{
	TIME_BEGIN;
	freopen("./heap.in" , "r" , stdin);
	int t;
	while(cin>>t)
	{
		insert(t);//插入堆元素 
	}
	print(size);//按层遍历整个堆 
	cout<<"==============="<<endl;
	while(size)
	{
		cout<<dele()<<" ";//依次弹出堆顶进行排序 
	}
	cout<<endl<<"==============="<<endl;
	TIME_END;
	return 0;
}

测试数据：15 1 2 9 8 7 6 3 11 13 5 12 4 10 14

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
1
3 2
8 5 4 6
15 11 13 9 12 7 10 14
===============
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
===============

0.00ms

——————————–
Process exited with return value 0
Press any key to continue . . .
发表更新算法设计

POJ 3253 Fence Repair

哈夫曼思想，优先队列解决

手打版

就把上一篇堆的代码做了点改动

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
/*
poj  3253
368K	47MS
*/

#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<iostream>
#include<algorithm>

#define MAXN 30005
#define MAX_INT 2147483647
#define FA(x) (x>>1) 
#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%.2lfms\n",t2-t1)

using namespace std;

int size,top = 1;
__int64 heap[MAXN];

bool cmp(__int64 a,__int64 b)
{
	return a < b;
}

void up(int id)
{
	if(id == 1)
		return ;
	if(!cmp(heap[FA(id)] , heap[id]))
	{
		swap(heap[FA(id)] , heap[id]);
		up(FA(id));
	}
}

void down(int id)
{
	if(RC(id) <= size)
	{
		if(cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
		else if(!cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[RC(id)] , heap[id]))
		{
			swap(heap[RC(id)] , heap[id]);
			down(RC(id));
		}
	}
	else if(LC(id) <= size)
	{
		if(cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
	}
}

void insert(__int64 t)
{
	heap[++size] = t;
	up(size);
}

__int64 dele()
{
	__int64 tmp = heap[top];
	if(RC(top) <= size)
	{
		if(heap[LC(top)] < heap[RC(top)])
		{
			tmp += heap[LC(top)];
			heap[LC(top)] = heap[size--];
			down(LC(top));
		}
		else
		{
			tmp += heap[RC(top)];
			heap[RC(top)] = heap[size--];
			down(RC(top));
		}
		heap[top] = tmp;
		down(top);
	}
	else
	{
		size --;
		tmp += heap[LC(top)];
	}
	return tmp;
}

void print(int num)
{
	int k = 1,cnt = 0,kk = 0;
	while(num)
	{
		num -= k;
		while(kk < k)
		{
			cnt ++; kk ++;
			cout<<heap[cnt]<<" ";
		}
		kk = 0;
		cout<<endl;
		k = min(k<<1, num);
	}
}

int main()
{
	__int64 sum = 0;
	freopen("./3253.in" , "r" , stdin);
	int n;
	cin>>n;
	if(n == 1)
	{
		cout<<0<<endl;
		return 0;
	}
	while(n--)
	{
		int t;
		scanf("%d",&t);
		insert(t);
	}
	while(size > 1)
	{
		sum+= dele();
	}
	cout<<sum<<endl;
	return 0;
}

STL偷懒版

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
/*
poj 3253
324K	32MS
*/
#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int>myQueue;
int main()
{
	int n,t;
	__int64 ans = 0;
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d",&t);t = -t;
		myQueue.push(t);
	}
	while(myQueue.size() > 1)
	{
		__int64 t1 = myQueue.top();
		myQueue.pop();
		__int64 t2 = myQueue.top();
		myQueue.pop();t1 += t2;ans += t1;
		myQueue.push(t1);
	}
	printf("%I64d\n",-ans);
	return 0;
}
发表更新算法设计

POJ 1042 Gone Fishing（贪心）

题目大意：

一个人要去钓鱼，可用时间为h（小时），可选湖泊为n个，可以将湖泊看成在一条直线上的顺序的n个点，要去第k个点必须从第k-1个点出发，所用时间为t[k-1]（个5分钟），每个湖初始鱼的数目为f[i]（注意，可能为0），每个湖泊单位时间（五分钟）鱼的数目减少d[i]条（这是人在该湖泊钓鱼的情况下，人不在就不会减少）,问h时间内他能钓的鱼最多是多少？

题目分析：

贪心策略，先找到他能到达的最远的（所有时间用来跑路的极限值）湖泊p，然后分为若干种情况:他的活动范围是 11 、 12 、 ······· 1p，即他可以选择的跑去钓鱼的最远的湖泊有p个，枚举每种情况，把总时间减去跑路的时间就是他能钓鱼的时间，在情况 1k 时，对于每一个单位时间（五分钟），都从1到k枚举每个湖泊找到最大值记录相应位置，然后每种情况都算一次，迭代出最大值就可以了。

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
/*
poj  1042
236K	47MS
*/

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

#define MAXN 30

using namespace std;

int f[MAXN],d[MAXN],t[MAXN],n,ans[MAXN],tot[MAXN][200],h;
//tot[i][j]是第i个在湖第j个5分钟能抓的鱼的数目 

void init()
{
	h *= 12;
	for(int i = 1;i <= n;i ++)
		scanf("%d",&f[i]);
	for(int i = 1;i <= n;i ++)
		scanf("%d",&d[i]);
	for(int i = 1;i < n;i ++)
		scanf("%d",&t[i]);
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= h;j ++)
			tot[i][j] = max(f[i] - d[i] * (j - 1) , 0);
}

void calc()
{
	int far = 1,tmp[MAXN] = {0},index[MAXN] = {0},sum = -0xfffffff;//可能有全为零的情况 
	//far为其能到达并钓一会鱼的最远的湖,tmp[i]是从i出发到达下一个湖时用的跑路总时间 
	//index[i]是指为钓到最多的鱼在第i个湖待的时间 
	while(far <= n)//计算所能到达的最远的湖 
	{
		tmp[far] = tmp[far-1] + t[far];
		if(tmp[far] >= h)
			break;
		far++;
	}
	if(far > n)
		far = n;
	int cnt = 1;
	while(cnt <= far)//从近到远试遍所有情况 
	{
		int tsum = 0;
		memset(index , 0 , sizeof(index));
		int th = h - tmp[cnt-1];//可用钓鱼时间
		for(int i = 1;i <= th;i ++)//对于每一个单位时间（五分钟）都寻找最多鱼的湖 
		{
			int tmax = 0,tj = 1;//默认为第一个湖 
			for(int j = 1;j <= cnt;j ++)//最远到第cnt个湖  cnt∈[1,far] 
			{
				if(tot[j][index[j]+1] > tmax)
				{
					tj = j;//记录位置 
					tmax = tot[j][index[j]+1];//记录数目 
				}
			}
			tsum += tmax;
			index[tj] ++;//在第tj个湖已经待的时间+1 
		}
		if(tsum > sum)//替换 
		{
			sum = tsum;
			memcpy(ans , index , sizeof(index));
		}
		cnt ++;//范围扩大一个湖 
	}
	for(int i = 1;i <= n;i ++)
	{
		if(i == n)
			printf("%d\n",ans[i] * 5);
		else
			printf("%d, ",ans[i] * 5);
	}
	printf("Number of fish expected: %d\n\n",sum);
}

int main()
{
	freopen("./1042.in" , "r" , stdin);
	while(cin>>n>>h)
	{
		init();
		calc();
	}
	return 0;
}
发表更新算法设计

POJ 2823 Sliding Window（单调队列）

所谓单调队列，就是支持从队尾插入删除，队头查询的一种数据结构，虽然用途不是很广泛，但是对于某些问题如：在一个被不断刷新的缓存区中多次查询最小值（最大值）非常高效

构造方法：对于单调上升队列：每次从队尾入队一个元素，都从队尾起依次删除比当前元素大的元素，强制使队列单调

示例，POJ 2823 Sliding Window

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
/*
poj  2823
8012K	5344MS
*/ 

#include<cstdio>
#include<iostream>

#define MAXN 1000005
#define MAX_INT 2147483647

using namespace std;

int que_min[MAXN][2],que_max[MAXN][2],ans_min[MAXN],ans_max[MAXN];
//que二维数组，[][0]表示元素，[][1]表示元素在输入序列中的下标 
int main()
{
	//freopen("./2823.in" , "r" , stdin);
	int m,n,h_max = 0,t_max = 0,h_min = 0,t_min = 0,t;
	/*
	h_min   t_min
	h_max   t_max
	分别是两个单调队列的头尾指针 
	*/
	que_min[0][0] = -MAX_INT; que_max[0][0] = MAX_INT;
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d",&t);
		while(t <= que_min[t_min][0] && t_min >= h_min)
		//从尾端开始，删除所有比当前元素大的元素 
		{
			t_min --;
		}
		t_min ++;
		que_min[t_min][0] = t;
		que_min[t_min][1] = i;
		while(que_min[h_min][1] <= i - m)
		//从当前位置i开始，取最小值的范围只能是[i - m + 1 , i] 
		//删除不合法的元素
		{
			h_min ++;
		}
		ans_min[i] = que_min[h_min][0];
	
		//同理计算最大值 
		while(t >= que_max[t_max][0] && t_max >= h_max)
		//从尾端开始，删除所有比当前元素小的元素 
		{
			t_max --;
		}
		t_max ++;
		que_max[t_max][0] = t;
		que_max[t_max][1] = i;
		while(que_max[h_max][1] <= i - m)
		//从当前位置i开始，取最大值的范围只能是[i - m + 1 , i]
		//删除不合法的元素
		{
			h_max ++;
		}
		ans_max[i] = que_max[h_max][0];
	}
	
	for(int i = m;i <= n;i ++)
		printf("%d ",ans_min[i]);
	printf("\n");
	for(int i = m;i <= n;i ++)
		printf("%d ",ans_max[i]);
	printf("\n");
	return 0;
}
关注我

最新文章

分类

标签

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

归档

链接

×