当前位置： 首页 > article >正文

蓝桥杯 3.搜索

article 2025/2/25 6:54:18

蓝桥杯 3.搜索

文章目录

  • 蓝桥杯 3.搜索
    • DFS回溯
    • DFS剪枝
    • 记忆化搜索
    • 编程66-75

DFS回溯

回溯法简介

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

image-20250218162557042

image-20250218162806703

回溯法模板

// 求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 可以省略
    }
}

// 这是一个排列型搜索树, 子集型搜索树跟这个类似, 就是在往下走的时候只有两条, 表示"选或不选当前的元素"

例题讲解

image-20250218165942338

#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;
}

image-20250218171830882

#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剪枝

简介

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

例题讲解

image-20250219211905581

#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;
}

image-20250219214259308

#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;
}

image-20250219214844893

#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){
  // 剪枝1
  if(mul > 1e5) return;
  if(dep == n + 1){
    cnt[mul]++;
    return;
  }
  // 剪枝2
  int up = pow(1e5 / mul, 1.0 / (n - dep + 1)) + 3;
  // 剪枝3
  for(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;
}

image-20250221164605428

#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

image-20250221171522028

#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;
}

image-20250221174827235

image-20250221172825029

// 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; // 0
    vis[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, 并且没有被访问, 那么就dfs
          vis[i][j] = 1;
          ans = max(ans, dfs(i, j));
        }
      }
    }
    cout << ans << "\n";
  	return 0;
}

image-20250223212457696

#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没写


http://www.kler.cn/a/559995.html

相关文章：

  • Spring Core面试题
  • MySQL数据库连接池泄露导致MySQL Server超时关闭连接
  • 硬件加速与技术创新双轮驱动：DeepSeek和ChatGPT性能进阶的未来蓝图
  • 51单片机-AT24CXX存储器工作原理
  • 深入解析 Linux 文件系统：EXT4、NTFS、NFS、CIFS 等的特点与应用（中英双语）
  • QML 将CheckBox添加到一个组，同一时间只能勾选一个，具有排他性
  • 接雨水的算法
  • 盲视观测者效应：认知的量子诗学 AI回复盲人双缝实验
  • 便携式动平衡仪Qt应用层详细设计方案（基于Qt Widgets）
  • 华为2025年技术发布会：智能汽车核心技术大爆发
  • 连接数据库的方式
  • 【JavaScript】《JavaScript高级程序设计 (第4版) 》笔记-Chapter22-处理 XML
  • Lecture 2 - Python
  • Apache Tomcat RCE 稳定复现 保姆级！(CVE-2024-50379)附视频+POC
  • JavaWeb-Servlet对象生命周期
  • 系统学习算法：专题十二 记忆化搜索
  • vue从入门到精通(十三)：收集表单数据
  • 鸿蒙开发深入浅出01（基本环境搭建、页面模板与TabBar）
  • 基于SpringBoot+Vue前后端分离的旅游信息推荐管理系统设计与实现+毕业论文+指导搭建视频
  • 深入剖析 Java Pinpoint：分布式系统性能分析的利器