一、前言
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;
}
