devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十四届蓝桥杯（八题C++ 题目+代码+注解）_十四届蓝桥杯国赛题目 c++

作者：从前慢现在也慢 | 2024-04-25 02:14:52

赞

踩

十四届蓝桥杯国赛题目 c++

目录

题目一（日期统计 纯暴力）：

代码：

 题目二（01串的熵 模拟）：

代码：

 题目三（治炼金属）：

代码：

 题目四（飞机降落 深度搜索）：

代码：

题目五（接龙数列 动态规划）：

代码：

 题目六（岛屿个数 广度优先）：

 代码：

题目七（子串简写 尺取法）：

代码：

题目八（整数删除）:

代码：

题目一（日期统计 纯暴力）：

代码：

  1. #include <iostream>
  2. using namespace std;
  3. int main() 
  4. {
  5.     int array[100] = 
  6.     {
  7.         5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
  8.         5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
  9.         2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
  10.         8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
  11.         1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
  12.     };
  13.  
  14.     int Month[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  15.     int ans = 0;
  16.  
  17.     for (int month = 1; month <= 12; ++month)//枚举月
  18.     {
  19.         for (int day = 1; day <= Month[month]; ++day)//枚举天
  20.         {
  21.             int date[8] = { 2, 0, 2, 3, month / 10, month % 10, day / 10, day % 10 };//把八位数得出
  22.             int k = 0;
  23.  
  24.             for (int i = 0; i < 100; ++i) //遍历100个数，是否能满足有该天
  25.             {
  26.                 if (array[i] == date[k]) //满足该位
  27.                 {
  28.                     ++k;//下一位
  29.                     if (k == 8) //等于8，即满足该年月日，答案加一
  30.                     {
  31.                         ans++;
  32.                         break;
  33.                     }
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     cout << ans;
  39.     return 0;
  40. }

 题目二（01串的熵 模拟）：

代码：

  1. #include <iostream>//H（s）= -(0的个数)/(总长度)*log2((0的个数)/(总长度))*0的个数-(1的个数)/(总长度)*log2((1的个数)/(总长度))*1的个数
  2. #include <algorithm>
  3. #include <cmath>
  4. using namespace std;
  5. int main()
  6. {
  7.     int n = 23333333;//0出现的次数更少
  8.     for (int i = 1; i < n / 2; ++i)
  9.     {
  10.         double a = i * 1.0 / n;//0的占比
  11.         double b = (n - i) * 1.0 / n;//1的占比
  12.         double res1,res2;
  13.         res1 = 0 - (a * log2(a) * i);//求0的部分
  14.         res2 = 0 - b * log2(b) * (n - i);//求1的部分
  15.         if (abs((res1+res2) - 11625907.5798) < 0.0001)//差距在0.000内
  16.         {
  17.             cout << i << endl;
  18.             break;
  19.         }
  20.     }
  21.     return 0;
  22. }

 题目三（治炼金属）：

代码：

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. struct node
  5. {
  6.     int x, s;
  7. };
  8. bool cmp(node a, node b)//v小的排前
  9. {
  10.     return a.x / a.s < b.x / b.s;
  11. }
  12. int main()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     int maxx = 1e9;
  17.     node a[10100];
  18.     for (int i = 1; i <= n; i++)
  19.     {
  20.         cin >> a[i].x >> a[i].s;
  21.     }
  22.     sort(a + 1, a + 1 + n, cmp);//能满足所有的，且v为最大
  23.     maxx = a[1].x / a[1].s;
  24.     int minn = 0;
  25.     for (int z = maxx; z >= 1; z--)//由最大的往前算，递减，直到有一个不满足
  26.     {
  27.         int flag = 0;
  28.         for (int i = 1; i <= n; i++)
  29.         {
  30.             if (a[i].x / z > a[i].s)
  31.             {
  32.                 flag = 1;
  33.                 minn = z;
  34.                 break;
  35.             }
  36.         }
  37.         if (flag == 1)
  38.             break;
  39.     }
  40.     cout << minn + 1 << " " << maxx;
  41. }

 题目四（飞机降落 深度搜索）：

代码：

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. struct plane// 创建飞机结构体变量
  5. {
  6.     int t, d, l;
  7. };
  8. bool vis[15];  // true表示飞机降落，false表示飞机未降落
  9. bool flag;  // 标记是否全部安全降落
  10. vector<plane> p(15);
  11. int m, cnt;
  12. void dfs(int cnt,int last)  // lasttime表示此前所有飞机降落所需的单位时间
  13. {
  14.     if (cnt == m)//所有飞机都可降落
  15.     {
  16.         flag = true;
  17.         return;
  18.     }
  19.     for (int i = 0; i < m; i++)//遍历所有飞机
  20.     {
  21.         if (!vis[i] && p[i].t + p[i].d >= last)  // 还未降落且只有最迟降落时间（来的时刻+盘旋时间） > lasttime 的飞机才可以安全降落
  22.         {
  23.             vis[i] = true;
  24.             dfs(cnt + 1, max(last, p[i].t) + p[i].l);
  25.             vis[i] = false;
  26.         }
  27.     }
  28. }
  29.  
  30. int main()
  31. {
  32.     int T;
  33.     cin >> T;
  34.     while (T--)
  35.     {
  36.         cin >> m;
  37.         for (int i = 0; i < m; ++i)
  38.             cin >> p[i].t >> p[i].d >> p[i].l;
  39.         flag = false;
  40.         dfs(0, 0);
  41.         if (flag)
  42.             cout << "YES" << endl;
  43.         else
  44.             cout << "NO" << endl;
  45.     }
  46.     return 0;
  47. }

题目五（接龙数列 动态规划）：

代码：

  1. #include <iostream>//动态规划，类0、1背包问题
  2. #include <string>
  3. using namespace std;
  4. int dp[10];//第n个时以i结尾的最长接龙序列
  5. int main()
  6. {
  7.     int n;
  8.     cin >> n;
  9.     string s;
  10.     int m = 0;
  11.     for (int i = 0; i < n; i++) 
  12.     {
  13.         cin >> s;
  14.         int x = s[0] - '0', y = s.back() - '0';//x表示该数的首字母，y表示该数的最后一个字母
  15.         //除了以y结尾的，其它不变
  16.         dp[y] = max(dp[x] + 1, dp[y]);//dp[x]+1表示选该数字时的最长序列，dp[y]表示不选该数字时的最长序列，继承
  17.         m = max(m, dp[y]);//每次比较，记录最大值
  18.     }
  19.     cout << n - m << endl;
  20.     return 0;
  21. }

 题目六（岛屿个数 广度优先）：

 代码：

  1. #include<iostream>
  2. #include<queue>
  3. #include<cstring>
  4. using namespace std;
  5. const int N = 77;
  6. string s[N];
  7. int book[N][N];
  8. int m, n, ans=0;
  9. int dx[8] = { 0,0,1,-1,1,1,-1,-1 };
  10. int dy[8] = { 1,-1,0,0,1,-1,1,-1 };
  11. int check(int x,int y)//通过海水（0）是否能到达边界判断这个岛屿是否在环岛内
  12. {
  13. 	queue<pair<int, int>>q;
  14. 	q.push({ x, y });
  15. 	int vis[N][N];
  16. 	memset(vis, 0, sizeof(vis));//访问数组，初始化为0
  17. 	while (!q.empty())
  18. 	{
  19. 		x = q.front().first, y = q.front().second;
  20. 		q.pop();
  21. 		if (x == 1 || x == n || y == 1 || y == m)//到边界，则不在环岛内
  22. 			return 1;
  23. 		for (int i = 0; i < 8; i++)
  24. 		{
  25. 			int tx = x + dx[i], ty = y + dy[i];
  26. 			if (vis[tx][ty] == 1 || s[tx][ty] == '1')//边界条件
  27. 				continue;
  28. 			vis[tx][ty] = 1;
  29. 			q.push({ tx,ty });
  30. 		}
  31. 	}
  32. 	return 0;
  33. }
  34. void bfs(int x,int y)//遍历这个岛屿
  35. {
  36. 	queue<pair<int, int>>q;
  37. 	q.push({ x,y });
  38. 	book[x][y] = 1;
  39. 	while (!q.empty())
  40. 	{
  41. 		x = q.front().first, y = q.front().second;
  42. 		q.pop();
  43. 		for (int i = 0; i < 4; i++)
  44. 		{
  45. 			int tx = x + dx[i], ty = y + dy[i];
  46. 			if (tx<1 || ty<1 || tx>n || ty>m || book[tx][ty] == 1 || s[tx][ty] == '0')//边界条件
  47. 				continue;
  48. 			book[tx][ty] = 1;
  49. 			q.push({ tx,ty });
  50. 		}
  51. 	}
  52. }
  53. void solve()
  54. {
  55. 	memset(book, 0, sizeof(book));//访问数组，初始为0
  56. 	cin >> n >> m;
  57. 	for (int i = 1; i <= n; i++)
  58. 		cin >> s[i], s[i] = " " + s[i];
  59. 	for(int i=1;i<=n;i++)
  60. 		for (int j = 1; j <= m; j++)
  61. 		{
  62. 			if (book[i][j] == 0 && s[i][j] == '1')//没访问过且为陆地
  63. 			{
  64. 				bfs(i, j);
  65. 				if (check(i, j))//判断是否在环岛内，不在则加一
  66. 					ans++;
  67. 			}
  68. 		}
  69. 	cout << ans << endl;
  70. }
  71. int main()
  72. {
  73. 	int T;
  74. 	cin >> T;
  75. 	while (T--)
  76. 	{
  77. 		ans = 0;
  78. 		solve();
  79. 	}
  80. }

题目七（子串简写 尺取法）：

代码：

  1. #include <iostream>//尺取法
  2. using namespace std;
  3. int k, t;
  4. string s;
  5. long long sum = 0;
  6. int main()
  7. {
  8.     char c1, c2;
  9.     cin >> k >> s >> c1 >> c2;
  10.     for (int j = 0; j < s.length(); j++)
  11.     {
  12.         if (s[j] == c1)  //t记录j及以前c1的个数
  13.             t++;
  14.         if (s[j + k - 1] == c2) //刚好满足k之后的是否为c2
  15.             sum += t;
  16.     }
  17.     cout << sum;
  18.     return 0;
  19. }

题目八（整数删除）:

代码：

  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<functional>//greater降序排序，less升序排序
  5. #define int long long
  6. using namespace std;
  7. typedef pair<int, int> pii;
  8. const int N = 5e5 + 10;
  9. int a[N], l[N], r[N], st[N];//l存左下标，r存右下标
  10. signed main()
  11. {
  12.     int n, k;
  13.     cin >> n >> k;
  14.     priority_queue<pii, vector<pii>, greater<pii>> q;//最小堆排序
  15.     for (int i = 0; i < n; i++)
  16.     {
  17.         cin >> a[i];
  18.         q.push({ a[i],i });//存值和下标
  19.         st[i] = a[i];//存值
  20.         l[i] = i - 1;
  21.         r[i] = i + 1;
  22.         if (r[i] == n) 
  23.             r[i] = -1;
  24.     }
  25.     while (k)//k次操作
  26.     {
  27.         pii t = q.top();//取对顶
  28.         q.pop();
  29.         if (t.first != st[t.second])//值与之前不相等，则把新值，下标存入，重新排序
  30.         {
  31.             q.push({ st[t.second],t.second });
  32.             continue;
  33.         }
  34.         k--;
  35.         int pos = t.second;//取该次的下标
  36.         if (l[pos] >= 0) st[l[pos]] += t.first;//左加值
  37.         if (r[pos] >= 0) st[r[pos]] += t.first;//右加值
  38.         if (l[pos] >= 0) r[l[pos]] = r[pos];//该左边值的右下标
  39.         if (r[pos] >= 0) l[r[pos]] = l[pos];//该右边值的左下标
  40.         st[pos] = -1;//标记为-1，表示移除队列
  41.     }
  42.     for (int i = 0; i < n; i++)//不等与-1的，按序输出
  43.     {
  44.         if (st[i] != -1)
  45.             cout << st[i] << ' ';
  46.     }
  47.     return 0;
  48. }

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号