搜索
朴素搜索
NOIP2015 提高组 斗地主
搜索典题,只需按题意搜索枚举出牌方式并进行最优化剪枝即可.
细节如储存牌方式以及最后单张散牌处理.
0-1 BFS
OS:正好不知道正确性
突然想到一种方式口胡:
考虑dij实现方式:每次选距离最小的点扩展,走0边距离不增,仍在队头,只有当层被扩展完后下一层才会被取出,所以同一时间只会有2层在priority中,走1边即下一层,放在对尾即可
时间复杂度:\(O(n+m)\quad\)priority的log被干掉了
meet in the midde
双向搜索
个人口胡:大多是在复杂度为指数时食用(每增加一层状态时状态数巨量增加),效果不错(指数直接砍一半),但是必须支持可以从尾部开搜
例题:
[USACO09NOV] Lights G
n很小,可以状态压缩,可以先搜索前一半点,再搜索后一半点去拼上前一半的点
时间复杂度:\(O(2^n)\rightarrow O(2^{\frac{n}{2}})\) 按实现带log
Minimax搜索
博弈搜索
在搜到不同人时使用不同搜索策略,最大/最小化得分
例题:
[九省联考 2018] 一双木棋 chess
轮廓线数量为\(C_{n+m}^{n}\)(从左下走到右上)约\(10^5\)级别
记忆化搜索即可
轮廓线储存方式可以记录每行/列放棋子个数,hash储存
分治
平面最近点对
归并,将mid两边集合合并
设目前两集合内最小答案为d
对于每个\(P_i\),考虑可能产生最优解的\(P_j\)
\(P_j\)满足:
1.与mid距离小于d
2.比\(P_i\)纵坐标大
3.与\(P_i\)纵坐标差小于d
画一个d*2d的矩形,每矩形内最多3个点,线性时间复杂度
总时间复杂度:\(O(nlogn)\)
「XXOI 2018」暑假时在做什么？有没有空？可以来学物理吗？
关于分治解决区间问题,一般思路是先解决过中点区间,再把中点扣掉,分治处理左区间和右区间
考虑枚举右区间固定右端点,左端点为一端区间,设\(f_i=max(s_r-s_{l-1})\),每个\(f_i\)可以更新右边到mid的所有\(ans_i\),左区间同理
贪心
[POI2011] DYN-Dynamite
典,模拟赛做出来了,很顶
总结:对于每种可能情况,差啥维护啥,自底到顶更新即可