蓝桥杯练习题总结（二）dfs题、飞机降落、全球变暖

目录

一、飞机降落
二、全球变暖
初始化和输入
确定岛屿
DFS搜索判断岛屿是否会被淹没
 计算被淹没的岛屿数量
三、军训排队 

---

一、飞机降落

   题目描述：
  N架飞机预备降落到某个只有一条跑道的机场。此中第 i 架飞机在

时刻到达机场上空，到达时它的剩余油料还可以继承回旋

个单位时间，即它最早可以于 1, 时刻开始降落，最晚可以于

时刻开始降落。降落过程需要

个单位时间。
  输入格式：
  输入包罗多组数据。
  第一行包罗一个整数N，代表测试数据的组数。
  对于每组数据：
  第一行包罗一个整数T，代表测试数据的组数。
  对于每组数据，第一行包罗一个整数 N。
接下来的N行，每行包罗三个整数

。
输出格式：
  对于每组数据，输出YES或者NO，代表是否可以全部安全降落。
  输入样例：

1. 2
2. 3
3. 0 100 10
4. 10 10 10
5. 0 2 20
6. 3
7. 0 10 20
8. 10 10 20
9. 20 10 20

复制代码

输出样例：

1. YES
2. NO

复制代码

思路：

• 首先读取飞机的数量N，然后读取每架飞机的到达时间t、回旋时间d和降落时间l。
  
• 使用深度优先搜索（DFS）尝试所有大概的降落顺序。DFS的过程中，我们需要一个bool数组来记录每架飞机的降落状态（比方，是否已经降落）。
  

1. bool st[N];// 判断当前飞机是否已经降落

复制代码

• 循环遍历假如当前尝试的飞机不能在剩余油料答应的时间内降落，或者尝试完所有飞机后没有找到合法的降落顺序，则回溯到上一个状态，尝试另一种降落顺序。
  
• 对于每一架尝试降落的飞机，检查它是否可以大概在剩余油料答应的时间内开始降落，即降落的开始时间应该在到达时间加回旋时间的范围内（
  
   上一次降落时间 + 
  
    ）。
  

1. if (p[i].t + p[i].d < time)
2. // 如果当前时间超过了飞机的最晚降落时间
3. {
4.     //回溯，回溯到DFS之前的状态。
5.         st[i] = false;
6.         return false;
7. }
8. int t = max(time, p[i].t) + p[i].l;// 此次降落时间

复制代码

• 假如当前尝试的飞机可以降落，更新该飞机的状态为已降落，并更新跑道的可用时间为该飞机降落完成的时间。
  

1. int t = max(time, p[i].t) + p[i].l;
2. if (dfs(u + 1, t))
3.                 return true;

复制代码

• 假如找到了一个所有飞机都能在其剩余油料答应的时间内完成降落的顺序，则输出"YES"，否则输出"NO"。
  
• 重置st数组，预备下一组数据
  

1. for (int i = 0; i < n; i++)
2.                 st[i] = false;

复制代码

1. #include<bits/stdc++.h>
2. #define ll long long
3. using namespace std;
4. const int N = 10 + 20;
6. struct plane {
7.         ll t,// 到达上空时间
8.                 d,// 可盘旋时间
9.                 l;// 降落所需时间
11. }p[N];
13. bool st[N];// 判断当前飞机是否已经降落
15. ll n;// 飞机个数。
17. // u表示已经有U架飞机成功降落了。
18. // time表示当前的时间,前一架飞机落地的时间。
19. bool dfs(ll u, ll time)
20. {
21.         if (u >= n)return true;
22.         // 已经有n架飞机降落，顺序合法
24.         // 遍历所有飞机，考虑它们的降落顺序
25.         for (int i = 0; i < n; i++)
26.         {
27.                 if (!st[i])// 如果没有降落
28.                 {
29.                         st[i] = true;
30.                         if (p[i].t + p[i].d < time)
31.             // 如果当前时间超过了飞机的最晚降落时间
32.                         {
33.                                 //回溯，回溯到DFS之前的状态。
34.                                 st[i] = false;
35.                                 return false;
36.                         }
38.                         ll t = max(time, p[i].t) + p[i].l;
39.                         if (dfs(u + 1, t))
40.                                 return true;
42.                         //回溯，回溯到DFS之前的状态。
43.                         st[i] = false;
44.                 }
45.         }
46.         return false;
47. }
49. void solve()
50. {
51.         cin >> n;
52.         for (int i = 0; i < n; i++)// 读入每架飞机的信息
53.                 cin >> p[i].t >> p[i].d >> p[i].l;
55.         if (dfs(0, 0))
56.                 cout << "YES" << endl;
57.         else
58.                 cout << "NO" << endl;
60.         for (int i = 0; i < n; i++)// 重置st数组，准备下一组数据
61.                 st[i] = false;
62. }
64. int main()
65. {
66.         ios::sync_with_stdio(0);
67.         cin.tie(0);
68.         int t = 1;
69.         cin >> t;
70.         while (t--)
71.                 solve();
72. }

复制代码

二、全球变暖

   标题描述：
  由于全球变暖导致海面上升，科学家预测将来几十年内，岛屿边沿的一个像素范围将会被海水淹没。具体来说，假如一块陆地像素（用“#”表现）与海洋像素（用“.”表现）相邻（即上下左右四个相邻像素中有海洋），这块陆地就会被淹没，变成海洋。给定一个N×N的海域照片，你需要计算根据科学家的预测，照片中会有多少岛屿被完全淹没。
  输入描述：
  第一行包罗一个整数N（1≤N≤1000），表现海域照片的尺寸。
接下来N行，每行包罗N个字符，表现海域照片，此中“#”表现陆地，“.”表现海洋。照片保证第一行、第一列、第N行、第N列的像素都是海洋。
  输出描述：
  输出一个整数，表现根据科学家的预测，会有多少岛屿被完全淹没。
  样例输入：
  7
..##...
.###...
.#..#..
..####.
...#.#.
....###
.......
  样例输出：
  1
  表明：
  给定的海域照片中有两座岛屿，分别由"#"字符组成。根据科学家的预测，只有左边的岛屿会被完全淹没，因此输出为1。
  思路：
初始化和输入

• 定义了一个二维数组mp来存储给定的海域照片，此中“#”表现陆地，“.”表现海洋。
  
• col数组用于记录每个像素点属于哪一个岛屿。
  
• vis数组用于标记一个岛屿是否会被完全淹没。
  
• 输入尺寸n和海域照片。
  

1. using ll = long long;
2. const int N = 1e3 + 5;
4. int n, scc, // 尺寸和颜色编号
5. col[N][N];// 用于记录每个像素点属于哪一个岛屿
6. char mp[N][N];// 存储海域照片
8. // 表示四个可能的移动方向：上，下，左，右
9. int dx[] = { 0,0,1,-1 };
10. int dy[] = { 1,-1,0,0 };
12. bool vis[N * N];// 用于标记一个岛屿是否被完全淹没

复制代码

• 确定岛屿
  

1. for (int i = 1; i <= n; i++)
2.         for (int j = 1; j <= n; j++)
3.         // 遍历每一个像素点
4.         {
5.             if (col[i][j] || mp[i][j] == '.') continue;
6.             scc++;       dfs(i, j);
7.             // 岛屿数量++ 开始DFS搜索
8.         }

复制代码

首先，我们需要识别舆图上所有的岛屿。这可以通过遍历整个照片来完成，每当我们遇到一个“#”（陆地）字符，我们就从这个点开始举行深度优先搜索（DFS），以找出这块陆地毗连的所有部分，即一个完整的岛屿。在搜索过程中，我们将不同的岛屿染上不同的颜色，并将访问过的陆地标记为已访问，以制止重复计算。

• DFS搜索判断岛屿是否会被淹没
  

对于每个岛屿，我们需要判断它是否会被完全淹没。这意味着我们需要检查岛屿的边沿是否与海洋相邻。假如岛屿的任何一部分位于边沿（即，与舆图边沿的海洋相邻）或者有至少一个部分的上下左右四个方向中有一个是海洋，则这个岛屿将不会被完全淹没。否则，该岛屿将被视为会被完全淹没。

1. // 找出岛屿的范围
2. void dfs(int x, int y)
3. {
4.     col[x][y] = scc;// 标记该像素点属于当前岛屿
5.     for (int i = 0; i < 4; i++)
6.     // 遍历所有可能的移动方向
7.     {
8.         int nx = x + dx[i], ny = y + dy[i];// 计算新的位置
9.         if (col[nx][ny] || mp[nx][ny] == '.') continue;
10.         // 如果是访问过或者是海洋则跳过
11.         dfs(nx, ny);
12.     }
13. }

复制代码

• 使用dfs函数来找出每一个岛屿的范围。dfs函数通过递归地搜索每个陆地像素的上下左右四个相邻位置来实现，假如相邻位置也是陆地（“#”），则继承举行DFS搜索。
  
• 在dfs的过程中，使用col数组来标记当前正在搜索的岛屿的所有像素点，即将这些点都标记为当前岛屿的编号scc。
  
• 通过dx和dy数组来表现四个大概的移动方向（上、下、左、右），以便在DFS搜索中移动到相邻的像素点。
  

1.     for (int k = 0; k < 4; ++k)
2.     // 遍历四个方向
3.     {
4.         int x = i + dx[k], y = j + dy[k];
5.         if (mp[x][y] == '.') tag = false;
6.         // (x, y)处的像素是否被海洋淹没(全是陆地就不淹没)
7.     }
8.    

复制代码

•  计算被淹没的岛屿数量
  

• 使用tag标记来表现当前检查的像素点是否会被淹没，即假如四个方向中有海洋，则tag为false，表现该岛屿的这个部分会被淹没。
  
• 对于每一个岛屿，假如其任何一个部分不会被淹没，则整个岛屿都不会被淹没。使用vis数组来标记这些情况。假如vis数组中对应的岛屿编号为false，则将其标记为true并增长ans计数器（记录不会被淹没的岛屿数量）。
  

1. if (tag)// 如果四个方向都不是海洋，则当前陆地像素点不会被淹没
2.     {
3.         if (!vis[col[i][j]]) ans++;
4.         // 如果这个岛屿还没有被计入被淹没的岛屿中, 完全被淹没的岛屿++
5.         vis[col[i][j]] = true;// 标记这个岛屿为被淹没
6.     }

复制代码

• 末了，输出scc - ans，即总岛屿数量减去不会被淹没的岛屿数量，得到的就是会被完全淹没的岛屿数量。
  

1. cout << scc - ans << '\n';

复制代码

1. #include<bits/stdc++.h>using namespace std;using ll = long long;
2. const int N = 1e3 + 5;
4. int n, scc, // 尺寸和颜色编号
5. col[N][N];// 用于记录每个像素点属于哪一个岛屿
6. char mp[N][N];// 存储海域照片
8. // 表示四个可能的移动方向：上，下，左，右
9. int dx[] = { 0,0,1,-1 };
10. int dy[] = { 1,-1,0,0 };
12. bool vis[N * N];// 用于标记一个岛屿是否被完全淹没// 找出岛屿的范围
13. void dfs(int x, int y)
14. {
15.     col[x][y] = scc;// 标记该像素点属于当前岛屿
16.     for (int i = 0; i < 4; i++)
17.     // 遍历所有可能的移动方向
18.     {
19.         int nx = x + dx[i], ny = y + dy[i];// 计算新的位置
20.         if (col[nx][ny] || mp[nx][ny] == '.') continue;
21.         // 如果是访问过或者是海洋则跳过
22.         dfs(nx, ny);
23.     }
24. }int main(){    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    cin >> n;//读入尺寸    for (int i = 1; i <= n; i++)        cin >> mp[i] + 1;// 读入海域照片数据        // 从这一行的第二个元素开始读取输入    for (int i = 1; i <= n; i++)
25.         for (int j = 1; j <= n; j++)
26.         // 遍历每一个像素点
27.         {
28.             if (col[i][j] || mp[i][j] == '.') continue;
29.             scc++;       dfs(i, j);
30.             // 岛屿数量++ 开始DFS搜索
31.         }    int ans = 0;// 用于记录被完全淹没的岛屿数量    for (int i = 1; i <= n; i++)        for (int j = 1; j <= n; j++)        {            if (mp[i][j] == '.') continue;            // 假如是海洋，则跳过            bool tag = true;// 标记是否会被淹没            for (int k = 0; k < 4; ++k)            // 遍历四个方向            {                int x = i + dx[k], y = j + dy[k];                if (mp[x][y] == '.') tag = false;                // (x, y)处的像素是否被海洋淹没(全是陆地就不淹没)            }            if (tag)// 假如四个方向都不是海洋，则当前陆地像素点不会被淹没            {                if (!vis[col[i][j]]) ans++;                // 假如这个岛屿还没有被计入被淹没的岛屿中, 完全被淹没的岛屿++                vis[col[i][j]] = true;// 标记这个岛屿为被淹没            }        }    cout << scc - ans << '\n';// 输出未被淹没的岛屿数量    return 0;}

复制代码

三、军训排队 

   题目描述
  数字王国开学了，它们也和我们人类一样有开学前的军训。现在一共有n名学生，每个学生有一个本身的名字（在数字王国里，名字就是一个正整数）。注意，学生们大概出现重名的情况。反叛教官来看了之后感觉非常别扭，决定将学生重新分队。排队规则为：将学生分成若干队，每队里面至少有一个学生，且每队里面学生的名字不能出现倍数关系（注意，名字相同也算是倍数关系）。现在请你帮忙算算最少可以分成几队？
  比方：有4名学生(2,3,4,4)，最少可以分成(2,3)、(4)、(4)共3队。
  输入格式
  第一行包罗一个正整数n，表现学生数量。
  第二行包罗n个由空格隔开的整数，第i个整数表现第i个学生的名字α。
  输出格式
  输出共1行，包罗一个整数，表现最少可以分成几队。
  样例输入
  4
  2 3 4 4
  样例输出
  3
  （表明：如上所述，可以将4名学生分成(2,3)、(4)、(4)共3队，满足每队学生的名字之间不存在倍数关系。）
  思路：
枚举最少队伍数量：
首先，我们可以从小到大枚举“最少队伍的数量”。这意味着，我们从最少的队伍数开始尝试，逐渐增长队伍数，直到找到一个可行的分组方案。
搜索合法性：
对于每一个枚举的队伍数量，我们需要判断在这个数量下是否可以乐成分组。这可以通过搜索来实现。具体来说，我们确定总队伍数量后，对于每一个人（或元素），枚举他所属的队伍。这里，回溯法是一种非常有用的搜索技术。
剪枝策略：
在搜索过程中，为了提高服从，我们需要接纳剪枝策略。一种常见的剪枝方法是，当某个人（或元素）尝试参加某个队伍时，我们立即检查这个队伍中是否已存在与该人具有某种特定关系（如倍系关系）的其他成员。假如存在这样的关系，我们就可以直接跳过当前尝试，由于它不大概导致一个有用的分组。

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 15; // 最大可能的队伍数目或学生数
5. int a[N], n; // a数组用来存储每个学生的名字，n表示学生的数量
7. vector<int>v[N]; // 使用vector数组来表示每个队伍，存储队伍中学生的名字
9. // dfs函数尝试将学生分配到不同的队伍中
10. bool dfs(int cnt, int dep) {
11.     // cnt表示当前尝试的队伍数量，dep表示当前处理到第几个学生
12.     if (dep == n + 1) {
13.         // 如果dep等于n+1，说明所有学生都已经被分配到队伍中
14.         return true;
15.     }
16.     for (int i = 1; i <= cnt; ++i) {
17.         // 遍历当前所有队伍，尝试将学生放入
18.         bool tag = true; // 用tag标记当前学生是否能放入队伍i中
19.         for (const auto& j : v[i]) {
20.             // 遍历队伍i中已经有的学生名字
21.             if (a[dep] % j == 0) {
22.                 // 如果当前学生的名字是队伍中某学生名字的倍数
23.                 tag = false; // 不能放入这个队伍
24.                 break; // 停止遍历队伍
25.             }
26.         }
27.         if (!tag) continue; // 如果不能放入当前队伍，继续尝试下一个队伍
28.         v[i].push_back(a[dep]); // 将学生放入队伍i
29.         if (dfs(cnt, dep + 1)) return true; // 递归地尝试放置下一个学生
30.         v[i].pop_back(); // 如果不能成功放置，将学生从队伍i中移除
31.     }
32.     return false; // 如果所有队伍都不能放入当前学生，返回false
33. }
34. int main() {
35.     // 设置输入输出流以提高效率
36.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
37.     cin >> n; // 读入学生数量
38.     for (int i = 1; i <= n; i++) {
39.         cin >> a[i]; // 读入每个学生的名字
40.     }
41.     for (int i = 1; i <= n; i++) {
42.         // 从1个队伍尝试到n个队伍，找到最少可以分成的队伍数量
43.         if (dfs(i, 1)) {
44.             // 如果可以将所有学生分配到i个队伍中
45.             cout << i << '\n'; // 输出队伍的数量
46.             break;
47.         }
48.     }
49.     return 0;
50. }

复制代码

本日就先到这了！！！

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
你们的点赞就是博主更新最大的动力！
有题目可以评论或者私信呢秒回哦。


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