搜索专讲

搜索 讲课

作业部落

评论地址

Part 1 课件下载(预计开放时间7.20-7.25)

开放时间结束（恕不外传校内资料）

Part 2 Dancing Links

博客链接

Part 3 Meet in the middle

博客链接

题单一句话题解

题单链接

李老师给的包

• POJ1426-Find The Multiple☃☃

m不超过19位

• POJ2251-Dungeon Master☃

三维迷宫

• POJ3126-Prime Path☃

处理质数，爆搜改每一位

• POJ3278-Catch That Cow☃

广搜最短路

• POJ3414-Pots☃☃

搜索每次的操作，记录方案

• POJ1321-Chess Problem☃

八皇后

• POJ1920-Towers of Hanoi☃

暴力去移动每个柱子上的盘子

• POJ1958-Strange Towers of Hanoi☃☃

汉诺塔的递推

• POJ2488-A Knight's Journey☃

搜

• POJ3009-Curling 2.0☃

搜，记住读入是先列再行！！！调了一上午

• POJ3083-Children of the Candy Corn☃☃

走路的方向是固定的，在网上搜懂题目的意思就直接模拟就好啦

• POJ3601-Tower of Hanoi☃

汉诺塔的递推

• POJ1010-STAMPS☃☃

照着题意模拟，题意不太好懂，看看我的代码后面的注释是题意

• POJ1011-Sticks☃☃☃☃

小木棍，把后面洛谷上的kuai过来AC，题解在后面

• POJ2362-Square☃☃☃☃

太过分了，还是小木棍，题解贴在下面哈

• POJ2676-Sudoku☃

数独问题，爆搜能过，可以用Dancing Links

自己在网上找的

• [USACO07OPEN]翻转棋☃☃☃

他们说枚举第一列翻转的情况下面的就确定了
完了说好的搜索我用高斯消元做的

• [SCOI2005]栅栏☃☃☃

二分答案，然后从大往小地贪心地去加有90分，然而这个贪心显然错误，改用搜索，然后加上可行性剪枝：浪费的材料大于最大值则不行

• [luogu1784]数独☃☃

如题，类似八皇后的搜索就可以轻松AC本题
dalao想用舞蹈链也没人拦你

• [Noip2009]靶形数独☃☃☃☃

高级的数独，一般采用的方法是先搜确定点多的行或列，也算一个剪枝吧
本题也可用舞蹈链做

• [Noip2010]引水入城☃☃☃☃

用BFS处理每个临湖的城市可以处理的沙漠城市的区间，若能全部覆盖，则BFS选取最少的区间
这题值得写一写

• [JZOJ5263]分手是祝愿☃☃

区间DP，记搜会很好写，不记搜也很好写

• 油滴扩展☃☃

用next_permutation枚举放置顺序，注意对数学公式细节的处理

• 砝码称重☃☃

不知道那天的htam给你留下了怎样的心理阴影，反正我改动后放过了一种爆踩std的解法

• Hanoi双塔问题☃☃

汉诺塔系列问题，出题人为了不让你一行公式就过特意加了高精度

• 新汉诺塔☃☃☃☃

个人觉得是最难的汉诺塔问题，虽然代码很简单，核心思想就是把第$d$大的盘从$x$柱弄到$y$柱，那么$d-1$盘一定在$z$柱上，递归先把$d-1$弄到$z$柱

• 伊甸园日历游戏☃☃☃

大家都考过这道题吧，对抗搜索加记忆化，不难想但是细节多

• 虫食算☃☃☃

搜索每一个字母是什么，然后加一堆剪枝啊就过了
大家刷Noip真题应该都见过

• 小木棍［数据加强版］☃☃☃☃☃

搜索入门题 入门nmb 题解放在课件里啊
前面POJ那么多铺垫就咕咕咕啦~(≧▽≦)/~

• [NOI1999]生日蛋糕☃☃☃☃☃

搜索的剪枝，题解放在课件里啦

• [SCOI2005]骑士精神☃☃☃☃

迭代加深IDA*，题解在课件里啦

• 斗地主☃☃☃☃☃

简单模拟题：你不信去做做
偷偷告诉你，$PKUWC$也出了一道斗地主哦，$PKUSC$出了主斗地，九条可怜说还有四种排列没有用上

• Mayan游戏☃☃☃☃☃

简单模拟题：你试试就知道有多简单了
不过$Noip$题大家都做了就不写题解了

• 愤怒的小鸟☃☃☃☃

一次至少打死两头猪（两点确定一条抛物线），搜索两个点然后暴力判断其他点是否能被打到
注意下精度（真感动没看题解还一遍过）

• [HNOI2013]数列☃☃☃☃

竟然是结论题！看到搜索的标签就进来了，题解在课件里

• [NOI2005]智慧珠游戏☃☃☃☃☃

照题意模拟即可，你谷最快代码$10k$，模拟清楚就不难想了，调不出的可以找我要数据

• [HNOI2013]比赛☃☃☃☃☃

爆搜过不了，得到性质：任两支队伍的得分交换对答案没有影响
按照$N$对$1-(N-1)$,$N-1$对$1-(N-2)$这样的顺序会发现一些状态被重复搜索
排序后$Hash$然后存进$Map$就可以使用记忆化搜索进行剪枝了
一开始排个序还可以快$10$倍

• [CQOI2009]循环赛☃☃☃☃☃

上题的双倍经验题，直接把$AC$代码拿过来即可$AC$

• [hihocoder1304]搜索一·24点☃☃

模板题

• [hihocoder1308]搜索二·骑士问题☃☃

模板题

• [hihocoder1312]搜索三·启发式搜索☃☃

模板题

• [hihocoder1317]搜索四·跳舞链☃☃

模板题

• [hihocoder1321]搜索五·数独☃☃

模板题

• 算24点☃☃☃☃

这道题一定要写一写，分为六种运算符（反减反除），搜索所有情况

• [luogu1219]八皇后☃☃☃

舞蹈链精确覆盖，把每个格子作为行，四个限制条件作为列求精确覆盖，注意记录方案

• [POJ3740]Easy Finding☃☃

舞蹈链精确覆盖，照着题意模拟即可

• [HDU3498]whosyourdaddy☃☃

舞蹈链重复覆盖，照着题意模拟即可

• [FZU1686]神龙的难题☃☃

舞蹈链重复覆盖，把每个$n1×n2$的矩阵作为行，每个1的结点作为列求重复覆盖

• [HDU1109]Run Away☃☃☃

退火或者爬山，实数注意要在退火的结果附近寻找最优解

• [JSOI2004]平衡点 / 吊打XXX☃☃☃☃

退火，物理力的合成，实数注意要在退火的结果附近寻找最优解

• [HAOI2006]均分数据☃☃☃☃☃

退火构造方案，增大其调整次数

• [Luogu3936]Coloring☃☃☃☃☃

退火构造方案，增大其调整次数

• [ZJOI2008]瞭望塔☃☃☃☃☃☃

半平面交转峰函数极值，退火实现，实数退火要继续寻找最优解

• [AHOI2014/JSOI2014]宅男计划☃☃☃☃☃

首先要有一个贪心策略：知道叫外卖的次数能够活几天，然后用退火实现找外卖次数，因为外卖次数与存活天数大致呈单峰函数

• [SPOJ4580]ABCDEF☃☃

简单题，$SPOJ$用不了$map$，注意$d=0$的情况，使用$Meet\ in\ the\ middle$

• [NOI2001]方程的解数☃☃

为什么这题和上题都卡$Map$卡空间卡递归层数一定要手写二分？！
直接就是$Meet\ in\ the\ middle$的板子了

• [TopCoder14580] EllysRPS☃☃☃

你要用相同的策略和$m$个人玩$n$次石头剪刀布，你知道他们的策略，问你有多少种方法使得你与每个人玩都是平局，$m\le100,n\le25$，注意$TopCoder$采用类输出（具体在vjudge的Leaderboard上看看我代码）。
普通搜索$3^{20}$会TLE，采用双向搜索合并状态，复杂度降为$3^{10}*Map常数$，方法叫做$Meet\ in\ the\ middle$

• [BZOJ4800]Ice Hockey World Championship☃☃☃

爆搜选或不选肯定过不了，然后$2^{20}$是可以接受的，各个物品互不影响采用$Meet\ in\ the\ middle$分两边选或者不选，把$2^{20}$种情况记录的花费在数组里，运用尺取法计算答案

• [Codeforces888E]Maximum Subsequence☃☃☃

双倍经验，楼上$AC$代码改动$20$个字符即可$AC$

• [ZOJ3777] Problem Arrangement☃☃

随机一个长度为$n$的排列$P$，$val=\sum[(\sum_{i=1}^{n}A[P[i]][j])>m?1:0]$，就是所有权值大于$m$的排列的方案数$val$，求$\frac{n!}{val}$，$n\le12,m\le500$。
普通爆搜会TLE，采用$Meet\ in\ the\ middle$两边各搜一半后合并
或者使用状态压缩DP（代码量差不多，DP更符合人类思维吧。。）

• 八数码难题☃☃☃☃

康托展开后单向搜索或者双向搜索
双向搜索也是$Meet\ in\ the\ middle$的一种哦

• [九省联考2018]一双木棋chess☃☃☃☃☃

记忆化搜索，Min-Max搜索，Hash状态各种骚操作揉在一起
很难想到但是不难实现，题解在课件中了

• [luogu1763]蓄水池☃☃☃☃☃☃

搜索&容斥，计算答案用状态压缩DP完成
神仙题，具体看代码吧能懂的

• [HNOI2010]矩阵☃☃☃☃☃☃

神仙题，复杂度$10^{200}$但就是跑得过
首先发现只需要枚举$400$个位置然后递推就可以了
不难发现位置有个计算公式
于是可以给每行的头列定个范围
这样强有力的剪枝大概是$10000^2$级别了
具体看课件吧

• [luogu1254]扇区填数☃☃☃☃

只要知道了一个结论：$ans=n*(n-1)+1$
爆搜然后打表就好了
事实上，这个结论是错的，$n=7$就无法构造出这种方案了
但是通过打表可以知道这题的数据$n=(2,3,4,5,6,8)$满足这种规律

• [SCOI2010]幸运数字☃☃☃☃

爆搜每个幸运数字的倍数多少个，然后容斥，课件有详解

• [HAOI2007]反素数☃☃☃☃

知道约数的计算公式后，就可以通过搜索每个质因子出现多少次来做了

为大家准备了一些神仙题，大家可以试试，洛谷紫题黑题我太菜了不会写

• [POJ1085]Triangle War https://vjudge.net/problem/POJ-1085
• [POI1999]仓库管理员 http://cogs.pro:8080/cogs/problem/problem.php?pid=240
• [HNOI2011]任务调度 https://www.luogu.org/problemnew/show/P3212
• [SCOI2008]城堡 https://www.luogu.org/problemnew/show/P2538
• 魔法阵 https://www.luogu.org/problemnew/show/P1585
• yyy loves Maths VII https://www.luogu.org/problemnew/show/P2396
• 切孔机 https://www.luogu.org/problemnew/show/P1299
• Haywire https://www.luogu.org/problemnew/show/P2210