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