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

字典树

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

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

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

堆和堆排序

所谓堆，就是一棵完全二叉树，对于二叉树的任意一个节点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;
}
发表更新算法设计

POJ题目分类（不定期更新）

大水题

  1. a加b 不解释
  2. 求高精度幂 高精度幂，巨多细节
  3. Hangover 套公式
  4. I Think I Need a Houseboat 虽然简单，但是做了无数次总是不能1A
  5. DNA Sorting 快排就行
  6. Packets 细节细节
  7. 高精度 细心一点就好
  8. IMMEDIATE DECODABILITY 本应该用字典树的，但是数据量只有10，就算了
  9. Cable master 精度卡哭了
  10. The Clocks 想清楚，暴力就行
  11. THE DRUNK JAILER
  12. Self Numbers 记着不难
  13. Cabric Number Problem 数字黑洞问题
  14. Bode Plot 阅读理解
  15. TEX Quotes 大水
  16. Integer Inquiry 高精度加法
  17. u Calculate e 很麻烦
  18. Digital Roots
  19. Adding Reversed Numbers 不难
  20. Clay Bully
  21. Doubles
  22. Skew数 水~
  23. Just the Facts 会写循环就行了
  24. Eva’s Problem
  25. Sorting by Swapping
  26. Yeehaa! 水！
  27. Diplomatic License
  28. Litmus Test 化学题
  29. No Brainer 题目就是最好的评价
  30. Calendar 很恶心
  31. Recaman’s Sequence 咬牙把数组开大点就行了
  32. Honey and Milk Land 理解题解+细节
  33. IP Address 水~
  34. Speed Limit 大水题
  35. Vertical Histogram 注意格式就行了
  36. ISBN 细节
  37. Specialized Four-Digit Numbers
  38. The King
  39. Lotto 简单求组合数
  40. Ones
  41. Error Correction 就是因为忘记归零参数WA了
  42. Goldbach’s Conjecture 策略选择需要稍微想一下
  43. Beat the Spread! 英语题
  44. Questions and answers 就一个快排
  45. Who’s in the Middle sort，没了
  46. Bull Math 高精度乘法
  47. Hardwood Species 快排
  48. Peter’s smokes 就当做阅读理解了
  49. How much did the businessman lose 就当做阅读理解了
  50. Very Simple Problem 记着是好像不难
  51. WERTYU 就是打表麻烦
  52. Jolly Jumpers
  53. Keep on Truckin’ 水！
  54. Series Determination 算一下公式
  55. Soundex
  56. Electrical Outlets == a+b
  57. Unhappy Jinjin 10秒AC不了就别活了，真的不夸张。10秒，至于为什么，看题就知道
  58. Trees 马路上的树
  59. Sum of Consecutive Prime Numbers 不痛不痒
  60. Big Clock 大水
  61. Pascal Library 看懂题就好
  62. A Simple Question of Chemistry 叙述的可真够麻烦的，就当练英语吧
  63. Goldbach’s Conjecture 打个素数表+细节
  64. Dirichlet’s Theorem on Arithmetic Progressions
  65. Nasty Hacks 水·~
  66. Rounders 细节@
  67. Triangular Sums 水~
  68. Quicksum
  69. Root of the Problem 细节细节+神奇的double+想清楚策略
  70. World Cup 想清楚关系就很简单了！
  71. Parkside’s Triangle
  72. Lab杯
  73. Judging Olympia
  74. Prime Gap 素数问题
  75. Beer Refrigerator 暴搜就行了
  76. Number-guessing Game
  77. The Seven Percent Solution
  78. Cow Multiplication 水~！
  79. 时间日期格式转换 大水！
  80. 分数加减法 比较麻烦
  81. 取模运算 真是。。。。
  82. 序列 高精度加法+迭代
  83. 快算24 样例就是全部的测试数据

BFS

  1. Find The Multiple 也可以用数学证明和DFS，而且都比BFS快！
  2. Knight Moves 第一道BFS
  3. Knight Moves 裸BFS
  4. Dungeon Master

DFS

  1. 木棒 经典深搜 + 酷炫剪枝
  2. 滑雪 记忆化搜索
  3. 生日蛋糕 剪枝很重要
  4. The 3n + 1 problem
  5. 棋盘问题
  6. Find The Multiple 也可以用数学证明和BFS
  7. Oil Deposit 经典深搜
  8. Function Run Fun 记忆化搜索
  9. 放苹果 勉强算是吧
  10. Red and Black 稍微有点弯的深搜
  11. Zipper 深搜
  12. Lake Counting 经典深搜
  13. A Knight’s Journey 简单DFS
  14. Sudoku 数独问题
  15. 迷宫问题

DP

  1. Dividing想清楚一个点后多重背包就可以了
  2. 需要先稍微想一下~之后很简答
  3. Human Gene Functions LCS变形，注意边界处理
  4. Brackets Sequence 确实需要好好想想
  5. LITTLE SHOP OF FLOWERS 分析关系
  6. The Triangle 数字三角形
  7. Cash Machine 多重背包
  8. Common Subsequence 最长公共子序列
  9. Coins 多重背包
  10. Divisibility 很帅的递推
  11. Charlie’s Change记录路径的多重背包 很吊
  12. Testing the CATCHER 最长不上升子序列
  13. Chores 想清楚关系再递推
  14. World Cup Noise 斐波那契 数列
  15. Alphacode 细节 递推
  16. Jumping Cows 想清楚 核心代码很简单
  17. Apple Catching 想清楚挺水的
  18. Space Elevator 多重背包
  19. Longest Ordered Subsequence 最长上升/下降 子序列
  20. Cow Bowling 数字三角形
  21. Charm Bracelet 0-1背包

计算机几何

  1. Rope 傻瓜凸包

STL 水过

  1. Web Navigation 算是用到了栈，STL水过
  2. Anagram next_permutation 水过
  3. Orders next_permutution 水过
  4. 排列 next_permutation 水过
  5. Stripies 优先级队列
  6. Babelfish map 可水 字典树王道

模拟

  1. 生理周期 简单模拟
  2. Financial Management 。。。
  3. 玛雅历 细节细节
  4. Color Me Less
  5. Parencodings
  6. Moving Tables
  7. Safecracker 略麻烦
  8. Box of Bricks 模板里总结了这类移动问题
  9. Machined Surfaces 看懂题目就好
  10. Perfect Cubes 暴搜即可
  11. Eva’s Problem 不难
  12. Distance on Chessboard 简单找规律
  13. Gold Coins
  14. Cornfields
  15. When Can We Meet? 模拟
  16. Filling Out the Team 不难
  17. Above Average 不难
  18. Blocks 不难
  19. Bank Interest 水~
  20. Feed Accounting 模拟喂牛 细心：
  21. Blurred Vision 应该不难吧
  22. Prerequisites? 应该不难
  23. Monthly Expense 二分法
  24. ICPC Score Totalizer Software 大水题
  25. Ecology tax 题目混乱做的也混乱
  26. Look and Say

数据结构

  1. Web Navigation 算是用到了栈，STL水过
  2. Mobile phones 二维树状数组（最佳） . 线段树，很重要！
  3. Crazy Search 第一道hash
  4. Jungle Roads 最小生成树模板
  5. Agri-Net 最小生成树模板
  6. The Perfect Stall 二分图最大匹配问题
  7. Rails 算是对单栈排序输出序列的理解吧，想清楚细节
  8. Find them, Catch them 种类并查集
  9. Truck History 最小生成树模板
  10. Stripies 大顶堆
  11. 食物链 种类并查集
  12. K-th Number 划分树原型，很重要！
  13. Ultra-QuickSort 归并排序，点树，树状数组
  14. BST 二叉排序树的的外壳，位运算的本质
  15. Stars 树状数组
  16. Constructing Roads 稍微变动的最小生成树
  17. Highways 最小生成树模板
  18. Babelfish 字典树 ，map可水
  19. Ubiquitous Religions 简单并查集
  20. Mayor’s posters 熟悉掌握线段树以及离散的好题！
  21. Sliding Window 单调队列，RMQ，线段树
  22. Fence Repair 优先队列
  23. A Simple Problem with Integers 树状数组（真漂亮）. 线段树
  24. Building Roads 稍微变动的最小生成树
  25. Phone List 字典树

数学证明类

  1. Joseph 约瑟夫环公式+枚举+记忆
  2. 取石子游戏 博弈论
  3. 另类数制转换 吊 Octal Fractions
  4. Ugly Numbers 理同 2591
  5. Factorial
  6. Big Number string公式或者暴力lg都可以
  7. Find The Multiple 这样略麻烦，可以用BFS DFS简单过
  8. Deck 数学公式
  9. Number Steps 其实也挺水的
  10. Sum 想到这么证的人真吊
  11. Count on Canton 简单规律
  12. The Cow Lineup 神犇牛推
  13. Power of Cryptography 神奇的double 严格证明需要泰勒展开式
  14. Herd Sums 简单公式推导
  15. Lost Cows 需要证明推导
  16. Moo Volume 公式推导很麻烦
  17. Binomial Showdown 虽然水，还是WA了很久，而且避免超时还是需要一点数学知识
  18. Set Definition 苦逼快排死得连渣都没有，大神代码果然风骚！
  19. Faulty Odometer 找数学规律，也要细心
  20. Sequence Sum Possibilities 简单数学公式
  21. Gau? in Elementary School 公式
  22. Fibonacci 斐波那契数列矩阵加速求法
  23. Ride to School 其实算不上证明，想清楚很水的

贪心策略

  1. Gone Fishing
  2. To the Max 稍微转换一下就是最大子段和
  3. Best Cow Fences 类似最大连续子段和思想,但是自己尚不能做到举一反三
  4. Tian Ji — The Horse Racing 要好好想想
  5. Maximum sum 和2593 一模一样
  6. Max Sequence

字符串

  1. 487-3279 字符串+排序
  2. Spell checker 要么笨一点加一点剪枝，要么聪明一点想清楚关系，字典树太慢了，暴力就行
  3. Tanning Salon 很简单，栈的思想
  4. 史上最难的问题（←这货只是题目） 凯撒密码
  5. Word Amalgamation
  6. Mileage Bank 不难
  7. Perfection 不难
  8. Easier Done Than Said? 不难
  9. All in All 挺水的
  10. Period 同2406 Power Strings 天才才能想到用next！！
  11. Symmetric Order 简单
  12. To and Fro 不难
  13. Message Decowding 密码
  14. Ancient Cipher 凯撒密码
  15. Guessing Game 不难，但是过得并不顺利，细节
  16. Power Strings 天才才能想到用next！！
  17. Celebrity jeopardy 最水的一道题，没有之一
  18. Surprising Strings
  19. Subsequence
  20. Oulipo 简单KMP
  21. 破译密码 又是凯撒密码
  22. 字符串替换
关注我

最新文章

分类

标签

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

归档

链接

×