搜索经验收集

2019-06-22 16:34:11


原理:
1.广搜首解最优

代码技巧:
1.fx[4],fy[4]
2.gtid(),chck()等工具函数
3.用id函数压二维为一维

虫食蒜:
每次填数后立即给还未搜索的位来一个check能大幅度剪枝
看上去让程序变慢,实际上能剪不少,原理还没想清
以及第9组,无氧1.5s,吸氧0.8s
果然搜索都是玄学

usaco的数字三角形:
不宜盲目模拟,最好先研究题目性质

[SHOI2002]滑雪:
要是依次遍历每个点,如果之前bfs没访问到就从这个点开始bfs,会发现如果一条路的两截先后被bfs到,没法拼起来
题目性质:必须从山峰开始滑
队列数组开11000是不够的,实际上1100000也不够
用循环队列也不行,第二组数据我怎么写都会t
实际上这题用dfs好写得一比,只需要每次dfs得时候判断如果这个点来过就直接退
这样做可行是因为dfs的特性,使得在这道题里,如果某个点进行了dfs,则这个点存下的数据一定是最优的,下次再遇到的时候可以直接使用,而不像bfs会反复经过某个点
其实重写一遍也啥,bfs写崩溃的时候写一遍dfs也就5分钟就a了
bfs不见得就比dfs优越

靶形数独:
使用性质削减搜索树

易错点:
bfs染色的时候一定不能偷懒在bfs中每个点的循环开始时染色,而是应该在每个点进队时即染,否则会出现同一个点多次进队的尴尬情况(某点已经来过了,但是因为排在队伍后面所以没被打上标记)
这样写的话一定注意对头的点染色

洛谷1433 吃奶酪:
状态压缩的状态不仅包含来过哪些点,还有现在在哪个点上
这个在dfs的参数上已经体现出来,但是注意记忆化储存状态最优值的数组也是二维的

封锁阳光大学
小木棍
引水入城