2018年9月做的几道搜索题的总结

题解 算法-搜索
编辑文章

我前段时期刷紫书才发现我搜索实在是菜的一匹,近期就在做这方面的题。今天突然有觉得自己该发一篇文章了,于是就有了这个。

洛谷P1379 八数码难题

这道题其实并不是太难,说到这我想起了一位已经AFO搞物竞的同学花了三个月改了九个版本真正纯种暴搜最后拿了15的故事,主要难点集中在判重。这里我用的是康托展开。

康托展开是用来求在n个数的 所有排列组合中 某种排列组合的编号(就是从小到大的第几个)。

公式是

$$ X=a[n] \times (n-1)! + a[n-1] \times (n-2)! +...+ a[1] \times 0! $$

a[i]表示第i个元素在未出现的元素(即第i~n位的数字中)中排列第几(也就是求后面有几个数字比ai小)

看公式其实原理就比较清楚了,下面就放个代码(求数列s的康托展开值)

inline int get_hash(int *s)
{
    int ans=0;
    for (int i=1;i<=9;i++)
    {
        int sm=0;
        for (int j=i+1;j<=9;j++)
            if (s[j]<s[i]) sm++;
        ans+=fac[8-i+1]*sm;
    }
    return ans;
}

整道题的代码我自己觉得还是很清晰的,就直接放代码吧

#include<bits/stdc++.h>
using namespace std;

struct MP{
    int s[10],id,x0,y0;
};
int vis[370005]; //vis[]始终标记的是康托展开值
int fac[]={1,1,2,6,24,120,720,5040,40320},fx[4]={0,1,0,-1},fy[4]={1,0,-1,0};
int mp[4][4],ans[10]={0,1,2,3,8,0,4,7,6,5};

inline int get_hash(int *s) //康托展开值
{
    int ans=0;
    for (int i=1;i<=9;i++)
    {
        int sm=0;
        for (int j=i+1;j<=9;j++)
            if (s[j]<s[i]) sm++;
        ans+=fac[8-i+1]*sm;
    }
    return ans;
}

inline int to_line(int x,int y) //将二维坐标转换为一维
{
    return (x-1)*3+y;
}

inline void bfs(int stx,int sty)
{
    queue <MP> q;
    MP stat;
    stat.x0=stx; stat.y0=sty;
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            stat.s[to_line(i,j)]=mp[i][j];
    stat.id=get_hash(stat.s);
    vis[stat.id]=1; //为了标记把初始值设为1,最后-1即可
    q.push(stat);
    while (!q.empty())
    {
        MP x=q.front(); q.pop();
        int mapp[10];
        for (int i=1;i<=9;i++) mapp[i]=x.s[i]; //复制一份
        for (int i=0;i<4;i++)
        {
            int tx=x.x0+fx[i],ty=x.y0+fy[i];
            if (tx>3 || tx<1 || ty>3 || ty<1) continue; //越界退出
            int newpos=to_line(tx,ty),pos=to_line(x.x0,x.y0); //当前空格的位置和将要与之交换的位置
            swap(mapp[pos],mapp[newpos]);
            int new_hash=get_hash(mapp); //得到新的康托展开值
            if (vis[new_hash])
            {
                swap(mapp[pos],mapp[newpos]); //不满足需要换回来
                continue;
            }
            bool is_ans=1; //是否找到答案
            MP y; //下面是完善拓展结点的信息
            y.x0=tx; y.y0=ty;
            y.id=new_hash;
            for (int j=1;j<=9;j++) 
            {
                y.s[j]=mapp[j];
                if (mapp[j]!=ans[j]) is_ans=0;
            }
            vis[y.id]=vis[x.id]+1; //vis[]顺便记录答案
            if (is_ans) return;
            q.push(y);
            swap(mapp[pos],mapp[newpos]);
        }
    }
}

int main()
{
    char x[10];
    int s[10];
    scanf("%s",x);
    int cnt=-1,stx,sty;
    for (int i=1;i<=3;i++)
    {
        for (int j=1;j<=3;j++)
        {
            mp[i][j]=x[++cnt]-'0';
            if (mp[i][j]==0) stx=i,sty=j; //得到初始空格位置
        }
    }
    bfs(stx,sty);
    int anshash=get_hash(ans);
    printf("%d",vis[anshash]-1); //最后-1,理由见上
    return 0;
}

洛谷P1074 靶形数独

这题其实评分虚高,于是我又打了个入门难度平衡了一下。说的好像我有不打入门难度的题一样

刚开始看这评分还以为要用特殊的搜索方法+各种剪枝,事实上纯暴搜就有70,稍微改变下搜索顺序就AC了。

就跟真正的数独一样,我们要从已经填了的数字最多的那一行开始填。所以我们事先排个序,搜索时按照从多到少的顺序搜索即可。

值得一提的是我刚开始统计填了多少个数字时根本没有判断是不是0(也就意味着每一行都一样)都得了70分,不过很玄学的是开了O2以后就爆0了。所以这道题真的很水,大概普及难度就差不多了。

#include<bits/stdc++.h>

using namespace std;

int mp[10][10],ans;
bool vis[3][10][10];//0横,1竖,2九宫格
int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
struct line{
    int num,id;
} l[10];

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

inline int nine(int x,int y) //得到所在的九宫格编号
{
    return (x-1)/3*3+(y-1)/3+1;
}

void dfs(int id,int y)
{
    int x=l[id].id; //得到从大到小第id行的行数
    if (id==10) //搜完了统计答案
    {
        int now=0;
        for (int j=1;j<=9;j++)
            for (int k=1;k<=9;k++)
                now+=mp[j][k]*score[j][k];
        ans=max(ans,now);
        return;
    }
    if (y==10) //搜到最后一列后继续搜下一行
    {
        dfs(id+1,1);
        return;
    }
    if (mp[x][y]) //已经填了,继续搜
    {
        dfs(id,y+1);
        return;
    }
    for (int i=1;i<=9;i++) //没填就填个数再搜
    {
        if (vis[0][x][i] || vis[1][y][i] || vis[2][nine(x,y)][i]) continue;
        vis[0][x][i]=1;
        vis[1][y][i]=1;
        vis[2][nine(x,y)][i]=1;
        mp[x][y]=i;
        dfs(id,y+1);
        vis[0][x][i]=0;
        vis[1][y][i]=0;
        vis[2][nine(x,y)][i]=0;
        mp[x][y]=0;
    }
    return;
}

inline bool cmp(line x,line y)
{
    return x.num>y.num;
}

int main()
{
    for (int i=1;i<=9;i++)
    {
        l[i].id=i;
        for (int j=1;j<=9;j++) 
        {
            mp[i][j]=read();
            if (mp[i][j]) l[i].num++; //统计已填个数
            vis[0][i][mp[i][j]]=1;
            vis[1][j][mp[i][j]]=1;
            vis[2][nine(i,j)][mp[i][j]]=1;
        }
    }
    sort(l+1,l+10,cmp); //从大到小排序
    ans=-1; //如果搜不到即无解就输出-1
    dfs(1,1);
    printf("%d",ans);
    return 0;
}

洛谷P1120 小木棍

练习这道题对剪枝技能的提升很大,值得一刷。

总的来说这道题就是暴搜+各种神奇的剪枝。

搜索的思路就是先得到所有木棍的总长度,然后枚举各个可能的长度即能被总长度整除的长度,并以之进行搜索。当然事先需要将所有木棍从大到小排序,这样能加快搜索速度。

于是得到纯暴搜代码:

len是当前枚举到的可能长度,num是有多少根,可以用总长度/可能长度得到,id是搜索到了第几根,sum是搜索到的当前的和
bool dfs(int len,int num,int id,int sum)
{
    if (sum==len) 
    {
        if (id==num) return 1;
        else return dfs(len,num,id+1,0);
    }
    int i=1;
    while (len-sum<s[i]) i++; //跳过放不下的
    bool can=0;
    for (;i<=n;i++)
    {
        if (vis[i]) continue;
        vis[i]=1;
        can=dfs(len,num,id,sum+s[i]);
        if (can) return 1;
        vis[i]=0;
    }
    return 0;
}

这个代码得了33分。于是考虑优化,我加了一句

if (len-sum-s[i]<mn && len!=sum+s[i]) break;

就是剩下的长度连最小的都放不下了就直接退出,相当于可以少搜索一层。现在39分了。但是后来发现这句话有些bug会导致WA于是就没用了。

我还是太菜了,只有去看题解。题解中写到当前搜索应该从上一次搜索用的下一根木棍开始搜。仔细一想,这样可以保证之前用的比后面用的木棍都大,可以去除很多重复。于是我就加了个last变量,下一次搜索从last+1开始。同时我自己还想到如果已经搜了num-1根了那么剩下的一定可以组成最后一根了,于是可以少搜一层,不过似乎并没有太大的作用。

现在搜索变成了这样:

bool dfs(int len,int num,int id,int sum,int last)
{
    if (sum==len) 
    {
        if (id==num-1) return 1; //那个并没有什么卵用的优化
        else return dfs(len,num,id+1,0,0);
    }
    bool can=0;
    int i=last+1;
    while (len-sum<s[i]) i++; //从last+1开始
    for (;i<=n;i++)
    {
        if (vis[i]) continue;
        if (len-sum-s[i]<mn && len!=sum+s[i]) break;
        vis[i]=1;
        can=dfs(len,num,id,sum+s[i],i);
        if (can) return 1;
        vis[i]=0;
    }
    return 0;
}

现在有了48分了。

我突然想到,i只是代表第几个,如果有重复的长度的话仅仅+1就会搜索很多次重复的情况。于是我事先预处理了一个nxt[]数组,表示排序后第一个与第i位不同的数在第几位:

for (int i=n-1;i;i--)
{
    if (s[i]==s[i+1]) nxt[i]=nxt[i+1];
    else nxt[i]=i+1;
}

搜索中的枚举步骤变成了这样:

while (i<=n)
{
    if (vis[i]) 
    {
        i++;
        continue;
    }
    vis[i]=1;
    can=dfs(len,num,id,sum+s[i],i);
    if (can) return 1;
    vis[i]=0;
    i=nxt[i];
}

现在57分了。我是真的没办法了,又去看了题解。接下来可谓是最重要的优化了:

对于每一次枚举,如果拼接失败,而且 当前已拼接的长度为0 或者 当前枚举的木棍长度=剩余未拼接长度 ,则停止枚举,直接退出循环。

感觉这个优化很难理解,更难想到,不过仔细想想还是比较容易理解的。

我们可以逆向来想一下。之所以退出循环,肯定是因为上一根拼的根本就不行。

如果当前已拼接的长度是0,那么当前枚举的木棍,肯定要在当前拼接的组用上。因为它必定会出现在剩下的任意一个组里,而如果当前拼接的是0,那么它出现在剩下的哪个组其实都一样。而如果拼接失败,则代表它拼在哪个组都不行,所以上一根就没对,直接退出。

如果当前枚举的木棍长度=剩余未拼接长度,那么把当前的这根拼上其实就转化为上面的情况了,所以同理。

总结一下所有优化:

  1. 事先排序,搜索时从大到小搜
  2. 每次枚举从上一次搜索用的下一根木棍开始搜
  3. 预处理nxt[]数组,跳过重复
  4. 如果拼接失败,而且当前已拼接的长度为0 或者 当前枚举的木棍长度=剩余未拼接长度 ,则停止枚举,直接退出循环
#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int s[70],len[70],n,ans,mn,nxt[70];
bool vis[70];

inline bool cmp(int x,int y)
{
    return x>y;
}

bool dfs(int len,int num,int id,int sum,int last)
{
    if (sum==len) 
    {
        if (id==num-1) return 1;
        else return dfs(len,num,id+1,0,0);
    }
    bool can=0;
    int i=last+1; //优化2
    while (len-sum<s[i]) i=nxt[i];
    while (i<=n)
    {
        if (vis[i]) 
        {
            i++;
            continue;
        }
        vis[i]=1;
        can=dfs(len,num,id,sum+s[i],i);
        if (can) return 1;
        vis[i]=0;
        if (sum==0 || sum+s[i]==len) break; //优化4
        i=nxt[i];
    }
    return 0;
}

int main()
{
    n=read();
    int cnt=0,sum=0,mx=0;
    for (int i=1;i<=n;i++)
    {
        int a=read();
        if (a>50) continue; 
        s[++cnt]=a;
        sum+=a;
    }
    n=cnt;
    sort(s+1,s+cnt+1,cmp); //优化1
    mx=s[1]; mn=s[n];
    int lcnt=0;
    for (int i=mx;i*2<=sum;i++)
    {
        if (sum%i) continue;
        len[++lcnt]=i;
    }
    nxt[n]=n+1;
    for (int i=n-1;i;i--) //优化3
    {
        if (s[i]==s[i+1]) nxt[i]=nxt[i+1];
        else nxt[i]=i+1;
    }
    ans=sum;//全部拼成一根
    for (int i=1;i<=lcnt;i++)
    {
        if (dfs(len[i],sum/len[i],1,0,0))
        {
            ans=len[i];
            break;
        }
    }
    printf("%d",ans);
    return 0;
}

洛谷P1378 油滴扩展

裸的搜索。唯一需要注意的是如果两点距离<0的话需要把最大半径取成0。还有最好全部用double,否则最大的那组数据可能有精度问题。

还有就是double输出应该用%f,cyc大佬某天WA掉就是因为用了%lf输出。

#include<bits/stdc++.h>
#define pi acos(-1)

using namespace std;

double lx,rx,uy,dy;
int cur[10],n;
struct point{
    double x,y,len;
} pt[10];
bool vis[10];

inline double dis(int x1,int y1,int x2,int y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double dfs(int x)
{
    if (x==n+1) return 0;
    double mx=0;
    for (int i=1;i<=n;i++)
    {
        if (vis[i]) continue;
        cur[x]=i;
        vis[i]=1;
        double lmax=min(min(pt[i].x-lx,rx-pt[i].x),min(pt[i].y-dy,uy-pt[i].y)); //距离四条边的最短距离
        for (int j=1;j<x;j++)
        {
            double d=dis(pt[i].x,pt[i].y,pt[cur[j]].x,pt[cur[j]].y);
            lmax=min(lmax,max(d-pt[cur[j]].len,0.0)); //距离每个点的最小距离
        }
        pt[i].len=lmax;
        double ans=pi*lmax*lmax+dfs(x+1);
        vis[i]=0;
        pt[i].len=0;
        mx=max(mx,ans);
    }
    return mx;
}

int main()
{
    scanf("%d",&n);
    double x,y,xx,yy;
    scanf("%lf%lf%lf%lf",&x,&y,&xx,&yy);
    lx=min(x,xx); rx=max(x,xx); uy=max(y,yy); dy=min(y,yy);
    for (int i=1;i<=n;i++) scanf("%lf%lf",&pt[i].x,&pt[i].y);
    double s=(rx-lx)*(uy-dy);
    printf("%.0f",s-dfs(1)); // double输出用%f!
    return 0;
}

以上。

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。