基础算法

枚举

上来就是水仙花数

寻找三位数：多种枚举方式，代码难度不同

选择代码难度小、好写的枚举方法

搜索

• 深度优先搜索
• 广度优先搜索
• 记忆化搜索
• 迭代加深搜索
• AStar
• IDA*
• Meet In The Middle
• 爬山算法
• 模拟退火

老师甚至讲了dfs爆搜最短路， dfs爆搜全宇宙……

\(DFS\)

DFS求解图中环

记录vis数组，查找是否重复访问节点（记录是否入栈，即搜索过后要将vis归零）

八皇后问题

按行搜索或者按照列搜索。

NOI1999 生日蛋糕

剪枝方法：

• 最优化剪枝：如果在当前情况下已经累计得到的表面积大于当前拥有的答案，就停止搜索
• 当前的体积大于题目要求，则停止搜索
• 当前体积+之后最大的体积小于要求的体积，则返回
• 枚举开始的边界：这层的半径和高是上层开始还剩下的层数

\(BFS\)

老师讲了单源最短路径（？）

单源最短路径\(\rightarrow\)多源最短路经有一种方法：同时将多个起点入队。

“给定一个图，每条边的边权为0或者1，如何用广度优先搜索求单源最短路？”

• 双端队列：把零从队首拓展，把一从队尾拓展

[HAOI2008] 移动玩具

状压+构图+连边+最短路

记忆化搜索：适合拓扑序下的DP

#QBXT2020十一 Day1 上课笔记

原文：https://www.cnblogs.com/Cao-Yucong/p/13758991.html