蓝桥杯复习清单真题(C++版本）

蓝桥杯复习清单枚举日期统计问题描述小蓝现在有一个长度为 100 的数组数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3现在他想要从这个数组中寻找一些满足以下条件的子序列子序列的长度为 8这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期并且要求这个日期是 2023 年中的某一天的日期例如 20230902, 20231223。yyyy 表示年份mm 表示月份dd 表示天数当月份或者天数的长度只有一位时需要一个前导零补充。请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。解法由题意可知要找⽇期全是 2023 年份的只有⽉和⽇会变化。因此可以先枚举 2023 年的每⼀个⽉和⽇然后判断序列中是否存在这个⽇期。枚举 2023 年的每⼀个⽉和⽇的时间开销为 365判断数组中是否存在这个⽇期的时间开销为 100效率更⾼。代码如下#include iostream using namespace std; int n 100;// 数组长度固定为 100 int a[110];// 存储输入的数字序列下标从1开始 int days[] { 0,31,28,31,30,31,30,31,31,30,31,30,31 };//days[0]占位不用days[1]是 1 月的天数依此类推 int main() { for (int i 1; i n; i) cin a[i]; int cnt 0; for (int m 1; m 12; m)//枚举月份 for (int d 1; d days[m]; d)//枚举天数 { int t[] { 2,0,2,3,m / 10,m % 10,d / 10,d % 10 }; for (int i 0, j 1; j n; j) { if (a[j] t[i])// // 当前数字匹配目标序列 { i;//匹配下一个数 if (i 8)// 8 个数字全部匹配成功 { cnt;// 计数器1 break;// 跳出循环处理下一个日期 } } } } cout cnt endl; return 0; }二分查找冶炼金属【题目描述】小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 VV 是一个正整数这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X 当普通金属 O 的数目不足 V 时无法继续冶炼。现在给出了 N 条冶炼记录每条记录中包含两个整数 A 和 B这表示本次投入了 A 个普通金属 O最终冶炼出了 B 个特殊金属 X。每条记录都是独立的这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。根据这 N 条冶炼记录请你推测出转换率 V 的最小值和最大值分别可能是多少题目保证评测数据不存在无解的情况。【输入描述】第一行一个整数 N表示冶炼记录的数目。接下来输入 N 行每行两个整数 A、B含义如题目所述。【输出描述】输出两个整数分别表示 V 可能的最小值和最大值中间用空格分开。【示例一】输入375 353 259 2输出20 25代码如下#include iostream using namespace std; const int N 1e4 10; int n, a[N], b[N]; bool check1(int v) { for (int i 1; i n; i) if (a[i] / v b[i]) return false; return true; } bool check2(int v) { for (int i 1; i n; i) if (a[i] / v b[i]) return false; return true; } int main() { cin n; for (int i 1; i n; i) cin a[i] b[i]; //二分最小值 int l 1, r 1e9; while (l r) { int mid (l r) / 2; if (check1(mid)) r mid; else l mid 1; } cout l ; //二分最大值 l 1, r 1e9; while (l r) { int mid (l r 1) / 2;//mid (l r 1) / 2是向上取整避免在 lr-1 时死循环。 if (check2(mid)) l mid; else r mid - 1; } cout l endl; return 0; }DFS飞机降落【题目描述】N架飞机准备降落到某个只有一条跑道的机场。其中第 i架飞机在 Ti时刻到达机场上空到达时它的剩余油料还可以继续盘旋 Di个单位时间即它最早可以于 Ti时刻开始降落最晚可以于 TiDi时刻开始降落。降落过程需要 Li个单位时间。一架飞机降落完毕时另一架飞机可以立即在同一时刻开始降落但是不能在前一架飞机完成降落前开始降落。请你判断 N架飞机是否可以全部安全降落。【输入描述】输入包含多组数据。第一行包含一个整数 T代表测试数据的组数。对于每组数据第一行包含一个整数 N。以下 N行每行包含三个整数TiDi和 Li。【输出描述】对于每组数据输出YES或者NO代表是否可以全部安全降落。【示例一】输入230 100 1010 10 100 2 2030 10 2010 10 2020 10 20输出YESNO代码如下#include iostream #include cstring using namespace std; const int N 15; int n, t[N], d[N], l[N]; bool st[N]; bool dfs(int pos, int end) { //pos当前要安排第几架飞机已安排了 pos-1 架 //end当前跑道的可用时间上一架飞机降落结束的时间 if (pos n) return true;// 所有飞机都安排好了 for (int i 1; i n; i) { if (st[i]) continue; //如果最晚开始时间 跑道可用时间那么飞机无法降落油料不够等到跑道空闲 if (t[i] d[i] end) continue; st[i] true; int newend max(t[i], end) l[i]; if (dfs(pos 1, newend)) return true; st[i] false; } return false; } int main() { int T; cin T; while (T--) { memset(st, 0, 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; }线性DP-最长递增子序列接龙数列问题描述对于一个长度为 K 的整数数列A₁, A₂, …, Aₖ我们称之为接龙数列当且仅当 Aᵢ 的首位数字恰好等于 Aᵢ₋₁ 的末位数字2 ≤ i ≤ K。例如 12, 23, 35, 56, 61, 11 是接龙数列12, 23, 34, 56 不是接龙数列因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。现在给定一个长度为 N 的数列 A₁, A₂, …, Aₙ请你计算最少从中删除多少个数可以使剩下的序列是接龙序列输入格式第一行包含一个整数 N。第二行包含 N 个整数 A₁, A₂, …, Aₙ。输出格式一个整数代表答案。样例输入511 121 22 12 2023样例输出1样例说明删除 22剩余 11, 121, 12, 2023 是接龙数列。代码如下#include iostream #include string using namespace std; const int N 1e5 10; int n; int len[10]; // len[i] 表示以数字 i 结尾的接龙序列的最大长度 int main() { cin n; int ret 0; // 记录全局最长的接龙序列长度 for (int i 1; i n; i) { string s; cin s; int l s[0] - 0; // 首位数字 int r s.back() - 0; // 末位数字 int t len[l] 1; // 当前数字可以接在以 l 结尾的序列后面 len[r] max(len[r], t); // 更新以 r 结尾的序列最大长度 ret max(ret, t); // 更新全局最大值 } cout n - ret endl; // 最少删除数 总数 - 最长接龙序列长度 return 0; }FloodFill问题岛屿个数问题描述小蓝得到了一副大小为 M × N 的格子地图可以将其视作一个只包含字符 ‘0’代表海水和 ‘1’代表陆地的二维数组地图之外可以视作全部是海水每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。在岛屿 A 所占据的格子中如果可以从中选出 k 个不同的格子使得他们的坐标能够组成一个这样的排列(x₀, y₀), (x₁, y₁), …, (xₖ₋₁, yₖ₋₁)其中 (xᵢ₊₁ mod k, yᵢ₊₁ mod k) 是由 (xᵢ, yᵢ) 通过上/下/左/右移动一次得来的0 ≤ i ≤ k - 1此时这 k 个格子就构成了一个“环”。如果另一个岛屿 B 所占据的格子全部位于这个“环”内部此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿C 又是 B 的子岛屿那 C 也是 A 的子岛屿。请问这个地图上共有多少个岛屿在进行统计时不需要统计子岛屿的数目。输入格式第一行一个整数 T表示有 T 组测试数据。接下来输入 T 组数据。对于每组数据第一行包含两个用空格分隔的整数 M、N 表示地图大小接下来输入 M 行每行包含 N 个字符字符只可能是 ‘0’ 或 ‘1’。输出格式对于每组数据输出一行包含一个整数表示答案。样例输入25 501111110011010110001111115 6111111100001010101100001111111样例输出13代码如下#include iostream #include cstring using namespace std; const int N 55; int n, m, cnt; int g[N][N]; bool st[N][N]; // 4方向上下左右用于岛屿标记 int dx4[] {-1, 1, 0, 0}; int dy4[] {0, 0, -1, 1}; // 8方向包括对角线用于海水淹没 int dx8[] {-1, 1, 0, 0, -1, -1, 1, 1}; int dy8[] {0, 0, -1, 1, -1, 1, -1, 1}; // 标记整个岛屿4连通 void dfs_mark_island(int a, int b) { st[a][b] true; for (int i 0; i 4; i) { int x a dx4[i], y b dy4[i]; if (x 1 || x n || y 1 || y m || st[x][y]) continue; if (g[x][y]) dfs_mark_island(x, y); } } // 海水淹没8连通 void dfs_flood(int a, int b) { st[a][b] true; for (int i 0; i 8; i) { int x a dx8[i], y b dy8[i]; if (x 0 || x n 1 || y 0 || y m 1 || st[x][y]) continue; if (g[x][y]) { // 遇到陆地 cnt; // 这是一个新岛屿 dfs_mark_island(x, y); // 标记整个岛屿防止重复计数 } else { dfs_flood(x, y); // 继续淹没海水 } } } int main() { int T; cin T; while (T--) { // 初始化 memset(g, 0, sizeof g); memset(st, 0, sizeof st); cnt 0; cin n m; // 读入地图 for (int i 1; i n; i) { for (int j 1; j m; j) { char ch; cin ch; g[i][j] ch - 0; } } // 从地图外(0,0)开始海水淹没 // 注意g[0][0]一定是0海水因为地图外都是海水 dfs_flood(0, 0); cout cnt endl; } return 0; }模拟产值调整问题描述偏远的小镇上三兄弟共同经营着一家小型矿业公司“兄弟矿业”。公司旗下有三座矿山金矿、银矿和铜矿它们的初始产值分别用非负整数 A、B和 C表示。这些矿山的产出是小镇经济的核心支撑着三兄弟和许多矿工家庭的生计。然而各矿山的产值波动剧烈有时金矿收益高而银矿、铜矿低迷有时则相反。这种不稳定性让公司收入难以预测也常引发兄弟间的争执。为了稳定经营三兄弟设计了一个公平的产值调整策略每年执行一次每次调整时将根据当前的产值 A、B、C计算新产值金矿新产值 A′⌊2BC⌋银矿新产值 B′⌊2AC⌋铜矿新产值 C′⌊2AB⌋。其中⌊⌋表示向下取整。例如⌊3.7⌋3⌊5.2⌋5。计算出 A′、B′、C′后同时更新A变为 A′B变为 B′C变为 C′作为下一年调整的基础。三兄弟认为这个方法能平衡产值波动于是计划连续执行 K次调整。现在请你帮他们计算经过 K次调整后金矿、银矿和铜矿的产值分别是多少。输入格式输入的第一行包含一个整数 T表示测试用例的数量。接下来的 T行每行包含四个整数 ABCK分别表示金矿、银矿和铜矿的初始产值以及需要执行的调整次数。输出格式对于每个测试用例输出一行包含三个整数表示经过 K次调整后金矿、银矿和铜矿的产值用空格分隔。样例输入210 20 30 15 5 5 3样例输出25 20 155 5 5代码如下include iostream using namespace std; int main() { int T; cin T; while(T--) { int a, b, c, k; cin a b c k; while(k--) { int x (b c) / 2, y (a c) / 2, z (a b) / 2; a x, b y, c z; if(a b a c) break; } cout a b c endl; } }01BFS水质检测问题描述小明需要在一条 2×n的河床上铺设水质检测器。在他铺设之前河床上已经存在一些检测器。如果两个检测器上下或左右相邻那么这两个检测器就是互相连通的。连通具有传递性即如果 A和 B连通B和 C连通那么 A和 C也连通。现在他需要在河床上增加铺设一些检测器使得所有检测器都互相连通。他想知道最少需要增加铺设多少个检测器输入格式输入共两行表示一个 2×n的河床。每行一个长度为 n的字符串仅包含#和.其中#表示已经存在的检测器.表示空白。输出格式输出共 1 行一个整数表示最少需要增加的检测器数量。样例输入.##....# .#..#...样例输出5样例说明其中一种方案###....#.#######增加了 5 个检测器。代码如下#include iostream #include queue #include cstring using namespace std; const int N 1e6 10; int n; char g[2][N]; int dist[2][N]; bool st[2][N]; int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int bfs(int i, int j) { int ret 0; memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); // 每次BFS需要重置st数组 dequepairint, int q; q.push_back({i, j}); dist[i][j] 0; while(q.size()) { auto t q.front(); q.pop_front(); int a t.first, b t.second; if(st[a][b]) continue; st[a][b] true; if(g[a][b] #) ret max(ret, dist[a][b]); for(int k 0; k 4; k) { int x a dx[k], y b dy[k]; if(x 0 || x 2 || y 0 || y n) continue; int w (g[x][y] #) ? 0 : 1; if(dist[a][b] w dist[x][y]) { dist[x][y] dist[a][b] w; if(w 0) q.push_front({x, y}); else q.push_back({x, y}); } } } return ret; } int main() { cin g[0] g[1]; n strlen(g[0]); // 找到第一个已有的检测器作为起点 for(int j 0; j n; j) { if(g[0][j] #) { cout bfs(0, j) endl; return 0; } if(g[1][j] #) { cout bfs(1, j) endl; return 0; } } // 如果没有检测器 cout 0 endl; return 0; }