dfs 第一次加训 详解 下

目录

 P1706 全排列问题
思路
B3618 寻找团伙
思路
B3621 枚举元组
思路
B3622 枚举子集（递归实现指数型枚举）
思路
B3623 枚举排列（递归实现排列型枚举）
B3625 迷宫寻路
思路
P6183 [USACO10MAR] The Rock Game S
总结
P10448 组合型枚举
思路
P10483 小猫登山
思路 
P8604 [蓝桥杯 2013 国 C] 危险系数
思路
P9011 [USACO23JAN] Air Cownditioning II B
思路
P10294 [CCC 2024 J5] Harvest Waterloo
思路

---

 P1706 全排列问题

   标题形貌
  按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不答应出现重复的数字。
  输入格式
  一个整数 n。
  输出格式
  由 1∼n 组成的所有不重复的数字序列，每行一个序列。
  每个数字生存 5 个场宽。
  输入输出样例
  输入 #1复制

1. 3

复制代码

输出 #1复制

1.     1    2    3
2.     1    3    2
3.     2    1    3
4.     2    3    1
5.     3    1    2
6.     3    2    1

复制代码

阐明/提示
  1≤n≤9。
  思路

用dfs来写，其实就是n个for循环而已，比如 3个数1 2 3来进行排列 那就是for for for，然后前面的for现在的i不能被后面再用所以再来个visited，防止重新用了前面已经排的数

1. #include<bits/stdc++.h>
2. using namespace std;
3. vector<int>path;
4. vector<vector<int>>res;
5. vector<bool> visited(100000);
6. int n;
7. void dfs(){
8.         if(path.size()==n) {
9.                 res.push_back(path);
10.                 return ;
11.         }
12.         for(int i=1;i<=n;i++){
13.                 if(!visited[i]){
14.                         visited[i]=1;
15.                         path.push_back(i);
16.                         dfs();
17.                         path.pop_back();
18.                         visited[i]=0;
19.                 }
20.         }
21. }
23. int main(){
25.         cin>>n;
26.         dfs();
27.         for(auto i:res){
28.                 for(auto j:i){
29.                          printf("%5d", j); // 使用 printf 保证 5 个场宽  
30.                 }
31.                 cout<<endl;
32.         }
33. }

复制代码

---

B3618 寻找团伙

   标题形貌
  天下局面风云变幻，你想办一件大事。办事自然要有人参与，你能从 n 个人里面挑选一部分人共襄盛举。
  要办这件事，一共涉及 k 方面的本领，例如游说他人的本领、玩游戏的本领、睡觉的本领。每位人士都会具备某一些本领，例如机器猫就可能善于睡觉、善于玩游戏，而不善于游说他人。
  你的操持很宏伟，因此你渴望团队拥有很全面的本领。不幸的是，如果团队中有偶数个人拥有同一类本领，那么他们就会分成两派，辩论不下，导致整个团队丧失这方面的本领。相应地，如果这项本领只有奇数个人拥有，那么他们总能形成一个多数派，帮团队去做这方面的工作。
  需要注意的是，团队拥有的每一项本领，对操持的成功率的贡献是不一样的。第一项本领最重要，它的权重是 2k−1；第二项本领的权重是 2k−2；依次类推。第 k 项本领最不重要，权重只有 1。
  操持的成功率得分，便是团队拥有的所有本领对应的权重之和。
  你渴望操持成功率最大。因此，你需要选出符合的人士，来参与到你的宏图伟业中。
  输入格式
  第一行，两个正整数 n,k。分别表示供你挑选的人的数量，以及本领的种类数。
接下来 n 行，每行表示每个人拥有的本领。这一行首先有一个整数 c，表示该人士拥有多少种本领；接下来是 c 个 [1,k] 之间的正整数，表示该人士拥有哪些本领。
  输出格式
  仅一行，一个整数，表示操持的成功率得分。
  
  输入输出样例
  输入 #1复制

1. 5 5
2. 1 1
3. 1 2
4. 1 3
5. 1 4
6. 1 5

复制代码

输出 #1复制

1. 31

复制代码

输入 #2复制

1. 3 5
2. 3 1 2 3
3. 4 2 3 4 5
4. 2 3 4

复制代码

输出 #2复制

1. 28

复制代码

输入 #3复制

1. 3 5
2. 2 1 2
3. 3 5 3 2
4. 3 4 2 5

复制代码

输出 #3复制

1. 30

复制代码

输入 #4复制

1. 21 60
2. 0
3. 0
4. 3 60 27 48
5. 0
6. 1 48
7. 2 52 14
8. 2 4 31
9. 0
10. 0
11. 2 28 43
12. 2 6 31
13. 0
14. 1 7
15. 3 45 6 48
16. 0
17. 1 51
18. 0
19. 2 28 20
20. 2 37
21. 51
22. 1 8
23. 53 59 39 29 23 53 27 13 16 44 34 38 24 9 32 58 54 31 1 7 45 3 30 36 17 48 42 22 18 21 6 11 25 33 37
24. 52 10 60 49 57 2 28 8 14 5 47 4 41 35 43 50 46 26 12

复制代码

输出 #4复制

1. 115288
2. 4121210322895

复制代码

阐明/提示
  样例解释
  第一组样例，共 5 个人，每个人拥有的本领不一样。最终选择的效果是让这 5 个人都参与操持，得分 16+8+4+2+1=31。
  第二组样例，我们选择只让 1 参与。那么团队具有本领 1,2,3，得分 16+8+4=28。
  第三组样例，我们让 1,2,3 参与。由于团队中有偶数个成员拥有本领 5，故团队并不拥有本领 5。奇数个成员拥有本领 2，故团队拥有本领 2。最终，团队具有本领 1,2,3,4。得分 16+8+4+2=30。
  数据规模与约定
  对于 100% 的数据，有 n≤21,k≤60。
  思路

很显着就是选或不选某个人呗，然后搞个ans全局变量纪录答案，当每个人都搜索一遍后就ans搞一下，看看每个方案哪个ans最大就ok，这是团体思路，，，里面还需要一些位运算，好吧这个位运算的是看的题解，

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. ll n, k, a[21+10], ans;
5. void dfs(ll i,ll now) {
6.         if(i>n) {//都搜索过一遍后
7.                 ans=max(ans,now);
8.                 return;
9.         }
10.         //异或的性质就是相同为0，不同为1，那相同就是偶数，奇数就是不同，
11.         //eg.比如选了1和3 那这个人的能力值就是101，另一个只选了3那就是100异或后就是001，正好符合题目要求
12.         dfs(i+1,now^a[i]);//选这个人，抑或上他的分值,用来异或就不用再多考虑奇数偶数情况，因为上面说了异或的性质
13.         dfs(i+1,now);//不选
14. }
15. int main(){
16.         cin>>n>>k;//n个人，k个能力
17.         for(ll i=1;i<=n;i++){
18.                 int c;
19.                 cin>>c;
20.                 for(ll j=1;j<=c;j++) {
21.                         int x;
22.                         cin>>x;
23.                         a[i]|=(1ll<<(k-x)); //记录二进制分值，等价于a[i] += (1ull << (k - x))或a[i] += (1ull * pow(2, k - x))
24.                 }
25.         }
26.         dfs(0,0);//第一个参数是第几号人，因为第一个人也要判断选或不选，所以从0开始，
27.         //第二个参数是当前的团伙的总能力值
28.         cout << ans;
29.         return 0;
30. }

复制代码

---

B3621 枚举元组

   标题形貌
  n 元组是指由 n 个元素组成的序列。例如 (1,1,2) 是一个三元组、(233,254,277,123) 是一个四元组。
  给定 n 和 k，请按字典序输出全体 n 元组，此中元组内的元素是在 [1,k] 之间的整数。
  「字典序」是指：优先按照第一个元素从小到大的次序，若第一个元素相同，则按第二个元素从小到大……依此类推。详情参考样例数据。
  输入格式
  仅一行，两个正整数 n,k。
  输出格式
  若干行，每行表示一个元组。元组内的元素用空格隔开。
  输入输出样例
  输入 #1复制

1. 2 3

复制代码

输出 #1复制

1. 1 1
2. 1 2
3. 1 3
4. 2 1
5. 2 2
6. 2 3
7. 3 1
8. 3 2
9. 3 3

复制代码

输入 #2复制

1. 3 3

复制代码

输出 #2复制

1. 1 1 1
2. 1 1 2
3. 1 1 3
4. 1 2 1
5. 1 2 2
6. 1 2 3
7. 1 3 1
8. 1 3 2
9. 1 3 3
10. 2 1 1
11. 2 1 2
12. 2 1 3
13. 2 2 1
14. 2 2 2
15. 2 2 3
16. 2 3 1
17. 2 3 2
18. 2 3 3
19. 3 1 1
20. 3 1 2
21. 3 1 3
22. 3 2 1
23. 3 2 2
24. 3 2 3
25. 3 3 1
26. 3 3 2
27. 3 3 3

复制代码

阐明/提示
  对于 100% 的数据，有 n≤5,k≤4。
  思路

可以注意到输出的类似于全排列，但是他能输出 1 1,2 2，3 3阐明for for两个前面的for用了一个数后后面还可以用，那我们就不需要visited数组来保证一个数只用一次了，比前面的谁人全排列还要简朴，只要记着dfs里面的basecase是path.size()==n就好，看代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,k;
4. vector<vector<int>>res;
5. vector<int>path;
6. bool visited[6];//不需要用到
7. void dfs(){
8.         if((int)path.size()==n){
9.                 res.push_back(path);
10.                 return ;
11.         }
12.         for(int i=1;i<=k;i++){
13.                         path.push_back(i);       
14.                         dfs();
15.                         path.pop_back();
16.                 }
17.         }
19. int main(){
20.         cin>>n>>k;
21.         dfs();
22.         for(auto i:res){
23.                 for(auto j:i){
24.                         cout<<j<<' ';
25.                 }
26.                 cout<<endl;
27.         }
28. }

复制代码

---

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

   标题形貌
  今有 n 位同砚，可以从中选出任意名同砚参加合唱。
  请输出所有可能的选择方案。
  输入格式
  仅一行，一个正整数 n。
  输出格式
  若干行，每行表示一个选择方案。
  每一种选择方案用一个字符串表示，此中第 i 位为 Y 则表示第 i 名同砚参加合唱；为 N 则表示不参加。
  需要以字典序输出答案。
  输入输出样例
  输入 #1复制

1. 3

复制代码

输出 #1复制

1. NNN
2. NNY
3. NYN
4. NYY
5. YNN
6. YNY
7. YYN
8. YYY

复制代码

阐明/提示
  对于 100% 的数据，保证 1≤n≤10。
  思路

依旧是for for for组成，我们只要搞个数组里面放Y N，然后遍历，然后递归层数就是由n决定，当存了n个for后就行，依旧不需要visited数组

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n;
4. char a[2]{'Y','N'};
5. vector<string>res;
6. string path;
7. void dfs(){
8.         if((int)path.size()==n){
9.                 res.push_back(path);
10.                 return ;
11.         }
12.         for(int i=0;i<=1;i++){
13.                         path.push_back(a[i]);       
14.                         dfs();
15.                         path.pop_back();
16.                 }
17.         }
18. int main(){
19.         cin>>n;
20.         dfs();
21.         sort(res.begin(),res.end());
22.         for(auto i:res){
23.                 for(auto j:i){
24.                         cout<<j;
25.                 }
26.                 cout<<endl;
27.         }
28.        
29. }

复制代码

---

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

   标题形貌
  今有 n 名门生，要从中选出 k 人排成一列照相。
  请按字典序输出所有可能的排列方式。
  输入格式
  仅一行，两个正整数 n,k。
  输出格式
  若干行，每行 k 个正整数，表示一种可能的队伍次序。
  输入输出样例
  输入 #1复制

1. 3 2

复制代码

输出 #1复制

1. 1 2
2. 1 3
3. 2 1
4. 2 3
5. 3 1
6. 3 2

复制代码

阐明/提示
  对于 100% 的数据，1≤k≤n≤10。
  思路
求排列方式，那就需要visited数组，在求排列的方式底子上加了后就行，看代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,k;
4. vector<vector<int>>res;
5. vector<int> path;
6. bool visited[15]={false};
7. void dfs(){
8.         if((int)path.size()==k){
9.                 res.push_back(path);
10.                 return ;
11.         }
12.         for(int i=1;i<=n;i++){
13.                 if(!visited[i]){
14.                 path.push_back(i);
15.                 visited[i]=1;       
16.                 dfs();
17.                 visited[i]=0;
18.                 path.pop_back();
19.                 }
20.                 }
21.         }
22. int main(){
23.         cin>>n>>k;
24.         dfs();
25.         for(auto i:res){
26.                 for(auto j:i){
27.                         cout<<j<<' ';
28.                 }
29.                 cout<<endl;
30.         }
31. }

复制代码

---

B3625 迷宫寻路

   标题形貌
  机器猫被困在一个矩形迷宫里。
  迷宫可以视为一个 n×m 矩阵，每个位置要么是空隙，要么是墙。机器猫只能从一个空隙走到其上、下、左、右的空隙。
  机器猫初始时位于 (1,1) 的位置，问能否走到 (n,m) 位置。
  输入格式
  第一行，两个正整数 n,m。
  接下来 n 行，输入这个迷宫。每行输入一个长为 m 的字符串，# 表示墙，. 表示空隙。
  输出格式
  仅一行，一个字符串。如果机器猫能走到 (n,m)，则输出 Yes；否则输出 No。
  输入输出样例
  输入 #1复制

1. 3 5
2. .##.#
3. .#...
4. ...#.

复制代码

输出 #1复制

1. Yes

复制代码

阐明/提示
  样例解释
  路线如下：(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)
  数据规模与约定
  对于 100% 的数据，保证 1≤n,m≤100，且 (1,1) 和 (n,m) 均为空隙。
  思路

这个题用dfs，bfs都行，先来个bfs吧哈哈，我的队列是用数组模仿的，数组模仿的常数时间会更快，这也算是bfs模版了，不是很丢脸看应该就行了，之后我也会写关于bfs的文章
其实这个题根洪水添补差不多，只不过这个是一个点往外一直伸张，看看能不能伸张到末了一个点
多讲点吧，用数组模仿的话，由于这是要存坐标，所以我们就需要一个二维的[0]存x,[1]存y
大家平时见到的控制上下左右的数组可能是两个数组，我这里用了一个更方便一些，不懂得可以本身试一下就能理解了，不懂bfs的可以正勤学学，这就纯是一个模板

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,m;
4. const int N=1010;
5. vector<string>grid(N);
6. bool visited[N][N];
7. int mv[5]={-1,0,1,0,-1};
8. int q[N][2];
9. int main(){
10.         cin>>n>>m;
11.         for(int i=0;i<n;i++){
12.                 cin>>grid[i];
13.         }
14.     visited[0][0]=1;
15.     int l=0,r=0;
16.     q[r][0]=0;
17.     q[r++][1]=0;
18.     while(l<r){
19.                 int size=r-l;
20.                 for(int i=0,nx,ny,x,y;i<size;i++){
21.                         x=q[l][0];
22.                         y=q[l++][1];
23.                         if(x==n-1&&y==m-1) {
24.                                 cout<<"Yes";
25.                                 return 0;
26.                         }
27.                         for(int k=0;k<=4;k++){
28.                                 nx=x+mv[k];
29.                                 ny=y+mv[k+1];
30.                                 if(nx>=0&&ny>=0&&nx<n&&ny<m&&!visited[nx][ny]&&grid[nx][ny]=='.'){
31.                                         visited[nx][ny]=true;
32.                                         q[r][0]=nx;
33.                                         q[r++][1]=ny;
34.                                 }
35.                         }
36.                 }
37.         }
38.         cout<<"No";
39.         return 0;
40. }

复制代码

下面是dfs，其实都差不多

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=1010;
4. bool visited[N][N];
5. int n,m;
6. vector<string> grid(N);
7. int mv[5]={-1,0,1,0,-1};
8. bool dfs(int x,int y) {
9.     // 到达终点
10.     if (x ==n-1&&y==m-1) {
11.         return true;
12.     }
13.     // 标记当前点已访问
14.     visited[x][y]=true;
15.     for (int i=0;i<=4;i++) {
16.         int nx=x+mv[i];
17.         int ny=y+mv[i];
18.         if (nx>=0&&nx<n&&ny>=0&&ny<m&&grid[nx][ny]=='.'&&!visited[nx][ny]) {
19.             if (dfs(nx,ny)){
20.                 return true;
21.             }
22.         }
23.     }
24.     return false;
25. }
26. int main(){
27.     cin>>n>>m;
28.     for (int i=0;i<n;i++) {
29.         cin>>grid[i];
30.     }
31.     // 起点或终点是墙，直接输出No
32.     if (grid[0][0]=='#'||grid[n-1][m-1]=='#') {
33.         cout<<"No"<<endl;
34.         return 0;
35.     }
36.     bool result=dfs(0, 0);
37.     cout <<(result?"Yes":"No")<<endl;
38.     return 0;
39. }

复制代码

---

P6183 [USACO10MAR] The Rock Game S

   标题形貌
  在奶牛回家休息和娱乐之前，Farmer John 渴望它们通过玩游戏得到一些智力上的刺激。
  游戏板由 n 个相同的洞组成，这些洞最初都是空的。一头母牛要么用石头盖住一个空的洞，要么揭开一个先前被盖住的洞。游戏状态的界说是所有洞是否被石头覆盖的环境。
  游戏的目的是让奶牛到达每个可能的游戏状态一次，末了回到初始状态。
  以下是他们此中一次游戏的示例（空的洞用 O 表示，用石头盖住的洞用 X 表示）：
  时刻洞 1洞 2洞 3形貌0OOO一开始所有的洞都是空的1OOX盖上洞 32XOX盖上洞 13XOO打开洞 34XXO盖上洞 25OXO打开洞 16OXX盖上洞 37XXX盖上洞 1  现在牛被卡住玩不下去了！他们必须打开一个洞，然而不管他们打开哪个洞，他们都会到达一个他们已经到达过的状态。例如，如果他们从第二个洞中取出岩石，他们将到达他们在时刻 2 已经访问过的状态（X O X）。
  下面是一个 3 个孔的有效办理方案：
  时间洞 1洞 2洞 3形貌0OOO一开始所有的洞都是空的1OXO盖上洞 22OXX盖上洞 33OOX打开洞 24XOX盖上洞 15XXX盖上洞 26XXO打开洞 37XOO打开洞 28OOO打开洞 1，恢复到原来的状态  现在，奶牛们厌倦了这个游戏，它们想找你帮忙。
  给定 n，求游戏的有效办理方案序列。如果有多个办理方案，则输出任意一个。
  输入格式
  仅一行，一个整数 n。
  输出格式
  共 2n+1 行，每行一个长度为 n 的字符串，此中只包罗字符 O 和 X，该行中的第 i 个字符表示第 i 个孔在此状态下是被覆盖还是未覆盖，第一行和末了一行必须全部都是 O。
  输入输出样例
  输入 #1复制

1. 3

复制代码

输出 #1复制

1. OOO
2. OXO
3. OXX
4. OOX
5. XOX
6. XXX
7. XXO
8. XOO
9. OOO

复制代码

阐明/提示
  样例 1 阐明
  见标题形貌。
  数据规模与约定
  对于 100% 的数据，有 1≤n≤15。
  总结

这段代码通过深度优先搜索的方式，生成一个格雷码序列。格雷码的特点是相邻的两个码之间只有一个位差异。 代码首先输出全'O'的状态，然后递归地翻转每一位，生成新的格雷码状态。 使用 vis 数组来避免重复访问相同的状态，从而保证生成的是一个有效的格雷码序列。ans数组存储生成的序列，末了output函数负责按要求输出。
现实上这段代码找到的是一种特殊的格雷码序列，它从全'O'开始，每次只翻转一位，直到遍历完所有可能的状态。 由于标题要求"找到一组即可"，所以找到任何一种满意条件的格雷码序列就可以直接输出并退出。
总而言之，该步调使用DFS算法奇妙地探索格雷码空间，并用vis数组进行状态标记避免重复，最终找到并输出一个合法的格雷码序列。

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n;
4. int a[20];//记录格雷码一个a[i]记录0或1
5. int vis[1<<20];//记录每一个格雷码的是否走过
6. int ans[1<<20][20];//记录每一个状态的格雷码
7. void output(){
8.         for(int i=1;i<=1<<n;i++){
9.                 for(int j=1;j<=n;j++){
10.                         cout<<(ans[i][j]?'X':'O');
11.                 }
12.                 cout<<endl;
13.         }
14. }
15. int calc(){//将当前格雷码转化为10进制用来存储状态
16.         int res=0;
17.         for(int i=1;i<=n;i++){
18.                 res=res*2+a[i];
19.         }
20.         return res;
21. }
22. void dfs(int pos){
23.         if(pos==(1<<n)){
24.                 output();
25.                 exit(0) ;
26.         }
27.         for(int i=1;i<=n;i++){
28.                 a[i]=!a[i];//从第一位开始到第n位，每个都翻转一遍看哪个状态没走过
29.             if(vis[calc()]){
30.                         a[i]=!a[i];//如果走过就翻转回去
31.                         continue;
32.                 }
33.                 vis[calc()]=1;//没走过现在走过了
34.                 for(int j=1;j<=n;j++){
35.                         ans[pos][j]=a[j];//把翻过的a[i]给存到最终答案这里
36.                 }
37.                 dfs(pos+1);
38.                 vis[calc()]=0;//回溯
39.                 a[i]=!a[i];
40.         }
41. }
42. int main(){
43.         cin>>n;
44.         for(int i=1;i<=n;i++) cout<<'O';
45.         cout<<endl;
46.         vis[0]=true;//提前输出了，000不能再走了
47.         dfs(1);//从001开始搜素
48.         return 0;
49. }

复制代码

---

P10448 组合型枚举

   标题形貌
  从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
  输入格式
  两个整数 n,m ,在同一行用空格隔开。
  输出格式
  按照从小到大的次序输出所有方案，每行 1 个。
  首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
  其次，对于两个差异的行，对应下标的数一一比力，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
  输入输出样例
  输入 #1复制

1. 5 3

复制代码

输出 #1复制

1. 1 2 3
2. 1 2 4
3. 1 2 5
4. 1 3 4
5. 1 3 5
6. 1 4 5
7. 2 3 4
8. 2 3 5
9. 2 4 5
10. 3 4 5

复制代码

阐明/提示
  对于所有测试数据满意 0≤m≤n , n+(n−m)≤25。
  思路

组合嘛，他不能重复，也就是说1 2 3有了后，就不能有2 3 1等等，所以就是我们要的是1 2 3
1 2 4 ，1 2 5,1 3 4,1 3 5,1 4 5,2 3 4如许子，每个数必须比前面谁人大，如许就保证每次组合都是新的，不重复，我们也不会少某个组合

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,m;
4. vector<int>path;
5. vector<vector<int>>res;
6. bool visited[100];
7. void dfs(int start){
8.         if(path.size()==m){
9.                 res.push_back(path);
10.                 return;
11.         }
12.         for(int i=start;i<=n;i++){
13.                         path.push_back(i);
14.                         dfs(i+1);//从i+1开始我们就能保证后面的一定比前面那个大了
15.                         path.pop_back();
16.         }
17. }
18. int main(){
19.         cin>>n>>m;
20.         dfs(1);
21.         for(auto i:res){
22.                 for(auto j:i){
23.                         cout<<j<<' ';
24.                 }
25.                 cout<<endl;
26.         }
27. }

复制代码

---

P10483 小猫登山

   标题形貌
  Freda 和 rainbow 豢养了 N(N≤18) 只小猫，这天，小猫们要去登山。经历了千辛万苦，小猫们终于爬上了山顶，但是倦怠的它们再也不想徒步走下山了
  Freda 和 rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1​,C2​,…CN​。当然，每辆缆车上的小猫的重量之和不能凌驾 W(1≤Ci​,W≤108)。每租用一辆缆车，Freda 和 rainbow 就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
  输入格式
  第一行包罗两个用空格隔开的整数，N 和 W。 接下来 N 行每行一个整数，此中第 i+1 行的整数表示第 i 只小猫的重量 Ci​。
  输出格式
  输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。
  输入输出样例
  输入 #1复制

1. 5 1996
2. 1
3. 2
4. 1994
5. 12
6. 29

复制代码

输出 #1复制

1. 2

复制代码

思路 

装箱问题：将 n 个物品装入若干个容量为 m 的容器，要求每个容器内物品总重量不凌驾 m，目的是找到使用最少容器数量的方案。
直接看代码吧

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,m,cat[20],ans=20,w[20];
4. void dfs(int u,int v){
5.         if(v>=ans) return ;//如果当前用的缆车数大于等于之前记录的最少缆车数量，那就直接返回不用再装了
6.         if(u==n){//已经全搜过了就不用再搜了，同时更新答案
7.                 ans=v;
8.                 return;
9.         }
10.         //第一种选择，用之前用过的缆车
11.         for(int i=0;i<v;i++){
12.                 if(w[i]+cat[u]<=m){
13.                         w[i]+=cat[u];
14.                         dfs(u+1,v);
15.                         w[i]-=cat[u];
16.                 }
17.         }
18.         //第二种，用新的
19.         w[v]=cat[u];
20.         dfs(u+1,v+1);//继续去搜索之后的猫
21. }
22. int main(){
23.         cin>>n>>m;
24.                 ans=n;
25.                 for(int i=0;i<n;i++){
26.                          cin>>cat[i];
27.                 }
28.                 sort(cat,cat+n,greater<int>());
29.                 dfs(0,0);
30.                 cout<<ans;
31.                 return 0;
32. }

复制代码

---

P8604 [蓝桥杯 2013 国 C] 危险系数

   标题形貌
  地道的多个站点间有通道毗连，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去接洽。
  我们来界说一个危险系数 DF(x,y)：
  对于两个站点 x 和 y(x=y), 如果能找到一个站点 z，当 z 被敌人破坏后，x 和 y 不连通，那么我们称 z 为关于 x,y 的关键点。相应的，对于任意一对站点 x 和 y，危险系数 DF(x,y) 就表示为这两点之间的关键点个数。
  本题的任务是：已知网络布局，求两站点之间的危险系数。
  输入格式
  输入数据第一行包罗 2 个整数 n(2≤n≤1000)，m(0≤m≤2000)，分别代表站点数，通道数。
  接下来 m 行，每行两个整数 u,v(1≤u,v≤n,u=v) 代表一条通道。
  末了 1 行，两个数 u,v，代表询问两点之间的危险系数 DF(u,v)。
  输出格式
  一个整数，如果询问的两点不连通则输出 −1。
  输入输出样例
  输入 #1复制

1. 7 6
2. 1 3
3. 2 3
4. 3 4
5. 3 5
6. 4 5
7. 5 6
8. 1 6

复制代码

思路

遍历图，从初始点dfs然后把所有能走到止境的路都走一遍，纪录有几条路，纪录每个节点走几次，如果有节点走的次数跟路径相同，那就阐明这个节点是每条路都要走的，哪题一消失，那我们包到不了止境，这个就是关键点

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,m;
4. int M;
5. int cnt;
6. bool visited[1010];
7. int ans[1010];
8. int ans1;
9. int x,y;
10. void dfs(int x,vector<vector<int>>& graph){
11.         if(x==y){
12.                 cnt++;
13.                 for(int i=1;i<=M;i++){
14.                         //遍历一下所有编号，可能有的编号不存在
15.                         //所以判断一下是否存在
16.                         ans[i]+=visited[i]?1:0;
17.                
18.                 }
19.                         return;
20.         }
21.         visited[x]=1;
22.         for(auto i:graph[x]){
23.                 if(!visited[i])
24.                 dfs(i,graph);
25.         }
26.         visited[x]=false;//这节点走完就回溯
27. }
28. int main(){
29.         cin>>n>>m;
30.         vector<vector<int>>graph(1010);
31.         while(m--){
32.                 int u,v;
33.                 cin>>u>>v;
34.                 graph[u].push_back(v);
35.                 graph[v].push_back(u);
36.                 M=max(max(M,u),v);//记录一下最大节点的编号
37.         }
38.         cin>>x>>y;
39.         dfs(x,graph);//从u开始搜索
40.         for(int i=1;i<=M;i++){
41.                 if(ans[i]==cnt) ans1++;
42.         }
43.         cout<<ans1-1;//减去初始点
44. }

复制代码

---

P9011 [USACO23JAN] Air Cownditioning II B

   标题形貌
  农民约翰的 N 头奶牛 (1≤N≤20) 住在一个谷仓里，谷仓里有连续的牛栏，编号为 1−100 。 奶牛 i 占据了编号 [si​,ti​] 的牛栏。 差异奶牛占据的牛栏范围是互不相交的。 奶牛有差异的冷却要求，奶牛 i 占用的每个牛栏的温度必须至少降低 ci​ 单位。
  谷仓包罗 M 台空调，标记为 1−M (1≤M≤10)。第 i 台空调需要耗费 mi​ 单位的金钱来运行 (1≤mi​≤1000) ，如果运行，第 i 台空调将牛栏 [ai​,bi​] 所有牛栏的温度降低 pi​（1≤pi​≤106）。 空调覆盖的牛栏范围可能会重叠。
  请帮助农民约翰求出满意所有奶牛需求要耗费的最少金钱。
  输入格式
  第一行两个整数，分别为 N 和 M。
  第 2 至 (N+1) 行，每行三个整数，分别为 si​、ti​ 和 ci​ 。
  第 (N+2) 至 (M+N+1) 行，每行四个整数， 分别为 ai​、bi​、pi​ 和 mi​。
  输出格式
  一个整数，表示最少耗费的金钱。
  表现翻译
  题意翻译
  
  输入输出样例
  输入 #1复制

1. 2 4
2. 1 5 2
3. 7 9 3
4. 2 9 2 3
5. 1 6 2 8
6. 1 2 4 2
7. 6 9 1 5

复制代码

输出 #1复制

1. 10

复制代码

阐明/提示
  样例解释 1
  一种耗费最少的可能办理方案是选择那些冷却区间为 [2,9] 、[1,2] 和 [6,9] 的空调，本钱为 3+2+5=10 .
  对于 100% 的数据，1≤N≤20， 1≤M≤10, 1≤ai​,bi​,si​,ti​≤100, 1≤ci​,pi​≤106， 1≤mi​≤1000。
  思路

就是一起两搜索，选或不选这个空调，就好，只不过多注意细节，可以利用差分，我这里就没用

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=110;
4. int n,m,k,ans=1e9;//n头牛，m个空调
5. //第i头牛占据s[i]到t[i]的牛栏 ，每头牛i占的栅栏必须降低c[i]
6. //第i个空调需要花M[i],第i个空调能让a[i]到b[i]降低p[i]
7. int s[N],t[N],c[N],a[N],b[N],p[N],M[N],w[N];
8. bool check(){
9.         for(int i=1;i<=k;i++){
10.                 //如果还有某个牛所处区域的空调没到达c[i]
11.                 //因为我们是预处理最开始都等于c[i]所以这里是判断是否大于0
12.                 if(w[i]>0) return false;
13.         }
14.         return 1;
15. }
16. void dfs(int deep,int s){
17.         if(deep>m){
18.                 //如果搜索完一遍
19.                 if(check())
20.                         ans=min(ans,s);
21.                          return;
22.         }
23.                
24.         for(int i=a[deep];i<=b[deep];i++) w[i]-=p[deep];
25.         dfs(deep+1,s+M[deep]);//选这个空调  
26.         for(int i=a[deep];i<=b[deep];i++) w[i]+=p[deep];
27.     dfs(deep+1,s);//不选当前这个第deep号空调
28. }
29. int main(){
30.         cin>>n>>m;
31.         for(int i=1;i<=n;i++){
32.                 cin>>s[i]>>t[i]>>c[i];
33.                 k=max(k,t[i]);
34.                 for(int j=s[i];j<=t[i];j++){
35.                         w[j]+=c[i];
36.                 }
37.         }
38.         for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>p[i]>>M[i];
39.         dfs(1,0);
40.         cout<<ans;
41. }

复制代码

P10294 [CCC 2024 J5] Harvest Waterloo

   标题形貌
  有一款新出现的广受欢迎的收割模仿游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行，南瓜地里有成捆的干草和差异巨细的南瓜。游戏开始时，一个农民在此中一个南瓜的位置上。
  农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动，不能穿过干草，也不能脱离地步。
  你的工作是确定农民收获的南瓜的总代价。此中一个小南瓜值 1 美元，一个中等巨细的南瓜值 5 美元，而一个大南瓜值 10 美元。
  输入格式
  输入的第一行是一个整数 R>0 表示南瓜地的行数。
  第二行是一个整数 C>0 表示南瓜地的列数。
  接下来 R 行形貌了整个南瓜地。每行包罗 C 个字符而且每个字符要么表示一个南瓜，要么表示干草：S 表示小南瓜，M 表示中等巨细的南瓜，L 表示一个大南瓜，* 表示干草。
  下一行包罗一个整数 A 满意 0≤A<R，末了一行是一个整数 B 满意 0≤B<C。表示农民一开始在第 A 行第 B 列的位置。南瓜地的左上角称为第 0 行第 0 列。
  输出格式
  输出一个整数 V 表示农民可以或许收割的南瓜的总代价。
  输入输出样例
  输入 #1复制

1. 6
2. 6
3. **LMLS
4. S*LMMS
5. S*SMSM
6. ******
7. LLM*MS
8. SSL*SS
9. 5
10. 1

复制代码

输出 #1复制

1. 37

复制代码

输入 #2复制

1. 6
2. 6
3. **LMLS
4. S*LMMS
5. S*SMSM
6. ***SLL
7. LLM*MS
8. SSL*SS
9. 2
10. 4

复制代码

输出 #2复制

1. 88

复制代码

【数据范围】
  本题采用捆绑测试。
  对于所有数据，保证 1≤R,C≤105，1≤R×C≤105。
  下面的表格表现了 15 分的分配方案：
  分值形貌范围1南瓜地很小而且不存在干草。R×C≤1004南瓜地很小而且干草把南瓜地分割为一些矩形地域。R×C≤1005南瓜地很小而且干草可以在任意位置。R×C≤1005南瓜地可能很大而且干草可以在任意位置。R×C≤105  思路

依旧是简朴点洪水添补问题，直接看代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,m;
4. const int N=1e5+10;
5. vector<string> grid(N);
6. void dfs(int i,int j){
7.         if(i<0||j<0||i==n||j==m||(grid[i][j]!='L'&&grid[i][j]!='M'&&grid[i][j]!='S'))
8.         return;
9.         if(grid[i][j]=='L') grid[i][j]='l';
10.         if(grid[i][j]=='S') grid[i][j]='s';
11.         if(grid[i][j]=='M') grid[i][j]='m';
12.         dfs(i,j+1);
13.         dfs(i,j-1);
14.         dfs(i+1,j);
15.         dfs(i-1,j);
16.        
17. }
18. int l,s,m1;
19. int main(){
20.         cin>>n>>m;
21.         for(int i=0;i<n;i++){
22.                 cin>>grid[i];
23.         }
24.         int x,y;
25.         cin>>x>>y;
26.         dfs(x,y);
27.         for(int i=0;i<n;i++){
28.                 for(int j=0;j<m;j++){
29.                         if(grid[i][j]=='l') l+=10;
30.                         if(grid[i][j]=='m') m1+=5;
31.                         if(grid[i][j]=='s') s++;
32.                 }
33.         }
34.         cout<<l+m1+s;
35. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告