搜索小结

搜索概述

搜索问题的解,其实就是在问题对应的状态空间中进行映射与遍历. 使用递归,循环,数据结构等对状态空间的单调性,对称性,有解性进行排列归纳,加以搜索,以快速找到问题的答案

LuoguP1120 小木棍

DFS 剪枝,在洛谷的毒瘤时间范围下,剪枝剪到吐血。

搜索框架

如果采用向每个木棍填充木棍的方式,则超时

采用一个接一个拼木棍的方式,拼好一个,再拼下一个。

表示正在拼第 stick 根木棍,已拼的长度为 len.

可行性剪枝

枚举木棍长度时,从数列最大值枚举木棍长度到数列的和的一半,如果超过长度直接输出数列和

数组从大到小排序,优先选长的,以更快趋近边界(木棍顺序的等效性)

搜索时的木棍长度小于等于上一根木棍的长度(长度递减)(框架改为

等效性剪枝

长度相同的木棍不重复搜索(相同长度木棍的等效性)

如果搜索整根木棍时( )失败,就不再搜索(每根要拼凑木棍长度相同,等效)

最优性剪枝

当前长度与最短木棍的长度和都大于枚举的木棍长度,剪枝

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[70],sum,mxa;
int vis[70];
int sz;// 木棍的个数,长度
bool cmp(int a,int b){return a>b;}
void dfs(int stick,int len,int last){
    // 正在拼第 stick 根小木棍,已拼出的长度为 len,上一次选的木棍下标为 last
    if(stick*len==sum){printf("%d",sz);exit(0);}
    if(len==sz)dfs(stick+1,0,0);// 下一根
    if(sz-len<a[n])return;
    for(register int i=last+1;i<=n;i++){if(!vis[i]&&len+a[i]<=sz){// 可以使用
            vis[i]=1;
            dfs(stick,len+a[i],i);
            vis[i]=0;
            if(len+a[i]==sz||len==0)return;// 不同木棍的等效性
            while(a[i+1]==a[i])i++;// 长度相同木棍的等效性
        }
    }
    // 无解
}
int main(){scanf("%d",&n);
    for(register int i=1;i<=n;i++){scanf("%d",&a[i]);
        if(a[i]>50)--i,--n;// 过滤
        else sum+=a[i],mxa=max(mxa,a[i]);
    }
    sort(a+1,a+n+1,cmp);// 排序剪枝
    for(sz=mxa;sz<=sum/2;sz++)if(sum%sz==0)dfs(1,0,0);
    printf("%d",sum);
    return 0;
}

[NOIP2010] 引水入城

矩阵记忆化搜索

如果不能完全覆盖最后一行就输出个数

如果能,有一个小结论

对于第一行的格子所能延伸到最后一行的覆盖的区间一定连续

参见 神犇博客

于是贪心一下即可

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
const int N=503;
int n,m,tot,a[N][N],l[N][N],r[N][N];
bool vis[N][N];
void dfs(int x,int y){vis[x][y]=1;
    if(x==n)l[x][y]=min(l[x][y],y),r[x][y]=max(r[x][y],y);
    if(x>1&&a[x-1][y]<a[x][y]){if(!vis[x-1][y])dfs(x-1,y);
        l[x][y]=min(l[x][y],l[x-1][y]),r[x][y]=max(r[x][y],r[x-1][y]);
    }
    if(x<n&&a[x+1][y]<a[x][y]){if(!vis[x+1][y])dfs(x+1,y);
        l[x][y]=min(l[x][y],l[x+1][y]),r[x][y]=max(r[x][y],r[x+1][y]);
    }
    if(y>1&&a[x][y-1]<a[x][y]){if(!vis[x][y-1])dfs(x,y-1);
        l[x][y]=min(l[x][y],l[x][y-1]),r[x][y]=max(r[x][y],r[x][y-1]);
    }
    if(y<m&&a[x][y+1]<a[x][y]){if(!vis[x][y+1])dfs(x,y+1);
        l[x][y]=min(l[x][y],l[x][y+1]),r[x][y]=max(r[x][y],r[x][y+1]);
    }
}
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    memset(l,0x3f,sizeof(l));
    for(int i=1;i<=m;i++)dfs(1,i);
    for(int i=1;i<=m;i++)tot+=vis[n][i];
    if(tot<m)return printf("0\n%d",m-tot),0;
    pii p[N];
    for(int i=1;i<=m;i++)p[i].first=l[1][i],p[i].second=r[1][i];
    sort(p+1,p+m+1);
    int c=1,pre=0,ans=0;// 已被覆盖的城市
    while(pre<m){int cur=0;
        while(p[c].first<=pre+1)cur=max(p[c].second,cur),++c;
        pre=cur,ans++;
    }
    printf("1\n%d",ans);
    return 0;
}

[NOIP2011]Mayan 游戏

非常模拟的暴搜

非常强的代码复杂度

首先采用 DFS 搜索的方式,按字典序枚举,优先向右移动,再剪几个枝,再来几个玄学优化……

剪枝

  1. 如果某一个颜色的总数量小于 3,则不可能消完
  2. 对于所有的左移操作,当这两个方块都存在的时候,是可以用字典序更小的右移来代替的;所以仅当左边的方块为空,或者处在右边缘的位置的时候,才选择左移。

莫名其妙的优化

  1. exit 代替 return,避免回溯
  2. 本题中所有的数字均不超过 100,可以用 char 代替 int(内存空间小的变量运行时间更快?!!)

代码框架

放一个阉割版的代码,方便理解

#include<cstdio>
#include<cstdlib>
using namespace std;
char n;
struct game{char a[5][7];
    bool drop(){}// 方块下落,如果局面有变动,返回 1
    bool over(){}// 判断游戏是否无解(剪枝)
    bool win(){}// 判断游戏是否胜利(全 0)
    bool erase(){}// 消除,如果有方块变动就返回 1
    void left(char x,char y){}// 左移,并消除,下落
    void right(char x,char y){}// 右移,并消除,下落 };// 所有成员函数直接在 a 数组上修改
game g;
char ans[10][3];// 保存答案
void dfs(game cur,char k){// 目前的局面,当前的步数
    if(cur.over())return;// 剪枝 1
    if(cur.win()){for(char i=1;i<k;i++)printf("%hhd %hhd %hhd[n",ans[i][0],ans[i][1],ans[i][2]);
        exit(0);// 退出程序,包含在 <stdlib>
    }
    if(k>n)return;//k>n 且 cur.win()==0,则回溯
    for(char i=0;i<5;i++)for(char j=0;j<7&&cur.a[i][j];j++){// 按字典序枚举
        if(i<4){// 先右移
            game nex=cur;
            nex.right(i,j);
            ans[k][0]=i,ans[k][1]=j,ans[k][2]=1;// 记录答案
            dfs(nex,k+1);
        }
        if(i==4||(i>0&&!cur.a[i-1][j])){
            game nex=cur;
            nex.left(i,j);
            ans[k][0]=i,ans[k][1]=j,ans[k][2]=-1;
            dfs(nex,k+1);
        }
    }
}
int main(){scanf("%hhd",&n);//%hhd 读入 signed char
    for(char i=0;i<5;i++)for(char j=0,x;~scanf("%hhd",&x)&&x;j++)g.a[i][j]=x;// 读入
    dfs(g,1);// 如果有解就会直接退出程序
    puts("-1");// 否则输出 -1
    return 0;
}

完整代码

#include<cstdio>
#include<cstdlib>
#define swap(a,b) (a^=b^=a^=b)
using namespace std;
char n;
struct game{char a[5][7];
    bool drop(){// 方块下落,如果局面有变动,返回 1
        bool res=0;
        for(char i=0;i<5;i++)for(char j=0,p=0;j<7;j++){while(p<7&&a[i][p]==0)++p;
            if(p>=7)break;// 没有需要 drop 的方块
            if(p!=j)a[i][j]=a[i][p],a[i][p]=0,res=1;
            else ++p;
        }
        return res;
    }
    bool over(){// 判断游戏是否无解(剪枝)
        char tmp[12]={0};
        for(char i=0;i<5;i++)for(char j=0;j<7&&a[i][j];j++)++tmp[a[i][j]];
        for(char i=1;i<=10;i++)if(tmp[i]&&tmp[i]<3)return 1;
        return 0;
    }
    bool win(){for(char i=0;i<5;i++)if(a[i][0])return 0;
        return 1;
    }
    bool erase(){// 消除,如果有消除就返回 1
        bool res=0;
        do{bool e[5][7]={{0}};
            for(char i=0;i<5;i++)for(char j=0;j<7&&a[i][j];j++){if(j<5&&a[i][j]==a[i][j+1]&&a[i][j]==a[i][j+2])e[i][j]=e[i][j+1]=e[i][j+2]=1;
                if(i<3&&a[i][j]==a[i+1][j]&&a[i][j]==a[i+2][j])e[i][j]=e[i+1][j]=e[i+2][j]=1;
                if(e[i][j])a[i][j]=0,res=1;// 之后不会再遍历 a[i][j]
            }
        }while(drop());// 如果局面变动,继续循环,直到没有变动
        return res;
    }
    void left(char x,char y){// 左移,(x,y)<->(x-1,y)
        if(x==0)return;// 不可能左移
        swap(a[x][y],a[x-1][y]);
        drop();erase();
    }
    void right(char x,char y){if(x==4)return;
        swap(a[x][y],a[x+1][y]);
        drop();erase();
    }
};
game g;
char ans[10][3];
void dfs(game cur,char k){if(cur.over())return;
    if(cur.win()){for(char i=1;i<k;i++)printf("%hhd %hhd %hhd[n",ans[i][0],ans[i][1],ans[i][2]);
        exit(0);// 退出程序
    }
    if(k>n)return;//k>n 且 cur.win()==0,则回溯
    for(char i=0;i<5;i++)for(char j=0;j<7&&cur.a[i][j];j++){if(i<4){
            game nex=cur;
            nex.right(i,j);
            ans[k][0]=i,ans[k][1]=j,ans[k][2]=1;
            dfs(nex,k+1);
        }
        if(i==4||(i>0&&!cur.a[i-1][j])){
            game nex=cur;
            nex.left(i,j);
            ans[k][0]=i,ans[k][1]=j,ans[k][2]=-1;
            dfs(nex,k+1);
        }
    }
}
int main(){scanf("%hhd",&n);
    for(char i=0;i<5;i++)for(char j=0,x;~scanf("%hhd",&x)&&x;j++)g.a[i][j]=x;
    dfs(g,1);
    puts("-1");
    return 0;
}

[2017 清华集训』小 Y 和地铁

第一次 AC 如此难度的题,高兴的语无伦次……
这其实是一道很玄学的题

分析

其实这道题的地铁显然是可以随便乱建的,只考虑相对位置关系。

因此,只出现了一次一个换乘站的线路,直接忽略(假装地铁长度为 1 纳米……)

剩下的换乘站显然两两配对。对于地铁的线路,题目的样例就给了你很玄学的绕法,事实上,绕法一共有八种:
p4

直接暴搜,期望得分28-32分。

一剪

可以发现 1 和 2 是有重复的 “嫌疑” 的,只用考虑其中一种。可是如何确切证明呢?

将地铁周围的空间分为六个部分,我们发现,在图 1 中:(1)(2) 以及 (2)(3) 都被地铁分开了,相比之下,(1)(4) 和 (4)(5) 和 (5)(6) 和 (3)(6) 是没有被分开的。再看图 2,与图 1 是一样的。因此两者只需考虑一种。
p1

同理,5,6 中也只用考虑一种。于是就只剩下了 6 种情况。

那么对于 3,4 和 7,8 呢?同样根据上面的证明,也可以再排出两种情况,也就只剩下 4 种情况。

现在再来搜索,期望得分40-44分。

二剪

这对于满分显然还不够,能否再剪枝?

对于剩下的 4 种情况:
p2.png

考虑一下代码的实现过程。一般来讲,应是从走到右遍历数组,一个一个寻找配对的另一个换乘站,并选择一种情况,做记录,然后继续深搜遍历,直到数组末尾。再观察 1,3,5,7,这 4 种绕法,他们都没有顾及到第一个换乘站左边的部分,因此可以把他们变成这样:
p3.png

也就是说,我们对算法的可行性部分进行剪枝,不考虑左边的部分,直接搜索右边的部分

同样的分析方法 1,7 等价,3,5 等价。至此,剪枝为 2 种情况,期望得分100分。

关于代码实现

那难道我们直接考虑 1,5 两种情况搜索?显然不正确(比如样例 2).

对之前 8 种情况减到 4 种情况的剪枝是毋庸置疑的,而对这 4 种情况的剪枝是不同的。抽象一下,其实 1,7 两种情况相当于在 (1)(2) 之间隔了一条地铁线,其他的不影响;同理,3,5 两种情况相当于在 (3)(4) 之间隔了一条地铁线。

图 1 和图 7 等价的原因在于,他们对于后续搜索的影响是等价的。也就是说,你选 1 或 7,对于后面搜索的结果是没有区别的。为什么?

假设后续搜索中遇到的两个成对换乘站的位置:

  • 两个都在 (1)(3) 之间,则对于图 1 或图 7,用这 4 种情况中等价的绕法(比如一个用 1,一个用 7;或者一个用 5;一个用 5,一个用 3;或都用 1,都用 5……),可以同时做到 0 个交点(即多余的换乘站)
  • 一个在 (1)(3) 之间,一个在 (2)(4) 之间,用等价的绕法,可以同时做到 0 个交点(分别用 1,7 或 3,5)
  • 都在 (2)(4) 之间,同理可证。

显然,对于后续的搜索,可以做到等价且不影响最优解。因此 1,7 以及 3,5 在抽象上是等价的,只用选择其中最优的一个当作搜索的选择即可。

说得直接一点,将 1,7 归为一种情况,是因为他们对后续搜索的结果没有影响。而 1,7 两种情况都要考虑的原因,是因为他们受之前搜索的影响

实在不懂,画几个样例尝试一下……

当然,不要忘了常规剪枝(对答案的剪枝)

代码

#include<bits/stdc++.h>
#define INF 1000
using namespace std;
int T,n,ans;
int a[100],p[100];//a[]: 原数组.p[i]: 换乘站 i 的成对的另一个换乘站的下标(在 i 的后面)。如果没有,则为 -1
int upp[100],dow[100];
//upp[i]: 表示在 1-i 换乘站中,选择情况 1 的换乘站的个数(前缀和,树状数组维护)
//dow[i]: 表示在 1-i 换乘站中,选择情况 2 的换乘站的个数(前缀和,树状数组维护)

// 树状数组的操作
int update_up(int p,int v){for(int i=p;i<=n;i+=i&-i)upp[i]+=v;}
int update_down(int p,int v){for(int i=p;i<=n;i+=i&-i)dow[i]+=v;}
int sum_up(int p){int s=0;for(int i=p;i>0;i-=i&-i)s+=upp[i];return s;}
int sum_down(int p){int s=0;for(int i=p;i>0;i-=i&-i)s+=dow[i];return s;}

int search(int k,int s){// 第 k 个换乘站,目前的解为 s
    if(k>n)return ans=min(ans,s),0;// 压行代码,更新解 + 回溯
    if(s>=ans)return 0;// 常规剪枝
    int h=p[a[k]],x;//h 表示与其配对的换乘站的位置
    if(h==-1||h==k)return search(k+1,s),0;// 没有成对或着已经被搜素过了,就直接搜索下一个,最后直接返回
    // 在 (1)(2) 之间隔一道地铁线,考虑 1,7 两种情况。
        //1:sum_up[h]-sum_up[k] ,7:sum_up[n]-sum_up[h]+sum_down[n]-sum_down[k],
        x=min(sum_up(h)-sum_up(k),sum_up(n)-sum_up(h)+sum_down(n)-sum_down(k));
        update_up(h,1);
        search(k+1,s+x);
        update_up(h,-1);
    // 在 (3)(4) 之间隔一道地铁线,考虑 5,3 两种情况。
        //5:sum_down[h]-sum_down[k] ,3:sum_down[n]-sum_down[h]+sum_up[n]-sum_up[k],
        x=min(sum_down(h)-sum_down(k),sum_down(n)-sum_down(h)+sum_up(n)-sum_up(k));
        update_down(h,1);
        search(k+1,s+x);
        update_down(h,-1);
}
int main(){scanf("%d",&T);
    while(T--){scanf("%d",&n);
        ans=INF;
        for(int i=0;i<=n;i++)upp[i]=dow[i]=a[i]=p[i]=0;
        for(int i=1;i<=n;i++){scanf("%d",&a[i]);
            if(p[a[i]]==-1)p[a[i]]=i;
            else p[a[i]]=-1;
        }
        search(1,0);
        printf("%d\n",ans);
    }
    return 0;
}

  转载请注明: Sshwy's Blog 搜索小结

 上一篇
二分小结 二分小结
二分概述二分不同于分治,它根据问题的单调维度求解的特点,在该维度上折半查找答案,使复杂度系数由 降低到 . [TJOI2007] 路标设置求最大距离的最小值,典型的二分答案 #include<bit
2018.12.19
下一篇 
单调队列小结 单调队列小结
单调队列故名思义,单调队列旨在维护一个队列,其中元素始终以某一关键字单调的顺序排列 单调队列的思想广泛用于最优解的维护,用于优化 1D/1D 动态规划 朝花中学 OI 队的奋斗历程——浅谈单调队列 [NOIP2016] 蚯蚓优先队列每次取最
2018.12.19
  目录