posts - 126,  comments - 73,  trackbacks - 0
汇总]搜索题目推荐及解题报告(转自zhouxc07大牛)
2009-12-17 21:32

以前的帖子要么太分散,要么太凌乱,故现在开始,对每一个分类做一个长期更新的汇总贴。

格式说明:题目名后面列出个人此题的大致难度(对菜鸟而言)

POJ 1069 -The Bermuda Triangle(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1069
题意:用给定三角型填充六边形
解法:此题的思想上精华在于坐标化
ps:传说中比较bt,确实比较bt,主要很容易写错,我ac了,但程序没完全对....

POJ 1077 - Eight(中等,此题不做人生不完整)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
题意:八数码问题,超经典题
解法:广搜,A*,双向广搜
相关:http://hi.baidu.com/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html
(百度之星的版本,强烈推荐):http://acm.hnu.cn:8080/online/?action=problem&type=show&id=10466&courseid=0

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

POJ 1167 - The Buses(好难啊)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1167
题意:这道题综合了很多经典的深搜技巧,狂顶
解法:dfs

POJ 1190 - 生日蛋糕(基础,好题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190

题意:略
解法:dfs,题偏简单,但做出来还是有些感觉的

POJ 1324 - Holedox Moving(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324
题意:略
解法:A*,dfs + 上界剪枝,广搜
相关:http://hi.baidu.com/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html
http://hi.baidu.com/zfy0701/blog/item/a3c44ecc049b1c1501e92806.html

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*

POJ 1945 - Power Hungry Cows(??)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
题意:略
解法:在一份解题报告中被列为难题,不过好好像写了个很简单很暴力的bfs就过了...速度还是有些慢,暂时想不到好的启发函数

POJ 2044 - Weather Forecast(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
题意:略
解法:广搜,dp,深搜
相关:http://hi.baidu.com/zfy0701/blog/item/d7b6490f847948e8ab6457c6.html

POJ 2286 - The Rotation Game(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2286
题意:略
解法:IDA*(迭代加深+上下界强剪
相关:http://hi.baidu.com/zfy0701/blog/item/ce0f802261bfbba14723e871.html

POJ 2308 - Dearboy's Puzzle(中等,但做的人少?)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2308
题意:判断连连看是否有解
解法:DFS + BFS
相关:http://hi.baidu.com/zfy0701/blog/item/c62f41af65aa1fca7cd92afc.html

POJ 2426 Remainder(较难,=)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2426
题意:略,主要是数论部分比较容易让人抓狂
解法:bfs
相关:http://hi.baidu.com/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html

POJ 2449 Remmarguts' Date(中等,强烈推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2449
题意:经典问题:K短路
解法:dijkstra+A*,方法很多
相关:http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144

POJ 2688 - Cleaning Robot(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2688
题意:bfs后转换为tsp问题
解法:bfs+dp,bfs+dfs
相关:http://hi.baidu.com/zfy0701/blog/item/ceb06f261749a6128a82a1b2.html

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解决,
dancing links原始论文:http://lanl.arxiv.org/PS_cache/cs/pdf/0011/0011047v1.pdf
翻译:http://sqybi.com/works/dlxcn/

POJ 3322 - Bloxorz I(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3322
题意:略,这个游戏本身很好玩(http://jandan.net/2008/01/24/bloxorz.html
解法:广搜,双向广搜
相关:http://hi.baidu.com/zfy0701/blog/item/d7b6490f847948e8ab6457c6.html

POJ 3460 - Booksort(较难,很推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3460
题意:略
解法:IDA*,A*,DFS*
相关:http://hi.baidu.com/zfy0701/blog/item/5c5a404b0f73ecf582025ce4.html

POJ 3523 - The Morning after Halloween(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3523
题意:把所有机器人移到各自的位置,不能相撞或重合
解法:我的状态设计太暴力了:以所有机器人位置表示状态。然后用A*过,排倒数第几,郁闷。谁知道好的状态设计方法告诉我^_^

POJ 3633 - Copying DNA(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3633
题意:一个填充字符串的搜索题
解法:各种搜法皆宜
相关:算法的实现较挑战,我是参考了 http://www.wiskey86.cn/wordpress/?p=54 才搞定的

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

posted on 2010-07-13 17:05 我风 阅读(623) 评论(1)  编辑 收藏 引用

FeedBack:
# re: 汇总]搜索题目推荐及解题报告(转)
2010-10-03 10:19 |
静止在水平面上的船长L,质量为M,一个质量为m的人站在船头,当此人由船头走到船尾的过程中,船移动的距离为(不计水的阻力)  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年7月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(12)

随笔分类

随笔档案

文章档案

相册

收藏夹

C++

MyFavorite

搜索

  •  

积分与排名

  • 积分 - 319585
  • 排名 - 74

最新评论

阅读排行榜

评论排行榜