ACM笔记之搜索

常见的剪枝方法：

优化搜索顺序排除等效冗余可行性剪枝最优性剪枝记忆化

数独问题

AcWing 166. 数独

#include<bits/stdc++.h> using namespace std; char s[100]; char str[10][10]; int r[10],c[10],g[10]; //每一行每一列每个九宫格的状态 int cnt[512],num[512]; //数的二进制有多少个1,数的log值是多少 int tot; //统计'.'的数目 inline int change(int x,int y,int p) //将第x行y列的数改为p { //p = 0表示改成数字‘1’ 修改二进制的第0位 r[x] ^= (1<<p), c[y] ^= (1<<p), g[(x/3*3) + (y/3)] ^= (1<<p); } inline int lowbit(int x) { return x & (-x); } void init() //预处理得到初始状态 { tot = 0; for(int i = 0; i < 9; ++ i) { for(int j = 0; j < 9; ++ j) { str[i][j] = s[i*9 + j]; } } for(int i = 0; i < 9; ++ i) r[i] = c[i] = g[i] = (1<<9) - 1; for(int i = 0; i < 9; ++ i) { for(int j = 0; j < 9; ++ j) { if(str[i][j] == '.'){ ++tot; continue; } change(i,j, str[i][j] - '1'); } } } bool dfs(int now) { if(now == 0) return true; //枚举选项最少的点 int sml = 10,tmp; int x,y; for(int i = 0;i < 9; ++ i) { for(int j = 0;j < 9; ++ j) { if(str[i][j] != '.') continue; tmp = r[i] & c[j] & g[(i/3*3) + (j/3)]; if(!tmp) return false; //如果当前'.'没有一个数字可以填 说明不合法 if(cnt[tmp] < sml) { sml = cnt[tmp],x = i,y = j; } } } tmp = r[x] & c[y] & g[(x/3*3) + (y/3)]; for(; tmp ; tmp-=lowbit(tmp)) //枚举二进制中每一个1 { int p = num[lowbit(tmp)]; change(x,y, p); str[x][y] = p + '1'; if(dfs(now-1)) return true; change(x,y, p); //还原现场 str[x][y] = '.'; } return false; } int main() { //统计0~512二进制1的个数 for(int i = 0; i < (1<<9); ++ i) { for(int j = i; j; j -= lowbit(j)) cnt[i]++; } for(int i = 0; i < 9; ++i) num[1<<i] = i; while(~scanf("%s",s)) { if(!strcmp(s,"end")) break; init(); dfs(tot); for(int i = 0; i < 9; ++ i) printf("%s",str[i]); printf("\n"); } }

木棍问题

用一些木棍去拼一组长度相等的木棒 五种剪枝：

按木棍长度从大到小枚举木棍内部编号递增拼第一根木棍的时候失败了 那么当前方案一定不合法拼最后一根木棍的时候失败了 一定不合法跳过长度相同的木棍

AcWing 167. 木棒

#include<bits/stdc++.h> using namespace std; const int N = 65 + 2; const int M = N*50 + 2; int n; int a[N]; int len,sum; bool vis[N]; bool cmp(int x,int y) { return x>y; } //当前拼第u根木棒，已经拼了cur长度，枚举到了第st根木棍 bool DFS(int u,int cur,int st) { //printf("%d %d %d\n",u,cur,st); if((u-1)*len +cur == sum) return true; //最后一根木棒也拼好了 if(cur == len) return DFS(u+1,0,1); //拼好了当前的木棒，那么继续拼下一根木棒 for(int i=st; i<=n; ++i) { if(!vis[i] && a[i]+cur<=len) //如果当前木棍未被用 //而且 当前木棍长度拼到这根木棒上后不超过木棒的最大长度 //那么 就尝试把此木棍拼到木棒上 { vis[i] = 1; //标记木棍已用 if(DFS(u,cur+a[i],i+1)) return true; //如果在此状态下可以拼成功 那么返回true vis[i] = 0; //还原现场 //剪枝 if(!cur) return false; //拼第一根木棍的时候失败了 那么当前方案一定不合法 if(cur + a[i] == len) return false; //拼最后一根木棍的时候失败了 一定不合法 //当前木棍枚举失败 那么其后面长度相同的木棒也一定会失败 int j = i; while(j<=n && a[j]==a[i]) ++j; i = j-1; } } return false; } int main() { while(~scanf("%d",&n) && n) { sum = 0; for(int i=1;i<=n;++i) {scanf("%d",&a[i]); sum+=a[i];} sort(a+1,a+1+n,cmp); len = a[1]; fill(vis,vis+1+n,0); for(; ; ++len) { if(sum % len ==0 && DFS(1,0,1)) { printf("%d\n",len); break; } } } }

迭代加深

AcWing 170. 加成序列 满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：

1、X[1]=1

2、X[m]=n

3、X[1]<X[2]<…<X[m-1]<X[m]

4、对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得X[k]=X[i]+X[j]。

你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

#include<bits/stdc++.h> using namespace std; const int N = 110; int a[N]; int n; bool DFS(int u,int dep) { if( u == dep ) return a[dep-1] == n; //如果递归到上限层数，如果最后一个值为n即符合题意 bool vis[N] = {false}; //局部标记 for(int i=u-1;i>=0;i--)//从大到小枚举可以减少枚举次数 { for(int j=i;j>=0;j--) { int sum = a[i] + a[j]; //如果两个值的和大于当前末尾值(保证单调递增性) //而且和不超过最大值上限 //且前面没有被用过 if(sum>a[u-1] && sum<=n && !vis[sum]) { vis[sum] = 1; a[u] = sum; if(DFS(u+1,dep)) return true; } } } return false; } int main() { a[0] = 1; while(cin>>n && n) { int dep = 1; while(!DFS(1,dep)) ++dep; for(int i=0;i<dep;++i) cout<<a[i]<<" "; cout<<endl; } return 0; }

双向搜索

你搜一半，我搜一半，然后进行一些处理得到最终结果。

AcWing 171. 送礼物 求46个礼物中，最大的不超过w的礼物重量和 基本思路：拆分成两半，分别暴力，然后通过二分得到最终答案。

#include<bits/stdc++.h> using namespace std; const int N = 105, M = (1<<25) + 10; #define int long long int a[N],n,w,k; int cnt,weight[M]; int ans,len; void dfs_1(int u,int sum) { if(u == k) { //记录前一半礼物的重量和集 weight[++cnt] = sum; return; } if(a[u] + sum <= w) dfs_1(u+1,sum + a[u]); //选 dfs_1(u+1,sum); //不选 } void dfs_2(int u,int sum) { if(u == n) { int l = -1, r = len + 1; while(r-l > 1) { int mid = l + r >> 1; if(weight[mid] + sum <= w) l = mid; else r = mid; } if(weight[l] + sum <= w) ans = max(ans,weight[l] + sum); return; } if(a[u] + sum <= w) dfs_2(u+1, sum+a[u]); //选 dfs_2(u+1, sum); //不选 } signed main() { cnt = ans = 0; cin >> w >> n; for(int i = 0; i < n; ++ i) cin >>a[i]; sort(a, a + n, [](int x,int y) { return x > y; } ); k = n/2 + 2; dfs_1(0,0); //[0 ~ k-1] // for(int i = 1; i <= cnt; ++ i) cout <<weight[i] << ' '; sort(weight+1,weight+1+cnt); len = unique(weight+1,weight+1+cnt) - weight - 1; dfs_2(k,0); cout << ans << endl; }

双端队列搜索（01队列）

#include<bits/stdc++.h> using namespace std; const int N = 505; typedef pair<int,int> PII; char s[N][N]; int n,m; int dis[N][N]; int go[4][2] = { {-1,-1},{-1,1},{1,-1},{1,1} }; int to[4][2] = { {-1,-1},{-1,0},{0,-1},{0,0} }; bool check(int x,int y) { return x>=0 && x<=n && y>=0 && y<=m; } char p[] = "\\//\\"; bool bfs() { deque<PII>q; memset(dis , 0x3f , sizeof dis); q.push_back({0,0}); dis[0][0] = 0; while(q.size()) { auto t = q.front(); q.pop_front(); if(t.first == n && t.second == m) { return true; } int x = t.first, y = t.second; for(int i = 0; i < 4; ++ i) { int nx = x + go[i][0], ny = y + go[i][1]; int tx = x + to[i][0], ty = y + to[i][1]; if(check(nx,ny)) { int w = (s[tx][ty] == p[i])?0:1; if(dis[x][y] + w < dis[nx][ny]) { dis[nx][ny] = dis[x][y] + w; if(w) q.push_back({nx,ny}); //权为1 入队尾 else q.push_front({nx,ny}); //权为0 入队首 } } } } return false; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i = 0; i < n; ++ i) scanf("%s",s[i]); if(!bfs()) puts("NO SOLUTION"); else printf("%d\n",dis[n][m]); } }

广搜变形

AcWing 176. 装满的油箱

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int C = 105; // 最大油量 const int N = 1005; // 点的数量 const int M = 20005; // 边的数量 struct Point // 存每个点的状态 { int d, u, c; // d 存到这个点所花费的油钱，u 存点的编号，c 存当前还剩多少油 bool operator < (const Point &t) const // 重载小于号。按大于好反过来重载小于号，后面在建堆的时候建大根堆就可以了 { return d > t.d; } }; int n, m; int p[N], dist[N][C]; // p 存每个点上的油价，dist 存到每个被拆的点的最低油钱 int h[N], w[M], e[M], ne[M], idx; // 存图 bool st[N][C]; // 用于 dijkstra 中记录每个点是否已经出队 void add(int a, int b, int c) // 加边函数 { e[ ++ idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx; } // 求出从 start 到 end，油箱容量为 c 的最短距离。若不能到，返回 -1 inline int dijkstra(int c,int start,int end) { priority_queue<Point> heap; // 由于按大于号重载了小于号，所以建大根堆即可 memset(dist, 0x3f, sizeof dist); // 将到所有点的油钱都初始化为正无穷 memset(st, false, sizeof st); // 将 st 初始化为 false heap.push((Point){0, start, 0}); // 将 start 加入堆中 dist[start][0] = 0; // 到该点的油钱初始化为 0 while (heap.size()) { Point t = heap.top(); // 取出堆顶元素 heap.pop(); if (t.u == end) return t.d; // 如果到了 end，返回到 end 的距离 if (st[t.u][t.c]) continue; // 如果该点已经出队过，则跳过 st[t.u][t.c] = true; // 记录该点已经出队过 if (t.c < c) // 如果 t.c + 1 <= c，说明可以在该点加油，扩展一下加油的情况 if (dist[t.u][t.c + 1] > t.d + p[t.u]) // 如果这次加油后的油钱比原来的低， { dist[t.u][t.c + 1] = t.d + p[t.u]; // 那么更新原来的 heap.push((Point){dist[t.u][t.c + 1], t.u, t.c + 1}); // 该点加入堆中 } for (int i = h[t.u]; i; i = ne[i]) // 遍历该点所有能到达的点 if (t.c >= w[i]) // 如果用当前所剩的油量能到该点 if (dist[e[i]][t.c - w[i]] > t.d) // 如果这次到该点的油钱小于原来的 { dist[e[i]][t.c - w[i]] = t.d; // 那么更新原来的 heap.push((Point){t.d, e[i], t.c - w[i]}); // 将该点加入堆中 } } return -1; // 如果到不了 end，返回 -1 } int main() { scanf("%d%d", &n, &m); // 读入点数和边数 for (int i = 0; i < n; i ++ ) scanf("%d", &p[i]); // 读入每个点的油价 while (m -- ) // 读入 m 条边并建图 { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c), add(b, a, c); // 无向边 } int T; scanf("%d", &T); // 读入问题数量 while (T -- ) // 处理每个问题 { int C, S, E; scanf("%d%d%d", &C, &S, &E); int d = dijkstra(C, S, E); if (d == -1) puts("impossible"); else printf("%d\n", d); } return 0; }

AcWing 177. 噩梦

#include<bits/stdc++.h> using namespace std; #define fi first #define se second const int N = 805; typedef pair<int,int> PII; char mp[N][N]; int n,m; int st[N][N]; PII boy,girl,ghost[2]; int go[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; bool check(int x,int y,int t) { if(x<0 || x>=n|| y<0 || y>=m || mp[x][y]=='X') return false; for(int i=0;i<2;++i) { if( abs(x-ghost[i].fi) + abs(y-ghost[i].se) <= 2*t) return false; } return true; } void out(PII x) { cout<< x.fi <<' ' << x.se <<endl; } int bfs() { memset(st,0,sizeof st); queue<PII>qb,qg; while(qb.size()) qb.pop(); while(qg.size()) qg.pop(); qb.push(boy), qg.push(girl); st[boy.fi][boy.se] = 1, st[girl.fi][girl.se] = 2; ///st = 0表示男女都没走过，st=1表示男走过，st=2表示女走过 int t = 0; while(qb.size() || qg.size()) { ++t; //cout<< qb.size() <<' ' <<qg.size() <<endl; for(int i = 0; i < 3 ; ++ i) { for(int len = qb.size(); len ; --len) { auto u = qb.front(); qb.pop(); int x = u.fi, y = u.se; if(!check(x,y,t)) continue; for(int j = 0; j < 4; ++ j) { int xx = x + go[j][0], yy = y + go[j][1]; if(!check(xx,yy,t)) continue; if(!st[xx][yy]) { st[xx][yy] = 1; qb.push({xx,yy}); } else if(st[xx][yy] == 2) return t; } } } for(int i = 0; i < 1 ; ++ i) { for(int len = qg.size(); len ; --len) { auto u = qg.front(); qg.pop(); int x = u.fi, y = u.se; if(!check(x,y,t)) continue; for(int j = 0; j < 4; ++ j) { int xx = x + go[j][0], yy = y + go[j][1]; if(!check(xx,yy,t)) continue; if(!st[xx][yy]) { st[xx][yy] = 2; qg.push({xx,yy}); } else if(st[xx][yy] == 1) return t; } } } } return -1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i = 0 ; i < n; ++i ) scanf("%s",mp[i]); int cnt = 0; for(int i=0;i<n;++i) { for(int j=0;j<m;++j) { if(mp[i][j] == 'M') boy = {i,j}; else if(mp[i][j] == 'G') girl = {i,j}; else if(mp[i][j] == 'Z') { ghost[cnt++] = {i,j}; } } } int res = bfs(); cout<<res<<endl; } }