清北学堂金秋营 day1

%%%zhx

搜索

set的用法（t3判重）

#include <set>
using namespace std;
set<int> se;
int main(){
    int s;
    se.insert(s);
    if(se.count(s))
    then          zailimian
    se.erase(s);
}

结构体的set，要自己实现小于
当然能用bool数组就用bool数组

剪枝

• 最优解：超过当前最优解就return
• 可行解：玄学
• 解数量：记忆化

通用法：

• 排除不可能分支
• 玄学
• 随机化，防出题人把你卡爆（比如靶形数独，出题人把正搜卡了）

卡时

#include <ctime>
//仅用于最优解
...
int t=clock();
//返回一个从很早以前算起的时钟值，单位时钟单元
//CLOCKS_PER_SECOND为每秒的时钟单元
//1s建议设到0.85s

if(clock()-t>900)   print(), exit(0);

据说mayan游戏可以这么过，尽管笔者自己朴素地写过了

双向bfs

要求：
1. 知道终止状态
2. 终止状态的逆转移可写
3. 终止状态逆转移状态与顺转移状态数同阶（忽略本条即可）
八数码问题可用。

a*

似乎没什么卵用。

分支界定

bfs的扩展
用优先队列搞出目前最好的

迭代加深搜素

出题人卡你bfs内存咋办？
利用迭代加深，限定dfs搜索深度。
两种迭代加深的方法：
1. 枚举深度（建议）
2. 二分深度

题目

靶形数独
mayan游戏
flowfree