存档

‘POJ解题报告’ 分类的存档

POJ 1161 The Suspects[并查集]

2011年9月13日 2 条评论

并查集分三个操作,并、查、初始化。初始化时把秩初始化为0,值和父亲都是自己;查的时候看看节点的父亲是不是自己,如果是,则停止查找,如果不是,查找父节点的父节点,同时压缩路径,把子孙节点的父节点都更新为最后找到的父节点。并的时候判断下两个节点是不是在一个集合中,如果不在,判断两个节点的父节点的秩,秩大的做父节点。如果秩相等,则任意一个节点作为父节点,作为父节点的秩增加1.
传送题目地址:POJ 1161 The Suspects http://poj.org/problem?id=1611

1
[......]

继续阅读

POJ 1050 To the Max[DP]

2011年9月13日 没有评论

POJ 2479/2593的拓展,从一维数组变成了二维矩阵,不过我们可以把情况模拟成一维的情况,在DP的基础上需要加上枚举。
题目要求求出给定的一个矩阵的和最大的子矩阵。
我们可以枚举第a行到第c行的情况(假设已经确定矩阵已经确定为最上面为第a行,最下面为第c行),那么只需要确定列的范围即可。我们可以把每一列都求和,这样会得到单独的一行,就可以直接求这一行的最大子段和即可。
POJ 1050 To the Max[DP] 传送:POJ 1050 To the Max http://poj.org[......]

继续阅读

POJ 2479 Maximum sum[DP]

2011年9月12日 没有评论

类似于HDU 1003 Max Sum这一题,只不过这里是说把数组分为两段,把这两段的最大子段和求出来相加,求出最大的这样的值。
方法还是DP,跟HDU1003一样,从i = 0 to n – 1求一次最大子段和,然后从i = n – 1 to 0求一次最大子段和,最后相加判断即可。
POJ 2593 Maximum sum
传送:
POJ 2479 Maximum sum http://poj.org/problem?id=2479
POJ 2593 Max Sequence http://poj.org/p[......]

继续阅读

POJ 2251 Dungeon Master[三维BFS]

2011年9月10日 7 条评论

题目大意:给定一个三维的迷宫,看看能不能从起点走到终点,如果能的话就求出最短的时间(每次移动耗费一个时间单位)。
解题思路:还是搜索,只不过多加了一层;普通的搜索通常是二维情况下的,也就是在一个平面内进行搜索;而这个题目中的搜索范围是一个三维空间;考虑到求最短时间,所以可以用BFS作为搜索方法;二维也好三维也好,BFS的本质是不变的,只是增加了一个向上和向下的移动方向而已。
传送:POJ 2251 Dungeon Master http://poj.org/problem?id=2251
解题代[......]

继续阅读

分类: POJ解题报告 标签: , ,

POJ 3461 Oulipo[KMP]

2011年9月7日 2 条评论

求子串在主串中出现的次数,KMP匹配即可。
传送:POJ 3461 Oulipo http://poj.org/problem?id=3461

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
 
#define MAIN_MAX_COUNT 1000010
#define SUB_MAX_CO[......]

继续阅读

分类: POJ解题报告 标签: ,

POJ 1521 Entropy[哈弗曼编码]

2011年9月3日 2 条评论

题目大意:题目很长,不过就是哈弗曼编码。
解题思路:还是用优先队列(STL提供了priority_queue)来做,先构建好哈弗曼树,然后求每个叶节点的深度就好了。这里用数据来构建哈夫曼树,方便。
传送门:POJ 1521 Entropy http://poj.org/problem?id=1521
Problem: 1521 Memory: 232K Time: 16MS Language: C++ Result: Accepted

#include <iostream>[......]

继续阅读

POJ 1562 Oil Deposits[DFS]

2011年9月3日 没有评论

题目大意:就是求油田的块数,如果一个小油田位于另一个小油田的周围的小矩形上(周围八个小方格),那么认为这两个油田是连通的,求有多少个这样的连通块。
解题思路:DFS搜索,两重循环遍历矩阵,如果这个节点是油田,就从这一个节点出发进行DFS,DFS过程中要进行标记,DFS返回后意味着发现一个连通块。我觉得BFS也是可以的 [em021]
传送门:POJ 1562 Oil Deposits http://poj.org/problem?id=1562
Problem: 1562 Memory: 18[......]

继续阅读

分类: POJ解题报告 标签:

POJ 1321 棋盘问题[DFS]

2011年9月2日 没有评论

题目描述:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
深搜,某一行放不放子的问题,大概是这样。中间判断一下某一列可不可以放子就好了。DFS返回条件是没有子可放了或者行数超出限制了。题目的数据量也不算大,直接用朴素的DFS就可以解决了。

#include <iostream>
#include <cstdio>
#i[......]

继续阅读

POJ 1915 Knight Moves[BFS]

2011年9月2日 没有评论

Knight问题,这个题比较好,给了个图说明了Knight的运行规则。这类题一般都是BFS做啦,可以定义一个数组存放移动的方法,这样更加方便。
更多题目:
POJ 1915 Knight Moves http://poj.org/problem?id=1915
POJ 2243 Knight Moves http://poj.org/problem?id=2243
POJ 2488 A Knight’s Journey http://poj.org/problem?id=2488
解[......]

继续阅读

分类: POJ解题报告 标签: ,

POJ 3278 Catch That Cow[BFS]

2011年9月2日 没有评论

复习数据结构ing,现在做做简单的题目。这是很久以前做的入门的题,翻出来了。用BFS做,如果只用一个队列,那么需要定义结构体来存储节点的位置信息和时间信息;如果不想用结构体的话需要两个队列,这样是一层一层的遍历节点,就只需要一个整型来记录时间信息了。其实都差不多,具体实现手法不同而已,BFS的思想是不变的。
下面两个版本的代码都贴一下,
POJ 3278 Catch That Cow[BFS] [http://poj.org/problem?id=3278]

#include <iost[......]

继续阅读