蓝桥杯备赛3.11

搜索

B3622 枚举子集（递归实现指数型枚举） - 洛谷

#include <bits/stdc++.h> using namespace std; int n; string path; void dfs(int pos) { if(pos > n) { //path 就存着前n个人的决策 cout << path << endl; return; } //不选 path += 'N'; dfs(pos + 1); path.pop_back();//回溯 清空现场 //选 path += 'Y'; dfs(pos + 1); path.pop_back();//清空现场 } int main() { cin >> n; dfs(1); return 0; }

P10448 组合型枚举 - 洛谷

#include <bits/stdc++.h> using namespace std; const int N = 1e3; int n,m; vector<int> path; void dfs(int begin) { if(path.size()==m) { for(auto &x:path) { cout << x << " "; } cout << endl; return ; } for(int i = begin;i <= n;++i) { path.push_back(i); dfs(i + 1); path.pop_back(); } } int main() { cin >> n >> m; dfs(1); return 0; }

B3623 枚举排列（递归实现排列型枚举） - 洛谷

#include <bits/stdc++.h> using namespace std; const int N = 1e3; int n,k; vector<int> path; bool st[15]; void dfs() { if(path.size()==k) { for(auto &x:path) { cout << x <<" "; } cout << endl; return; } for(int i = 1;i <= n;++i) { if(!st[i]) { path.push_back(i); st[i] = true; dfs(); st[i] = false; path.pop_back(); } } } int main() { cin >> n >> k; dfs(); return 0; }

P1706 全排列问题 - 洛谷

#include <bits/stdc++.h> using namespace std; const int N = 10; int n; vector<int> path; bool st[N]; void dfs() { if(path.size()== n) { for(auto &x:path) { printf("%5d",x); } cout << endl; return; } for(int i = 1;i <= n;++i) { if(!st[i]) { path.push_back(i); st[i] = true; dfs(); st[i] = false; path.pop_back(); } } } int main() { cin >> n; dfs(); return 0; }

P1036 [NOIP 2002 普及组] 选数 - 洛谷

#include <bits/stdc++.h> using namespace std; const int N = 25; int n,k; int ret; int path; int a[N]; bool isPrime(int x) { if(x < 2) return false; if(x == 2) return true; for(int i = 2;i <= x/i;++i) { if(x%i==0) return false; } return true; } void dfs(int pos,int begin) { if(pos > k) { if(isPrime(path)) ret++; return; } for(int i = begin;i <= n;++i) { path +=a[i]; dfs(pos + 1,i + 1); path -=a[i]; } } int main() { cin >> n >> k; for(int i = 1;i <= n;++i) { cin >> a[i]; } dfs(1,1); cout << ret; return 0; }

P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷

#include <bits/stdc++.h> using namespace std; const int N = 15; int t[N],d[N],l[N]; int T; int n; bool st[N]; bool dfs(int pos,int end) { if(pos > n) { return true; } for(int i = 1;i <= n;++i) { if(st[i]==true) continue; if(end > t[i] + d[i]) continue; int newend = max(end,t[i]) + l[i]; st[i] = true; if(dfs(pos + 1,newend)) return true; st[i] = false; } return false; } int main() { cin >> T; while(T--) { memset(st,false,sizeof st); cin >> n; for(int i = 1;i <= n;++i) { cin >> t[i] >> d[i] >> l[i]; } if(dfs(1,0)) cout <<"YES" << endl; else cout << "NO" << endl; } return 0; }