2022/10
主要是搜索专题的好题
洛谷 P2329 [SCOI2005]栅栏
二分+dfs
洛谷 P1120 小木棍
爆搜+剪枝
用桶存一下木棍，记录最大最小。
深搜的状态：
\(\text{sum-}\)目前拼的木棍长度
\(\text{step-}\)拼到第几根木棍
\(\text{MAX-}\) 上一个拼的值（最大边界）
剪枝：
-
从大往小拼
-
从最大的小木棍开始枚举木棍长度
-
如果遇到目前是整数个拼好的木棍，且拼不下去了，直接跳出循环
#include<bits/stdc++.h>
using namespace std;
int n,x,I,m,cnt,Sum,maxn,minn=100;
int t[100];
void dfs(int sum,int step,int MAX)
{
if(step==Sum/I)
{
printf("%d",I);
exit(0);
}
if(sum==I)
{
dfs(0,step+1,maxn);
return;
}
for(int i=MAX;i>=minn;i--)
{
if(t[i]==0||i+sum>I) continue;
t[i]--;
dfs(sum+i,step,i);
t[i]++;
if(sum==0||sum+i==I) break;
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
cnt++,t[x]++,Sum+=x;
maxn=max(maxn,x);
minn=min(minn,x);
}
for(I=maxn;I<=Sum;I++)
{
if(Sum%I!=0) continue;
dfs(0,0,maxn);
}
printf("%d",Sum);
return 0;
}
洛谷 P1763 埃及分数
迭代加深搜索
注：当输入为 570 877 时需要跑很久。
当前搜到还剩 \(\Large\frac{a}{b}\) 的时候，最大边界为 \(\Large \frac{a}{b}-\frac{1}{i}\) 即 \(\Large \frac{ai-b}{bi}\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void yf(int &x,int &y)
{
int GCD=__gcd(x,y);
x/=GCD,y/=GCD;
}
bool flag;
int minn=-1,k;
int nans[1010],ans[1010];
void dfs(int now,int a,int b,int lst) //还剩的分数个数；还剩的分数；上一个分数的分母
{
yf(a,b);
if(now==1)
{
if(a==1&&b>lst)
{
if(flag==1&&b>nans[1]) return;
flag=1,nans[1]=b;
memcpy(ans,nans,k<<5);
}
return;
}
for(int i=lst;i<=(b*now/a);i++) //边界为 a/(b*now) 的倒数(1/a/(b*now))
{
nans[now]=i;
dfs(now-1,a*i-b,b*i,i);
}
}
int x,y;
signed main()
{
cin>>x>>y;
yf(x,y);
while(!flag)
{
k++;
dfs(k,x,y,1);
}
for(int i=k;i>=1;i--) cout<<ans[i]<<" ";
return 0;
}
POJ 3322 Bloxorz
纯纯的爆搜。
几点注意事项：
-
记录开始位置的时候记得加上是否判断到过的标记，要不然会记录错位置。
-
记录 $1\times 1 \times 2 $ 小长方体的上边的或左边的正方体的位置。
-
记得注意脆弱的格子。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=517;
struct Node
{
int x,y,z;
};
queue<pair<Node,int>>q;
char map[MAXN][MAXN];
int vis[MAXN][MAXN][3];
int dis[3][4][3]=
{
{{-2,0,1},{1,0,1},{0,-2,2},{0,1,2}},
{{0,-1,1},{0,1,1},{-1,0,0},{2,0,0}},
{{0,-1,0},{0,2,0},{-1,0,2},{1,0,2}}
};
int n,m;
int sx,sy,ex,ey;
pair<Node,int> mkpair(Node x,int y)
{
return pair<Node,int>(x,y);
}
Node stNode()
{
Node tmp;
tmp.x=sx,tmp.y=sy;
if(map[sx+1][sy]=='X') tmp.z=1;
else if(map[sx][sy+1]=='X') tmp.z=2;
else tmp.z=0;
return tmp;
}
bool check(Node a)
{
if(a.x<=0||a.x>n||a.y<=0||a.y>m) return false;
if(map[a.x][a.y]=='#') return false;
if(a.z==0)
{
if(map[a.x][a.y]=='E') return false;
return true;
}
int x2=a.x,y2=a.y;
if(a.z==1) x2++;
else y2++;
if(x2<=0||x2>n||y2<=0||y2>m) return false;
if(map[x2][y2]=='#') return false;
return true;
}
bool end(Node a)
{
return a.z==0&&a.x==ex&&a.y==ey;
}
void bfs()
{
q.push(mkpair(stNode(),0));
while(!q.empty())
{
Node tmp=q.front().first;
int depth=q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
Node nxt;
nxt.x=tmp.x+dis[tmp.z][i][0],nxt.y=tmp.y+dis[tmp.z][i][1],nxt.z=dis[tmp.z][i][2];
if(check(nxt)&&!vis[nxt.x][nxt.y][nxt.z])
{
vis[nxt.x][nxt.y][nxt.z]=1;
q.push(mkpair(nxt,depth+1));
if(end(nxt))
{
printf("%d\n",depth+1);
return;
}
}
}
}
printf("Impossible\n");
}
int main()
{
while(true)
{
bool unfined=true;
scanf("%d%d",&n,&m);
if(n==0&&m==0) break;
for(int i=1;i<=n;i++)
{
scanf("%s", (map[i]+1));
for(int j=1;j<=m;j++)
{
if(map[i][j]=='X'&&unfined)
{
unfined=false;
sx=i,sy=j;
}
else if(map[i][j]=='O') ex=i,ey=j;
}
}
memset(vis,0,sizeof(vis));
while(!q.empty()) q.pop();
bfs();
}
return 0;
}