贺题记录-搜索
本文记录 以搜索算法为主的题目
-
加成序列模板 迭代加深搜索
疑惑
bool dfs(int maxd, int p){ if(p>maxd || a[p]>n) return false; if(a[p]==n){ return true; } if(a[p]<<(maxd-p)如当搜索到
1 2 4 8 10时，仅通过 10+? 并不能推出 8+8
能不能严格证明做法的正确性？
扩展BFS
-
Chamber of Secrets模板 双端队列
问题每次扩展代价只可能是 0 or 1 时，使用 01-BFS(双端队列可保证两端性和单调性) -
电路维修 双端队列
-
装满的油箱典 优先队列BFS (Dijkstra最短路)
注意状态的多元化，但优先队列中一般是以花费作为指标.
此题中的状态就包括了 当前结点和剩余油量以及最小花费 -
和为0的4个数模板 meet in the middle
-
luogu 世界冰球锦标赛典 meet in the middle (勋勋渐进的好题)
-
luogu 移动玩具模板 双向BFS
-
噩梦典 双向BFS(多步数)
双向BFS的一般代码框架
bool BFS(){ 取出队首 u，判断是否符合题目要求 扩展 1. 判断 v 是否合法 2. 使用 st[][] = 0/1/2 判断是否相遇 } int solve(){ 初始化 Qs 与 Qe while 逐层扩展 Qs, Qe }
带估价函数的搜索
-
第K短路 典 \(A^*\)优先队列BFS
估价函数的估值不能大于实际代价 -
八数码问题 \(A^*\)优先队列BFS+康托展开