蓝桥杯 3.搜索

蓝桥杯 3.搜索

DFS回溯

回溯法简介

• 使用**DFS(深度优先搜索)**实现, DFS是一种遍历或搜索图, 树或者图像等数据结构的算法, 当然这个图, 树未必要存储下来(隐式处理就是回溯法)
• 搜索树一般是排列型搜索树 (总节点个数n!)和子集型搜索树(总结点个数2^n)
• DFS从起始点开始, 沿着一条路径尽可能深入的搜索, 直到无法继续为止, 然后回溯到前一个结点, 继续探索其他路径, 直到遍历完整个图或树
• DFS一般使用递归来管理节点的遍历顺序

回溯法模板

// 求1~n的全排列
int a[N];
bool vis[N];void dfs(int dep){ // 深度if(dep == n + 1){ // n层for(int i = 1; i <= n; i++){cout << a[i] << "\n";}cout << "\n";return; // 出口}for(int i = 1; i <= n; i++){ // 向下搜索// 排除不合法的路径(vis[i]是否使用过)if(vis[i]) continue;// 修改状态vis[i] = true;a[dep] = i;// 下一层dfs(dep + 1);// 恢复现场vis[i] = false;// a[dep] = 0 可以省略}
}// 这是一个排列型搜索树, 子集型搜索树跟这个类似, 就是在往下走的时候只有两条, 表示"选或不选当前的元素"

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 15;
ll n, ans; 
// 求1~n的全排列
ll a[N];
ll vis[N][N];void dfs(int dep){ // 深度if(dep == n + 1){ // n层ans++;return; // 出口}for(int i = 1; i <= n; i++){ // 向下搜索// 排除不合法的路径if(vis[dep][i]) continue;// 修改状态for(int _i = 1; _i <= n; _i++) vis[_i][i]++;for(int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--) vis[_i][_j]++;for(int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--) vis[_i][_j]++;for(int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++) vis[_i][_j]++;for(int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++) vis[_i][_j]++;// 下一层dfs(dep + 1);// 恢复现场for(int _i = 1; _i <= n; _i++) vis[_i][i]--;for(int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--) vis[_i][_j]--;for(int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--) vis[_i][_j]--;for(int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++) vis[_i][_j]--;for(int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++) vis[_i][_j]--;}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;dfs(1);cout << ans << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5+9;
ll n, a[N], dfn[N], idx, mindfn; // dfn表示时间戳int dfs(int x){dfn[x] = ++idx;if(dfn[a[x]]){if(dfn[a[x]] >= mindfn) return dfn[x] - dfn[a[x]] + 1;return 0;}return dfs(a[x]);
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];}int ans = 0;for(int i = 1; i <= n; i++){if(!dfn[i]){mindfn = idx + 1;ans = max(ans, dfs(i));}}cout << ans << "\n";return 0;
}

DFS剪枝

简介

• 将搜索过程中一些不必要的部分直接剔除掉
• 剪枝是回溯法的一种重要的优化手段

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 9;
ll n, a[N];
vector<int> v[N];// cnt表示队伍数量, dfs返回在cnt个队伍的情况下是否可以成功分组
bool dfs(int cnt, int dep){if(dep == n + 1){return true;}// 枚举每个人所属的队伍for(int i = 1; i <= cnt; i++){bool tag = true;for(const auto &j : v[i]){if(a[dep] % j == 0){tag = false;break;}}if(!tag) continue;v[i].push_back(a[dep]);if(dfs(cnt, dep + 1)) return true;// 恢复现场v[i].pop_back();}return false;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];}sort(a + 1, a + 1 + n);int ans = 0;for(int i = 1; i <= n; i++){if(dfs(i, 1)){cout << i << "\n";    break;}}return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 9;
ll n, a[5], cnt[N], prefix[N];// cnt表示队伍数量, dfs返回在cnt个队伍的情况下是否可以成功分组
void dfs(int dep, int st, int mul, int sum){// 剪枝if(mul > 1e6) return;if(dep == 4){cnt[mul]++;return;}int up = pow(1e6 / mul, 1.0 / (4 - dep)) + 3;for(int i = st + 1; i < (dep == 3 ? sum : up); i++){dfs(dep + 1, i, mul * i, sum + i);}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);dfs(1, 0, 1, 0);for(int i = 1; i <= 1e6; i++){prefix[i] = prefix[i - 1] + cnt[i];}ll t; cin >> t;while(t--){ll l, r; cin >> l >> r;cout << prefix[r] - prefix[l - 1] << "\n";}return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 9;
ll n, a[5], cnt[N], prefix[N];// cnt表示队伍数量, dfs返回在cnt个队伍的情况下是否可以成功分组
void dfs(int dep, int st, int mul, int sum){// 剪枝1if(mul > 1e5) return;if(dep == n + 1){cnt[mul]++;return;}// 剪枝2int up = pow(1e5 / mul, 1.0 / (n - dep + 1)) + 3;// 剪枝3for(int i = st + 1; i < (dep == n ? min(sum , up) : up); i++){dfs(dep + 1, i, mul * i, sum + i);}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll t; cin >> t >> n;dfs(1, 0, 1, 0);for(int i = 1; i <= 1e5; i++){prefix[i] = prefix[i - 1] + cnt[i];}while(t--){ll l, r; cin >> l >> r;cout << prefix[r] - prefix[l - 1] << "\n";}return 0;
}

记忆化搜索

简介

• 将搜索过程中会重复计算且结果相同的部分保存下来
• 通常使用数组或者map来进行记忆化, 下标一般和dfs的参数表对应

例题讲解

• 斐波那契数列

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 9;
const ll p = 1e9 + 7;
ll n, a[N], dp[N];ll f(ll n){if(n == 1 || n == 2){return 1;}if(dp[n] != -1){return dp[n];}return dp[n] = (f(n - 1) + f(n - 2)) % p;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);memset(dp, -1, sizeof(dp)); // 初始化为-1, 表示这个状态还没有被算过cin >> n;cout << f(n) << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 9;
const ll p = 1e9 + 7;
ll n, m, k, a, b, c, d, h[N][N];
ll dx[] = {0, 0, 1, -1};
ll dy[] = {1, -1, 0, 0};int dp[N][N][2];ll inmp(int x, int y){return 1 <= x && x <= n && 1 <= y && y <= m;
}bool dfs(int x, int y, int t){if(x == c && y == d){return true;}if(dp[x][y][t] != -1){return dp[x][y][t];}for(int i = 0; i < 4; i++){int nx = x + dx[i], ny = y + dy[i];if(!inmp(nx, ny)) continue;if(!t){ // 没用过背包// 不用if(h[x][y] > h[nx][ny] && dfs(nx, ny, 0)) return dp[x][y][t] = true;// 用if(h[x][y] + k > h[nx][ny] && dfs(nx, ny, 1)) return dp[x][y][t] = true;} else { // 已经用过一次背包了// 不用if(h[x][y] > h[nx][ny] && dfs(nx, ny, 1)) return dp[x][y][t] = true;}}return dp[x][y][t] = false;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);memset(dp, -1, sizeof(dp));cin >> n >> m >> k;cin >> a >> b >> c >> d;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> h[i][j];}}cout << (dfs(a, b, 0) ? "Yes" : "No") << "\n";return 0;
}

编程66-75

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 9;
ll n, d;
pair<ll, ll> a[N];
bool vis[N];
ll dist2(ll x1, ll y1, ll x2, ll y2){return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); // 两点之间的距离的平方
}void dfs(ll x){vis[x] = 1; // 第一个人肯定传染for(int i = 1; i <= n; i++){ // 枚举n个人if(dist2(a[i].first, a[i].second, a[x].first, a[x].second) > d * d) continue; // 距离大于d的平方不会被传染if(vis[i]) continue; // 标记过的不传染dfs(i); // 继续dfs}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){cin >> a[i].first >> a[i].second;}cin >> d;dfs(1);for(int i = 1; i <= n; i++){cout << vis[i] << "\n";}return 0;
}

// dfs大概模板(对于二维)
ll dx[...] = ...
ll dy[...] = ...
ll dfs(ll x, ll y){ll sum = a[x][y];for(int i = 0; i < 4; i++){ll xx = x + dx[i];ll yy = y + dy[i];if(xx < 1 || xx > n || yy < 1 || yy > m) continue; // 超出边界if(vis[xx][yy]) continue; // 已经被访问过if(...) // 其他限制条件// 剩下的就是满足的vis[xx][yy] = 1;}
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 105;
ll n, m, a[N][N], vis[N][N];
ll dx[4] = {1, 0, 0, -1}; // 下左上右
ll dy[4] = {0, 1, -1, 0};ll dfs(ll x, ll y){ // 求(x, y)整个连通块的和ll sum = a[x][y];for(int i = 0; i < 4; i++){ll xx = x + dx[i];ll yy = y + dy[i];if(xx < 1 || xx > n || yy < 1 || yy > m) continue; // 超出边界if(vis[xx][yy]) continue; // 已经被访问过if(a[xx][yy] == 0) continue; // 0vis[xx][yy] = 1;sum += dfs(xx, yy);}return sum;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> a[i][j];}}ll ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(a[i][j] && !vis[i][j]){ // a[i][j]不为0, 并且没有被访问, 那么就dfsvis[i][j] = 1;ans = max(ans, dfs(i, j));}}}cout << ans << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 105;
ll n, m, f[N];
string a, b;
struct node{ll id, x, y;
}opt[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> a >> b >> m;for(int i = 1; i <= m; i++){cin >> opt[i].id >> opt[i].x >> opt[i].y;}for(int i = 1; i <= m; i++){f[i] = i;}do{string qwq = a;for(int i = 1; i <= m; i++){if(opt[f[i]].id == 1){qwq[opt[f[i]].x] = ((qwq[opt[f[i]].x] - '0' +  opt[f[i]].y) % 10) + '0';} else {swap(qwq[opt[f[i]].x], qwq[opt[f[i]].y]);}if(qwq == b){cout << "Yes\n";return 0;}}}while(next_permutation(f + 1, f + m + 1));cout << "No" << "\n";return 0;
}

69-75没写