POJ搜索题目列表

Note: 本文最初于 2011年02月18日 星期五 18:17 在 hi.baidu.com/lydrainbowcat 发表。

  • 这不是我原创的,是从网上找到的,跟大家分享一下。
  • 后边标的难度是对于小菜而言的,像例如说applepi(杜神牛)这样的神牛除外。
  • 放到这里还有一个原因是为了自己看着方便,因为我搜索较弱,要多加练习。
  • 红的是我已经做过并AC的题,蓝的是我做过但还没AC,或正在做的题。

POJ 1069 -The Bermuda Triangle(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1069
题意:用给定三角型填充六边形
解法:此题的思想上精华在于坐标化

POJ 1077 – Eight(中等,此题不做人生不完整)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
题意:八数码问题,超经典题
解法:广搜,A*,双向广搜 
本博客题解:http://www.lydshy.com/wordpress/123

POJ 1084 – Square Destroyer(中等,经典题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
题意:把每个正方型看做集合中的元素,每个木棒看做是一个子集,求最小的子集覆盖
解法:dfs,A*,广搜肯定爆空间
本博客题解:http://www.lydshy.com/wordpress/125

POJ 1167 – The Buses(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1167
题意:这道题综合了很多经典的深搜技巧,狂顶
解法:dfs
本博客题解:http://www.lydshy.com/wordpress/63

POJ 1190 – 生日蛋糕(基础,好题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190
题意:略
解法:dfs,题偏简单,但做出来还是有些感觉的
本博客题解:http://www.lydshy.com/wordpress/32

POJ 1324 – Holedox Moving(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324
题意:略
解法:A*,dfs + 上界剪枝,广搜

POJ 1376 – Robot(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1376
题意:略
解法:bfs,A*….

POJ 1475 – Pushing Boxes(中等,很推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1475
题意:推箱子游戏
解法:双重bfs(对箱子bfs 时 对人bfs),A*
本博客题解:http://www.lydshy.com/wordpress/61

POJ 1945 – Power Hungry Cows(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
题意:略
解法:略

POJ 2044 – Weather Forecast(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
题意:略
解法:广搜,dp,深搜
本博客题解:http://www.lydshy.com/wordpress/55

POJ 2286 – The Rotation Game(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2286
题意:略
解法:IDA*(迭代加深+上下界剪枝)
本博客题解:
http://www.lydshy.com/wordpress/127

POJ 2308 – Dearboy’s Puzzle(中等,但做的人少?)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2308
题意:判断连连看是否有解
解法:DFS + BFS

POJ 2426 Remainder(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2426
题意:略,主要是数论部分比较容易让人抓狂
解法:bfs

POJ 2449 Remmarguts’ Date(中等,强烈推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2449
题意:经典问题:K短路
解法:dijkstra+A*,方法很多
本博客题解:http://www.lydshy.com/wordpress/118

POJ1072 PuzzleOut(较难,强烈推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1072
题意:有关解密的
解法:Trie+DFS+剪枝
本博客题解:http://www.lydshy.com/wordpress/58

POJ2222 DeeperBlue(中等)
题意:一个国际象棋盘上放着几个子,问最少去掉几个可以不互相攻击。主要考察细心,题目跟题号的性质相符(比较2)
解法:dfs、暴力枚举
本博客题解:http://www.lydshy.com/wordpress/53

POJ 2688 – Cleaning Robot(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2688
题意:bfs后转换为tsp问题
解法:状态压缩BFS。转化为TSP的话极易超时。
 本博客题解:http://www.lydshy.com/wordpress/120

POJ 2908 – Quantum(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2908
题意:其实就是找单源最短路径
解法:优先队列广搜(即dijkstra),建议用位运算优化

POJ 3074 – Sudoku(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3074
题意:数独游戏,数据比2676强很多,但比3076弱
解法:用dfs回溯基本可过,不过每次应选择可能填的数字最少的格子搜,并加入位运算优化和可行性剪枝。
更快的方法是先转换成exact cover问题,然后用经典dancing links解决。

POJ 3322 – Bloxorz I(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3322
题意:略,这个游戏本身很好玩(http://jandan.net/2008/01/24/bloxorz.html)
解法:广搜,双向广搜。

POJ 3460 – Booksort(较难,很推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3460
题意:略
解法:IDA*,A*,双向BFS
本博客题解:http://www.lydshy.com/wordpress/129

POJ 3523 – The Morning after Halloween(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3523
题意:把所有机器人移到各自的位置,不能相撞或重合

POJ 3633 – Copying DNA(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3633
题意:一个填充字符串的搜索题
解法:各种搜法皆宜

POJ 3635 full tank?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3635
题意:最短路变形
解法:广搜
本博客题解:http://www.lydshy.com/wordpress/36

发表评论

电子邮件地址不会被公开。 必填项已用*标注