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

目录

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

代码：

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

代码：

 题目三（治炼金属）：

代码：

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

代码：

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

代码：

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

 代码：

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

代码：

题目八（整数删除）:

代码：

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

代码： #include <iostream> using namespace std; int main() { int array[100] = { 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 }; int Month[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int ans = 0; for (int month = 1; month <= 12; ++month)//枚举月 { for (int day = 1; day <= Month[month]; ++day)//枚举天 { int date[8] = { 2, 0, 2, 3, month / 10, month % 10, day / 10, day % 10 };//把八位数得出 int k = 0; for (int i = 0; i < 100; ++i) //遍历100个数，是否能满足有该天 { if (array[i] == date[k]) //满足该位 { ++k;//下一位 if (k == 8) //等于8，即满足该年月日，答案加一 { ans++; break; } } } } } cout << ans; return 0; }  题目二（01串的熵 模拟）：

代码： #include <iostream>//H（s）= -(0的个数)/(总长度)*log2((0的个数)/(总长度))*0的个数-(1的个数)/(总长度)*log2((1的个数)/(总长度))*1的个数 #include <algorithm> #include <cmath> using namespace std; int main() { int n = 23333333;//0出现的次数更少 for (int i = 1; i < n / 2; ++i) { double a = i * 1.0 / n;//0的占比 double b = (n - i) * 1.0 / n;//1的占比 double res1,res2; res1 = 0 - (a * log2(a) * i);//求0的部分 res2 = 0 - b * log2(b) * (n - i);//求1的部分 if (abs((res1+res2) - 11625907.5798) < 0.0001)//差距在0.000内 { cout << i << endl; break; } } return 0; }  题目三（治炼金属）：

代码： #include <iostream> #include <algorithm> using namespace std; struct node { int x, s; }; bool cmp(node a, node b)//v小的排前 { return a.x / a.s < b.x / b.s; } int main() { int n; cin >> n; int maxx = 1e9; node a[10100]; for (int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].s; } sort(a + 1, a + 1 + n, cmp);//能满足所有的，且v为最大 maxx = a[1].x / a[1].s; int minn = 0; for (int z = maxx; z >= 1; z--)//由最大的往前算，递减，直到有一个不满足 { int flag = 0; for (int i = 1; i <= n; i++) { if (a[i].x / z > a[i].s) { flag = 1; minn = z; break; } } if (flag == 1) break; } cout << minn + 1 << " " << maxx; }  题目四（飞机降落 深度搜索）：

代码： #include <iostream> #include <vector> using namespace std; struct plane// 创建飞机结构体变量 { int t, d, l; }; bool vis[15]; // true表示飞机降落，false表示飞机未降落 bool flag; // 标记是否全部安全降落 vector<plane> p(15); int m, cnt; void dfs(int cnt,int last) // lasttime表示此前所有飞机降落所需的单位时间 { if (cnt == m)//所有飞机都可降落 { flag = true; return; } for (int i = 0; i < m; i++)//遍历所有飞机 { if (!vis[i] && p[i].t + p[i].d >= last) // 还未降落且只有最迟降落时间（来的时刻+盘旋时间） > lasttime 的飞机才可以安全降落 { vis[i] = true; dfs(cnt + 1, max(last, p[i].t) + p[i].l); vis[i] = false; } } } int main() { int T; cin >> T; while (T--) { cin >> m; for (int i = 0; i < m; ++i) cin >> p[i].t >> p[i].d >> p[i].l; flag = false; dfs(0, 0); if (flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0; } 题目五（接龙数列 动态规划）：

代码： #include <iostream>//动态规划，类0、1背包问题 #include <string> using namespace std; int dp[10];//第n个时以i结尾的最长接龙序列 int main() { int n; cin >> n; string s; int m = 0; for (int i = 0; i < n; i++) { cin >> s; int x = s[0] - '0', y = s.back() - '0';//x表示该数的首字母，y表示该数的最后一个字母 //除了以y结尾的，其它不变 dp[y] = max(dp[x] + 1, dp[y]);//dp[x]+1表示选该数字时的最长序列，dp[y]表示不选该数字时的最长序列，继承 m = max(m, dp[y]);//每次比较，记录最大值 } cout << n - m << endl; return 0; }  题目六（岛屿个数 广度优先）：

 代码： #include<iostream> #include<queue> #include<cstring> using namespace std; const int N = 77; string s[N]; int book[N][N]; int m, n, ans=0; int dx[8] = { 0,0,1,-1,1,1,-1,-1 }; int dy[8] = { 1,-1,0,0,1,-1,1,-1 }; int check(int x,int y)//通过海水（0）是否能到达边界判断这个岛屿是否在环岛内 { queue<pair<int, int>>q; q.push({ x, y }); int vis[N][N]; memset(vis, 0, sizeof(vis));//访问数组，初始化为0 while (!q.empty()) { x = q.front().first, y = q.front().second; q.pop(); if (x == 1 || x == n || y == 1 || y == m)//到边界，则不在环岛内 return 1; for (int i = 0; i < 8; i++) { int tx = x + dx[i], ty = y + dy[i]; if (vis[tx][ty] == 1 || s[tx][ty] == '1')//边界条件 continue; vis[tx][ty] = 1; q.push({ tx,ty }); } } return 0; } void bfs(int x,int y)//遍历这个岛屿 { queue<pair<int, int>>q; q.push({ x,y }); book[x][y] = 1; while (!q.empty()) { x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int tx = x + dx[i], ty = y + dy[i]; if (tx<1 || ty<1 || tx>n || ty>m || book[tx][ty] == 1 || s[tx][ty] == '0')//边界条件 continue; book[tx][ty] = 1; q.push({ tx,ty }); } } } void solve() { memset(book, 0, sizeof(book));//访问数组，初始为0 cin >> n >> m; for (int i = 1; i <= n; i++) cin >> s[i], s[i] = " " + s[i]; for(int i=1;i<=n;i++) for (int j = 1; j <= m; j++) { if (book[i][j] == 0 && s[i][j] == '1')//没访问过且为陆地 { bfs(i, j); if (check(i, j))//判断是否在环岛内，不在则加一 ans++; } } cout << ans << endl; } int main() { int T; cin >> T; while (T--) { ans = 0; solve(); } } 题目七（子串简写 尺取法）：

代码： #include <iostream>//尺取法 using namespace std; int k, t; string s; long long sum = 0; int main() { char c1, c2; cin >> k >> s >> c1 >> c2; for (int j = 0; j < s.length(); j++) { if (s[j] == c1) //t记录j及以前c1的个数 t++; if (s[j + k - 1] == c2) //刚好满足k之后的是否为c2 sum += t; } cout << sum; return 0; } 题目八（整数删除）:

代码： #include<iostream> #include<vector> #include<queue> #include<functional>//greater降序排序，less升序排序 #define int long long using namespace std; typedef pair<int, int> pii; const int N = 5e5 + 10; int a[N], l[N], r[N], st[N];//l存左下标，r存右下标 signed main() { int n, k; cin >> n >> k; priority_queue<pii, vector<pii>, greater<pii>> q;//最小堆排序 for (int i = 0; i < n; i++) { cin >> a[i]; q.push({ a[i],i });//存值和下标 st[i] = a[i];//存值 l[i] = i - 1; r[i] = i + 1; if (r[i] == n) r[i] = -1; } while (k)//k次操作 { pii t = q.top();//取对顶 q.pop(); if (t.first != st[t.second])//值与之前不相等，则把新值，下标存入，重新排序 { q.push({ st[t.second],t.second }); continue; } k--; int pos = t.second;//取该次的下标 if (l[pos] >= 0) st[l[pos]] += t.first;//左加值 if (r[pos] >= 0) st[r[pos]] += t.first;//右加值 if (l[pos] >= 0) r[l[pos]] = r[pos];//该左边值的右下标 if (r[pos] >= 0) l[r[pos]] = l[pos];//该右边值的左下标 st[pos] = -1;//标记为-1，表示移除队列 } for (int i = 0; i < n; i++)//不等与-1的，按序输出 { if (st[i] != -1) cout << st[i] << ' '; } return 0; }