当前位置:   article > 正文

第十四届蓝桥杯C++B组编程题题目以及题解_2024蓝桥杯答案

2024蓝桥杯答案

a.冶炼金属(二分)

思路:

设任意一条冶炼记录投入金属数量为a,产出金属为b.

对于每一条冶炼记录我们都可以得到 一个转换率V的范围:

b<=a/v<b+1即a/b<= v <a/(b+1)

为什么是b+1呢?因为既然能产出b个金属,也就意味着一定不能产出b+1个,所以a/v<b+1

每一条记录都可以得到v的一个区间,我们不断地取交集,可以得到v的可能的最大值max和可能的最小值min。

在这里要注意,得到的max和minb并不就是答案,而是要在这个区间筛选出符合所有冶炼记录的v,再在这些v里面取最大值和最小值就是答案。这一步可以用二分

代码:

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N = 1e4 + 10;
  6. int arr[N][2];//冶炼金属的记录
  7. int main() {
  8. int t;
  9. cin >> t;
  10. int maxv = 1e9;
  11. int minv = 0;
  12. for (int i = 0; i < t; i++) {
  13. int a, b;
  14. cin >> a >> b;
  15. arr[i][0] = a;
  16. arr[i][1] = b;
  17. maxv = min(maxv, a / b);//区间取交集,右端点要不断地取最小值,
  18. minv = max(minv, (a) / (b + 1));//区间取交集,左端点要不断地取最大值,
  19. }
  20. //两次二分分别得到最大值和最小值
  21. int l = minv;
  22. int r = maxv + 1;
  23. int ans1 = 0, ans2 = 0;
  24. while (l + 1 != r) {
  25. int mid = (l + r) >> 1;
  26. int f = 0;
  27. for (int i = 0; i < t; i++) {
  28. if (arr[i][0] / mid != arr[i][1]) {
  29. f = 1;
  30. break;
  31. }
  32. }
  33. if (f) {
  34. l = mid;
  35. }
  36. else r = mid;
  37. }
  38. ans1 = r;
  39. l = minv;
  40. r = maxv + 1;
  41. //int ans1=0,ans2=0;
  42. while (l + 1 != r) {
  43. int mid = (l + r) >> 1;
  44. int f = 0;
  45. for (int i = 0; i < t; i++) {
  46. if (arr[i][0] / mid != arr[i][1]) {
  47. f = 1;
  48. break;
  49. }
  50. }
  51. if (f) {
  52. r = mid;
  53. }
  54. else l = mid;
  55. }
  56. ans2 = l;
  57. cout << ans1 << " " << ans2 << endl;
  58. return 0;
  59. }

b.飞机降落(dfs)

思路:

这题就是求能否存在一个飞机降落的顺序序列,能没有冲突的降落。这里的没有冲突是指,在当前时刻t<=当前飞机的最迟起飞时间(Ti+Di).

由于题目数据很小,飞机的数量最多10,我们可以暴力枚举飞机所有的的降落顺序,再检查是否存在某一个顺序可以让全部飞机降落。

跟枚举全排列的思路是一样的,求一个长度为n且符合要求的飞机序号排列。对于当前的时间t,能不能让序号为u的飞机起飞,如果能则安排这台飞机降落,往下遍历时长度加一,如果不能,则说明这一条排列不行,就不安排这一台飞机,换台飞机试试。反正暴力么,所有情况都不重不漏。

代码:

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. const int N = 15;
  7. int st[N];//标记已经降落的飞机
  8. int a[N][3];//记录每一台飞机的起飞时间、盘旋时间、降落时间
  9. int n;
  10. bool ans;//标记答案
  11. void dfs(int u, int t) {
  12. if (u == n) {//遍历到这里,长度已经够了,说明已经存在一个序列符合答案
  13. ans = true;
  14. return;
  15. }
  16. //安排下一台飞机
  17. for (int i = 1; i <= n; i++) {
  18. if (t > a[i][0] + a[i][1])continue;//不符合要求
  19. if (!st[i] && t <= a[i][0] + a[i][1]) {
  20. st[i] = 1;//标记序号为i的飞机要降落
  21. if (t <= a[i][0])dfs(u + 1, a[i][0] + a[i][2]);//如果当前的t比最早的起飞时间还早,那就等到时间为a[i][0]再降落
  22. else dfs(u + 1, t + a[i][2]);//否则就马上降落,更新时间
  23. st[i] = 0;//回溯
  24. }
  25. }
  26. }
  27. int main() {
  28. int t;
  29. cin >> t;
  30. while (t--) {
  31. cin >> n;
  32. for (int i = 1; i <= n; i++) {
  33. cin >> a[i][0] >> a[i][1] >> a[i][2];
  34. }
  35. memset(st, 0, sizeof st);
  36. ans = false;
  37. dfs(0, 0);
  38. if (ans)cout << "YES" << endl;
  39. else cout << "NO" << endl;
  40. }
  41. return 0;
  42. }

c.接龙序列(线性dp)

思路:

凭感觉就是dp问题,但是需要换一下题意,题目求最少删除多少个数可以满足接龙序列,我们可以求最长的接龙序列的长度,这样再用n减去这个最大值就是最少删除的元素个数了。

类似于求最长上升子序列,先考虑二维状态转移方程

设dp[i][k]为以第i个元素为尾元素且最后一位数位为k的最长接龙序列的长度。

  1. for(int i=1;i<=n;i++){
  2. int k1=gethh(a[i]);//a[i]的第一位数
  3. int k2=a[i]%10;//a[i]的最后一位位数
  4. f[i][k2]=1;//初始化长度为1
  5. for(int j=1;j<i;j++){//从前遍历,更新f[i][k2].
  6. f[i][k2]=max(f[j][k1]+1,f[i][k2]);
  7. ans=max(ans,f[i][k2]);
  8. }
  9. // f[k2]=max(f[k1]+1,f[k2]);
  10. // ans=max(ans,f[k2]);
  11. }

假设一个元素的第一位数是k1,最后一位是k2,那么这个数的上一个数的最后一位数必须是k1,也就是f[j][k1],要取最长,所以 f[i][k2]=max(f[j][k1]+1,f[i][k2]).

优化

显然这种是超时的,能不能优化一层for循环呢?通过观察我们可以发现,对于第i个元素,我们其实没有必要再一直往前遍历,我们只需要找到上一个以k1结尾的数的值,并更新以k2结尾的数的值就行了。所以我们可以用f[i]表示以位数为i结尾的最长接龙序列的长度是多少就好了。

代码:

  1. #include<iostream>
  2. #include<math.h>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int N=1e5+10;
  7. int f[10];
  8. int a[N];
  9. int s[10];
  10. int get_n(int x){//计算x的位数
  11. int res=0;
  12. while(x){
  13. x/=10;
  14. res++;
  15. }
  16. return res;
  17. }
  18. int gethh(int x){//计算x的第一位数
  19. int k=get_n(x);
  20. int hh=x/pow(10,k-1);
  21. return hh;
  22. }
  23. int main(){
  24. int n;
  25. cin>>n;
  26. for(int i=1;i<=n;i++){
  27. cin>>a[i];
  28. }
  29. int ans=0;
  30. for(int i=1;i<=n;i++){
  31. int k1=gethh(a[i]);//a[i]的第一位数
  32. int k2=a[i]%10;//a[i]的最后一位位数
  33. f[k2]=max(f[k1]+1,f[k2]);
  34. ans=max(ans,f[k2]);
  35. }
  36. cout<<n-ans<<endl;
  37. return 0;
  38. }

d.岛屿个数(bfs)

思路:

不同的岛屿比较好判断,但是需要考虑的就是怎么判断某个岛屿是不是子岛屿,也就是当前这个岛屿在不在某个环内。

我们可以优先遍历外面的海水,也就是地图最边框的海水地区。

考虑这样一个事实,如果最外层的海水存在,那么这些海水一定不在环内。且,最外层的海水bfs(只遍历相邻海水)一遍后一定能遍历完整个地图不在环内的海水。

于是乎,bfs一遍最外层的海水并标记后,对于海水而言,我们就能区分,在环内的海水和不在环内的海水。

这样一来,我们再把 在环内的海水全部变成陆地!这样一来,子岛屿和父岛屿就变成一个个整体了。

这个时候我们再计算地图岛屿的数量,就是答案了 

代码:

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<queue>
  5. #include<cstring>
  6. using namespace std;
  7. const int N = 60;
  8. typedef pair<int, int> PII;
  9. int m, n;
  10. char g[N][N];
  11. bool st[N][N];//标记哪些坐标被遍历过了
  12. int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };//遍历岛屿的位移偏移量
  13. int dxx[] = { 0,-1,-1,-1,0,1,1,1 }, dyy[] = { -1,-1,0,1,1,1,0,-1 };//遍历海水的位移偏移量
  14. int ans;
  15. void bfs1(int x, int y) {//第一次遍历海水
  16. queue<PII> q;
  17. q.push({ x,y });
  18. while (!q.empty()) {
  19. int sz = q.size();
  20. for (int i = 0; i < sz; i++) {
  21. auto it = q.front();
  22. q.pop();
  23. int xx = it.first;
  24. int yy = it.second;
  25. // g[xx][yy]=1;
  26. if (st[xx][yy])continue;
  27. st[xx][yy] = true;
  28. for (int j = 0; j < 8; j++) {
  29. int a = dxx[j] + xx;
  30. int b = dyy[j] + yy;
  31. if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] == '0' && !st[a][b]) {
  32. q.push({ a,b });
  33. }
  34. }
  35. }
  36. }
  37. }
  38. void bfs2(int x, int y) {//遍历岛屿
  39. queue<PII> q;
  40. q.push({ x,y });
  41. while (!q.empty()) {
  42. int sz = q.size();
  43. for (int i = 0; i < sz; i++) {
  44. auto it = q.front();
  45. q.pop();
  46. int xx = it.first;
  47. int yy = it.second;
  48. // g[xx][yy]=1;
  49. if (st[xx][yy])continue;
  50. st[xx][yy] = true;
  51. for (int j = 0; j < 4; j++) {
  52. int a = dx[j] + xx;
  53. int b = dy[j] + yy;
  54. if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] == '1' && !st[a][b]) {
  55. q.push({ a,b });
  56. }
  57. }
  58. }
  59. }
  60. return;
  61. }
  62. int main() {
  63. int t;
  64. cin >> t;
  65. while (t--) {
  66. memset(st, false, sizeof st);
  67. cin >> m >> n;
  68. for (int i = 0; i < m; i++) {//存图
  69. for (int j = 0; j < n; j++) {
  70. cin >> g[i][j];
  71. }
  72. }
  73. //开始遍历一定不在环内的海水
  74. for (int j = 0; j < n; j++) {
  75. if (!st[0][j] && g[0][j] == '0') {
  76. bfs1(0, j);
  77. }
  78. if (!st[m - 1][j] && g[m - 1][j] == '0') {
  79. bfs1(m - 1, j);
  80. }
  81. }
  82. for (int i = 0; i < m; i++) {
  83. if (!st[i][0] && g[i][0] == '0') {
  84. bfs1(i, 0);
  85. }
  86. if (!st[i][n - 1] && g[i][n - 1] == '0') {
  87. bfs1(i, n - 1);
  88. }
  89. }
  90. //把在环内的海水设置为陆地
  91. for (int i = 0; i < m; i++) {
  92. for (int j = 0; j < n; j++) {
  93. if (!st[i][j]) {
  94. g[i][j] = '1';
  95. }
  96. }
  97. }
  98. ans = 0;
  99. //计算岛屿数量
  100. for (int i = 0; i < m; i++) {
  101. for (int j = 0; j < n; j++) {
  102. if (!st[i][j] && g[i][j] == '1') {
  103. ans++;
  104. bfs2(i, j);
  105. }
  106. }
  107. }
  108. cout << ans << endl;
  109. }
  110. return 0;
  111. }

e.字串简写(前缀和)

思路:

遍历整个字符串,用一个s数组维护c1的区间和s[i]表示string S中0到i的c1的个数。再遍历一遍字符串S,如果遍历到了c2,前面有多少个c1就表示有多少个不同的子串能符合题目要求。也就是计算出以当前位置为末尾,长度大于k的的子串的c1的个数,就是s[i-k+1]。

代码:

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<string>
  5. using namespace std;
  6. int main()
  7. {
  8. int k;
  9. char a, b;
  10. string str;
  11. cin >> k >> str >> a >> b;
  12. int n = str.size();
  13. //int ans;
  14. vector<long long > s(n, 0);
  15. if (str[0] == a)s[0] = 1;
  16. for (int i = 1; i < n; i++) {
  17. if (str[i] == a)s[i] = 1;//如果是c1我们就把这个位置标记为1,方便前缀和计算
  18. s[i] += s[i - 1];
  19. }
  20. long long ans = 0;
  21. for (int i = 0; i < n; i++) {
  22. if (i >= k - 1 && str[i] == b) {
  23. ans += s[i - k + 1];
  24. }
  25. }
  26. cout << ans << endl;
  27. return 0;
  28. }

f整数删除(优先队列,双链表)

思路:

这题需要思考如何每次都能找到最小的数?以及删除一个数后如何调整剩下元素的相对位置?

第一点我们可以用优先队列来解决,也就是最小堆。顺便将原始下标存进去。

第二点我们可以用双链表来存储下标的位置关系。用l[i],r[i]分别表示下标为i的元素的右边和左边的元素的下标,这样一来,一旦我们决定要删除某一个数,修改r[i]和l[i]就可以继续维护一个彼此相邻的数组了。

除此之外,由于每删除一个数,隔壁的数的值都要加上这个数,我们又不好直接取出隔壁的数(都放在优先队列里的),所以我们可再维护一个数组cnt[i]表示下标为i的元素还需要增加的值

值得注意的是,我们需要判断当前取出的元素有可能不是最小值,因为有可能他还要加上cnt[i],所以取出来一个数后,要判断如果cnt[i]不为0的,表示之前删除过这个数的隔壁的数,所以要将取出来的数加上cnt[i]后再放回去,并将cnt[i]置为0。如果cnt[i]为0,意味着目前取出来的数一定是最小值,那么我们就把它删除,并修改其隔壁数的r[i]和l[i],以及cnt[i].

最后队列剩下的元素我们还需要根据按下标顺序输出

代码

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<queue>
  4. #include<vector>
  5. using namespace std;
  6. const int N=5e5+10;
  7. typedef long long LL;
  8. typedef pair<LL,int> PII;
  9. LL cnt[N];
  10. int l[N],r[N];
  11. LL a[N];
  12. int main(){
  13. int n,k;
  14. cin>>n>>k;
  15. priority_queue<PII,vector<PII>,greater<PII>>q;//最小堆
  16. r[0]=1;//边界0
  17. l[n+1]=n;//边界n+1
  18. for(int i=1;i<=n;i++){
  19. scanf("%lld",&a[i]);
  20. q.push({a[i],i});//元素的值在左边,最小堆默认按左边第一个值排序
  21. r[i]=i+1;//模拟双链表
  22. l[i]=i-1;
  23. }
  24. while(q.size()!=n-k){//要删除k个元素
  25. auto it=q.top();
  26. q.pop();
  27. LL v=it.first;
  28. int dix=it.second;
  29. if(cnt[dix]){
  30. v+=cnt[dix];
  31. q.push({v,dix});
  32. cnt[dix]=0;
  33. }else{
  34. cnt[l[dix]]+=v;//修改隔壁的增量
  35. cnt[r[dix]]+=v;
  36. l[r[dix]]=l[dix];//双链表的删除操作
  37. r[l[dix]]=r[dix];
  38. }
  39. }
  40. while(!q.empty()){//剩下元素按下标存入数组a中
  41. auto it=q.top();
  42. q.pop();
  43. a[it.second]=it.first;
  44. }
  45. int ne=0;
  46. while(r[ne]!=n+1){//遍历双链表
  47. printf("%lld ",a[r[ne]]+cnt[r[ne]]);
  48. ne=r[ne];
  49. }
  50. return 0;
  51. }

g.景区导游(LCA)

思路:

如何计算树中任意两个点u,v的距离?首先用一个dis数组存每个节点到根节点的距离,再找到这两个节点的最近公共祖先节点k,它们之间的距离就等于 dis[u]+dis[v]-2*dis[k]

最近公共祖先用LCA算法

答案求跳过Ai节点的路径总长度,我们可以先把总路径长度ans求出来,例如样例的路线 2-->6--> 5--> 1 .

假如跳过节点5,路径长度就变成了2-->6的长度+ 6-->1的长度

设path(v,u)表示两个节点在树上的距离

也就是说假如我们要跳过a[i],那么剩下路线总长度为

ans-getpath(a[i], a[i - 1])-getpath(a[i + 1], a[i])+ getpath(a[i + 1], a[i - 1])

代码:

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. typedef long long LL;
  7. const int N = 1e5 + 10;
  8. int f[N][21];
  9. int deth[N];
  10. LL dis[N];
  11. int a[N];
  12. vector<int>e[N], w[N];
  13. void dfs(int u, int fa) {
  14. deth[u] = deth[fa] + 1;
  15. f[u][0] = fa;
  16. for (int i = 1; i <= 20; i++) {
  17. f[u][i] = f[f[u][i - 1]][i - 1];
  18. }
  19. int sz = e[u].size();
  20. for (int i = 0; i < sz; i++) {
  21. int v = e[u][i], s = w[u][i];
  22. if (v == fa)continue;
  23. dis[v] = dis[u] + s;
  24. //cout<<u<<"-->"<<v<<" ll "<<s<<" kk "<<dis[u]<<endl;
  25. dfs(v, u);
  26. }
  27. }
  28. int LCA(int u, int v) {
  29. if (deth[u] < deth[v])swap(u, v);
  30. for (int i = 20; i >= 0; i--) {
  31. if (deth[f[u][i]] >= deth[v]) {
  32. u = f[u][i];
  33. }
  34. }
  35. if (u == v)return u;
  36. for (int i = 20; i >= 0; i--) {
  37. if (f[u][i] != f[v][i]) {
  38. u = f[u][i];
  39. v = f[v][i];
  40. }
  41. }
  42. return f[u][0];
  43. }
  44. LL getpath(int u, int v) {
  45. if (!u || !v)return 0;
  46. return dis[u] + dis[v] - 2 * dis[LCA(u, v)];
  47. }
  48. int main() {
  49. int n, k;
  50. cin >> n >> k;
  51. for (int i = 0; i < n - 1; i++) {
  52. int a, b, c;
  53. cin >> a >> b >> c;
  54. e[a].push_back(b);
  55. w[a].push_back(c);
  56. e[b].push_back(a);
  57. w[b].push_back(c);
  58. }
  59. dfs(1, 0);
  60. LL ans = 0;
  61. cin >> a[0];
  62. for (int i = 1; i < k; i++) {
  63. cin >> a[i];
  64. ans += getpath(a[i], a[i - 1]);
  65. }
  66. for (int i = 0; i < k; i++) {
  67. LL d1 = 0;
  68. if (i != 0)d1 += getpath(a[i], a[i - 1]);
  69. if (i != k - 1)d1 += getpath(a[i + 1], a[i]);
  70. LL d2 = 0;
  71. if (i != 0 && i != k - 1) {
  72. d2 += getpath(a[i + 1], a[i - 1]);
  73. }
  74. cout << ans - d1 + d2 << " ";
  75. }
  76. return 0;
  77. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/705627
推荐阅读
相关标签
  

闽ICP备14008679号