近期做的几道搜索题的总结
我前段时期刷紫书才发现我搜索实在是菜的一匹，近期就在做这方面的题。今天突然有觉得自己该发一篇文章了，于是就有了这个。
洛谷P1379 八数码难题
这道题其实并不是太难，说到这我想起了一位已经AFO搞物竞的同学花了三个月改了九个版本真正纯种暴搜最后拿了15的故事，主要难点集中在判重。这里我用的是康托展开。
康托展开是用来求在n个数的 所有排列组合中 某种排列组合的编号(就是从小到大的第几个)。
公式是
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，那么它出现在剩下的哪个组其实都一样。而如果拼接失败，则代表它拼在哪个组都不行，所以上一根就没对，直接退出。
如果当前枚举的木棍长度=剩余未拼接长度，那么把当前的这根拼上其实就转化为上面的情况了，所以同理。
总结一下所有优化：
- 事先排序，搜索时从大到小搜
- 每次枚举从上一次搜索用的下一根木棍开始搜
- 预处理
nxt[]数组，跳过重复 - 如果拼接失败，而且当前已拼接的长度为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;
}
以上。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/search-summary-201809.html