当前位置: 首页 > news >正文

2024算法基础公选课练习三(DFS1)(1)

一、前言

dfs是初学者的重点,也是难点,这次的有些题目也不好写。题目有点多,因此分成(1)和(2)

二、题目总览

三、具体题目

3.1 问题 A: 贪心——排队接水

思路

贪心,把接水时间短的往前排,输出排序前的下标,然后用前缀和除以n

我的代码

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int n;std::cin >> n;std::vector<pii> v(n+1);std::vector<int> pre(n+1,0);for(int i = 1;i<=n;++i){int num;std::cin >> num;v[i] = {num,i};} std::sort(v.begin()+1,v.begin()+1+n);for(int i = 1;i<=n;++i){std::cout << v[i].second << " \n"[i==n];pre[i] = pre[i-1]+v[i].first;}i64 sum = 0;for(int i = 1;i<=n;++i){sum+=pre[i];}std::cout << std::fixed << std::setprecision(2) << (1.0*sum/n) << '\n';return 0;
}

3.2 问题 B: 贪心——最大整数

思路

贪心,用string存储数字,排序后拼接即可,注意排序的思路

我的代码

#include <bits/stdc++.h>
using i64 = long long;int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int n;std::cin >> n;std::vector<std::string> v(n+1);for(int i = 1;i<=n;++i){std::cin >> v[i];}std::sort(v.begin()+1,v.begin()+1+n,[&](const std::string &s1,const std::string &s2){return s1+s2>s2+s1;});for(int i = 1;i<=n;++i){std::cout << v[i];}std::cout << '\n';return 0;
}

3.3 问题 C: 搜索与回溯——全排列问题

思路

next_permutation直接秒了

我的代码

#include <bits/stdc++.h>
using i64 = long long;int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int n;std::cin >> n;std::vector<int> v;for(int i = 0;i<n;++i){v.emplace_back(i+1);} do{for(int i = 0;i<n;++i){std::cout << v[i] << " \n"[i==n-1];}}while(std::next_permutation(v.begin(),v.end()));return 0;
}

3.4 问题 D: 搜索与回溯——组合的输出

思路

写dfs时注意判断当前位置u的范围

我的代码

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 25;int n,r;
std::vector<bool> vis(N,false);
std::vector<int> a(N,0);
void dfs(int u,int st) {if(u>r) {for(int i = 1;i<=r;++i) {std::cout << a[i] << " \n"[i==r];}return;}for(int i = st;i<=n;++i) {if(vis[i]) continue;vis[i] = true;a[u] = i;dfs(u+1,i+1);vis[i] = false;}
}
int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::cin >> n >> r;dfs(1,1);return 0;
}

3.5 问题 E: 搜索与回溯——输出组合2

思路

同理,注意范围,这个题其实比上个题简单

我的代码

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 25;int n,r;
std::vector<bool> vis(N,false);
std::vector<int> a(N,0);
void dfs(int u) {if(u>r) {for(int i = 1;i<=r;++i) {std::cout << a[i] << " \n"[i==r];}return;}for(int i = 1;i<=n;++i) {if(vis[i]) continue;vis[i] = true;a[u] = i;dfs(u+1);vis[i] = false;}
}
int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::cin >> n >> r;dfs(1);return 0;
}

3.6 问题 F: 因子全排列

思路

先暴力找因子(因为只找<10的因子),再用next_permutation输出全排列

我的代码

#include <bits/stdc++.h>
using i64 = long long;int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int n;std::cin >> n;std::vector<int> fac;for(int i = 1;i<10;++i){if(n%i==0){fac.emplace_back(i);}} std::sort(fac.begin(),fac.end());do{for(int i = 0;i<fac.size();++i) std::cout << fac[i] << " \n"[i==fac.size()-1];}while(std::next_permutation(fac.begin(),fac.end()));return 0;
}

3.7 问题 G: 卡片2

思路

dfs找到全部n取出k种的情况,然后把每种情况求sum后丢到set中,最后输出set的size即可

我的代码

#include <bits/stdc++.h>
using i64 = long long;
int n,k;
std::set<int> set;
std::vector<int> a;
std::vector<bool> vis;
void dfs(int u,int sum){if(u==k+1){set.insert(sum);return;}for(int i = 1;i<=n;++i){if(vis[i]) continue;vis[i] = true;dfs(u+1,sum+a[i]);vis[i] = false;}
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);std::cin >> n >> k;a.resize(n+5,0);vis.resize(n+5,false);for(int i = 1;i<=n;++i){std::cin >> a[i];} dfs(1,0);std::cout << set.size() << '\n';return 0;
}


http://www.mrgr.cn/news/74744.html

相关文章:

  • 使用 前端技术 创建 QR 码生成器 API1
  • Redis 性能优化 18招
  • 大数据新视界 -- 大数据大厂之 Hive 数据导入:多源数据集成的策略与实战(上)(3/ 30)
  • Spark RDD 的宽依赖和窄依赖
  • 力扣刷题--21.合并两个有序链表
  • AOC显示器915Sw按键失灵维修记
  • 全国交通安全日知识竞赛答题投票活动策划
  • 基于AX650N/AX630C部署多模态大模型InternVL2-1B
  • 华为OD机试真题---数组二叉树
  • C# 反射与动态编程
  • arcgis做buffer
  • LeetCode105.从前序与中序遍历构造二叉树
  • 上海亚商投顾:创业板指探底回升 两市成交额缩量5400亿
  • 云计算研究实训室建设方案
  • 蓝桥杯真题——k倍区间
  • 【性能优化】图片性能优化方案
  • Python 绘图工具详解:使用 Matplotlib、Seaborn 和 Pyecharts 绘制散点图
  • 基于Springboot+微信小程序的付费选座自习室小程序 (含源码数据库)
  • JavaScript 对象
  • fpga开发-存储器及其应用
  • 图像识别
  • AI开发-三方库-PyTorch-Matplotlib
  • TLP2361光耦器:为高速、高可靠性数字接口提供解决方案
  • STM32F407简单驱动步进电机(标准库)
  • 3.5MachineLearing1Chapter
  • 威联通Docker Compose搭建NAS媒体库资源工具NAS Tools