蓝桥杯-02-2023蓝桥杯c/c++省赛B组题目

参考

2023 年第十四届蓝桥杯 C/C++ B组省赛题解
2023蓝桥杯c/c++省赛B组题目(最全版)：

A：日期统计

这题方法应该很多，没有和别人讨论想法。我的解法思路是：先 load 函数生成所有这一年的合法日期，然后枚举所有可以从数据中拿到的八位日期，检查它是否在合法日期的集合中。

这里枚举到四位，即年份的时候要判断一下，不然可能数据太多要跑很久。

注意要去重！不知道有多少冤大头痛失这 5 分。（原题里特意加粗了不重复）

// 日期统计
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5+5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;// 235set<int> S;  // 记录一年中合法的日期
set<int> M;  // 记录出现的日期，自带去重// 生成数据
int mon[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void load() {for (int i = 1; i <= 12; i++) {for (int j = 1; j <= mon[i-1]; j++) {S.insert(2023 * 10000 + i * 100 + j);}}
}void solve() {const int n = 100;int a[256];for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cout << a[i] << ' ';}cout << endl;for (int _1 = 0; _1 < n; _1++) {for (int _2 = _1 + 1; _2 < n; _2++) {for (int _3 = _2 + 1; _3 < n; _3++) {for (int _4 = _3 + 1; _4 < n; _4++) {int x = 0;x = x * 10 + a[_1];x = x * 10 + a[_2];x = x * 10 + a[_3];x = x * 10 + a[_4];if (x != 2023) continue;  // 这里先判断一下合法，否则程序可能跑不动for (int _5 = _4 + 1; _5 < n; _5++) {for (int _6 = _5 + 1; _6 < n; _6++) {for (int _7 = _6 + 1; _7 < n; _7++) {for (int _8 = _7 + 1; _8 < n; _8++) {int x = 0;x = x * 10 + a[_1];x = x * 10 + a[_2];x = x * 10 + a[_3];x = x * 10 + a[_4];x = x * 10 + a[_5];x = x * 10 + a[_6];x = x * 10 + a[_7];x = x * 10 + a[_8];// 如果这个日期是这年的合法日期if (S.count(x)) {M.insert(x);}}}}}}}}}cout << M.size() << endl;
}int32_t main() {// 该文件是复制下来的题目给的数据freopen("A.txt", "r", stdin);load();cout << S.size() << endl;solve();return 0;
}

B: 01 串的熵

用Excel做比较方便，让我看看有谁？哈哈哈哈哈

答案当然就是 11027421了！！！！！

C: 冶炼金属

// 冶炼金属
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;void solve() {int n;cin >> n;int min_ = -INF - 1, max_ = INF;for (int i = 0; i < n; i++) {int x, y;cin >> x >> y;min_ = max(min_, x / (y + 1) + 1);  // 求左边界的并max_ = min(max_, x / y);            // 求右边界的并}cout << min_ << " " << max_ << endl;
}int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);solve();return 0;
}

#include <iostream>
using namespace std;
#include<cstdio>
int main(){long long n,a,b,t,t1;long long max=0,min=9999999999;cin >> n;for(int i = 0;i <n;i++){cin >> a >> b;t=a/b;if(t <= min){min = t;}t1 = a/(b+1); if(t1 >= max){max = t1;}}printf("%lld %lld",max+1,min);return 0;
}

D: 飞机降落

// 飞机降落
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 15;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;struct Air {// 最早降落时间, 最迟降落时间, 降落过程耗时int st, ed, len;
} air[MAX];int n;
bool vis[MAX];
bool dfs(int x, int pos) {if (x >= n) return true;for (int i = 0; i < n; i++) {// 如果 i 没有用过，且 i 最迟降落时间在前者的完成这个降落流程之后if (not vis[i] and pos <= air[i].ed) {  vis[i] = true;// 在条件允许的情况下后者尽早降落为后者提供，要两类讨论，这里算有一点点贪心bool tmp = dfs(x+1, max(air[i].st, pos) + air[i].len);  vis[i] = false;if (tmp) return true;}}return false;
}void solve() {cin >> n;for (int i = 0; i < n; i++) {cin >> air[i].st >> air[i].ed >> air[i].len;air[i].ed += air[i].st;}bool res = dfs(0, 0);if (res) {cout << "YES" << endl;} else {cout << "NO" << endl;}
}int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t;cin >> t;while (t--)solve();return 0;
}

E: 接龙数列

// 接龙序列
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;int res[10] = {0};void solve() {int n;cin >> n;for (int i = 0; i < n; i++) {int x;cin >> x;int tail = x % 10;  // 计算末尾int head;while (x) {head = x % 10;x /= 10;}  // 计算首位res[tail] = max(res[tail], res[head] + 1);  // 状态转移方程}int max_ = 0;for (int i = 0; i < 10; i++) {max_ = max(max_, res[i]);  // 获取最长接龙序列} cout << n - max_ << endl;
}int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);solve();return 0;
}

F: 岛屿个数

// 岛屿个数
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 55;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;char map_[MAX][MAX];              // 地图
bool track[MAX][MAX] = {false};   // 访问标记
bool outsea[MAX][MAX] = {false};  // 外海标记
struct XY {int x, y;
} nxt[] = {{1, 0},{-1, 0},{0, 1},{0, -1},{1, 1},{-1, 1},{1, -1},{-1, -1},
};void solve() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> map_[i];}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {track[i][j] = false;outsea[i][j] = false;}}// 预处理外海for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map_[i][j] == '1' or track[i][j]) continue;bool yep = false;queue<XY> que, arr;track[i][j] = true;que.push({i, j});arr.push({i, j});  // 记录搜索到的所有海域while (not que.empty()) {XY pos = que.front();que.pop();// 注意：海域搜索可以往八个方向走，陆地搜索只能朝四个方向for (int i = 0; i < 8; i++) {XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {if (map_[nw.x][nw.y] == '0' and track[nw.x][nw.y] == false) {track[nw.x][nw.y] = true;que.push(nw);arr.push(nw);}} else {yep = true;  // 如果有一次搜索到地图外，标记此次搜索的所有区域为外海}}}if (yep) {while (not arr.empty()) {XY pos = arr.front();arr.pop();outsea[pos.x][pos.y] = true;  // 标记搜索到的海域为外海}}}}// 别忘了清空访问标记for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {track[i][j] = false;}}// 处理岛屿int cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map_[i][j] == '0' or track[i][j]) continue;bool yep = false;queue<XY> que;track[i][j] = true;que.push({i, j});while (not que.empty()) {XY pos = que.front();que.pop();for (int i = 0; i < 4; i++) {XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {if (map_[nw.x][nw.y] == '1') {if (track[nw.x][nw.y] == false) {track[nw.x][nw.y] = true;que.push(nw);}} else {if (outsea[nw.x][nw.y]) {yep = true;  // 搜索到外海为外岛}}} else {yep = true;  // 搜索到边界外为外岛}}}if (yep) {cnt++;  // 外岛计数}}}cout << cnt << endl;
}int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t;cin >> t;while (t--)solve();return 0;
}

G: 子串简写

// 子串简写
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
#ifdef _DEBUG
#pragma GCC optimize(2)
#endif
using namespace std;
const int MAX = 5e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;int aa[MAX], cnt_aa = 0;
int bb[MAX], cnt_bb = 0;// binary_search 二分查找
int bs(int x) {int l = 0, r = cnt_bb - 1;while (l <= r) {int mid = l + r >> 1;if (bb[mid] < x) {l = mid + 1;} else {r = mid - 1;}}return l;
}void solve() {int k;cin >> k;string s;cin >> s;int n = s.size();char a, b;cin >> a >> b;for (int i = 0; i < n; i++) {if (s[i] == a) {aa[cnt_aa++] = i;  // 转储 c1 位置序列}if (s[i] == b) {bb[cnt_bb++] = i;  // 转储 c2 位置序列}}int res = 0;for (int i = 0; i < cnt_aa; i++) {res += cnt_bb - bs(aa[i] + k - 1);  // 记录有效贡献}cout << res << endl;
}int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);solve();return 0;
}

#include<iostream>
using namespace std;
int main(){string s;string a,b;int n;int ans = 0;cin >> n;cin >> s >> a >> b;for(int i = 0;i < s.length();i++){for(int j = i+3;j<s.length();j++){if(s[i]==a[0]){if(s[j] == b[0]){ans++;}}}}cout << ans;return 0;
}

输出为：

仅供参考，个人看法。反正结果正确，理解万岁，大家有什么更好的想法，欢迎评论区交流。。评论区见。

H: 整数删除

// 整数删除
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
#ifdef _DEBUG
// #pragma GCC optimize(2)
#endif
using namespace std;
const int MAX = 5e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;
int a[MAX];
int left_[MAX], right_[MAX];  // 仿链表结构using pii = pair<int, int>;// 小顶堆, 手写堆方法与 prority_queue 相仿，可跳至 第121行 void solve();
namespace heap {pii heap[MAX << 1];  // 堆 (树状数组)
int a2h[MAX << 1];   // 数组索引 -> 堆索引
int h2a[MAX << 1];   // 堆索引 -> 数组索引
int total = 0;       // 总节点 (含已 pop 节点)
int siz = 0;         // 堆大小// C 风格比较函数
bool cmp(pii x, pii y) { return x > y; }// 维护映射的交换
void swap_(int u, int v) {swap(a2h[h2a[u]], a2h[h2a[v]]);swap(h2a[u], a2h[v]);swap(heap[u], heap[v]);if (u == siz) {a2h[h2a[u]] = -1;h2a[u] = -1;}if (v == siz) {a2h[h2a[v]] = -1;h2a[v] = -1;}
}// 向上维护
void up(int node) {while (node and cmp(heap[(node - 1) / 2], heap[node])) {swap_(node, (node - 1) / 2);node = (node - 1) / 2;}
}// 向下维护
void down(int node) {int parent = node;         // 父节点下标int child = 2 * node + 1;  // 子节点下标while (child < siz) {// 判断子节点哪个大, 大的与父节点比较if (child + 1 < siz and cmp(heap[child], heap[child + 1]))child++;if (cmp(heap[parent], heap[child]))  // 判断父节点是否小于子节点{swap_(parent, child);  // 交换父节点和子节点parent = child;        // 子节点下标 赋给 父节点下标}child = child * 2 + 1;  // 换行, 比较下面的父节点和子节点}
}// 线性初始化堆
void build(int n) {total = siz = n;for (int i = 0; i < siz; i++) {a2h[i] = i;h2a[i] = i;}for (int i = siz / 2 - 1; i >= 0; i--)// 必须自下而上down(i);
}// 插入节点
void push(pii x) {heap[siz] = x;a2h[total] = siz;h2a[siz] = total;up(siz);total++;siz++;
}// 返回顶值
pii top() { return heap[0]; }// 删除顶点
pii pop() {siz--;swap_(0, siz);down(0);return heap[siz];
}// 修改第 u 个插入的节点
void modify_by_address(int u, pii x) {int v = a2h[u];heap[v] = x;down(v);up(v);
}// 删除第 u 个插入的节点. 返回: 布尔型: 节点在堆中
void pop_by_address(int u) {int v = a2h[u];siz--;swap_(v, siz);down(v);up(v);
}}  // namespace heapvoid solve() {int n, k;cin >> n >> k;for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++) {if (i > 0)left_[i] = i - 1; // 初始 i 的前驱 i - 1 elseleft_[i] = -1;  // 没有前驱的特殊标记if (i < n - 1)right_[i] = i + 1;  // 初始 i 的后继 i + 1elseright_[i] = -1;heap::push({a[i], i});  // 放入堆中}int cnt = 0;while (cnt < k) {pii p = heap::pop();  // 取出最小的数int idx = p.second, x = p.first;  // idx 为数的索引，x 为这个数if (a[idx] != x) continue;  // 过滤脏数据// 如果有前驱if (left_[idx] >= 0) {a[left_[idx]] += x;  // 贡献给前驱heap::push({a[left_[idx]], left_[idx]});  // 加入修改后数据，原数据变为脏数据，延迟过滤right_[left_[idx]] = right_[idx]; // 更新前驱的后继}// 如果有后继if (right_[idx] >= 0) {a[right_[idx]] += x; // 贡献给后继heap::push({a[right_[idx]], right_[idx]});  // 加入修改后数据，原数据变为脏数据，延迟过滤left_[right_[idx]] = left_[idx]; // 更新后继的前驱}// 标记为无效a[idx] = -1;cnt++;}// 输出for (int i = 0; i < n; i++)if (a[i] >= 0)cout << a[i] << ' ';cout << endl;
}int32_t main() {
#ifdef _DEBUG// freopen("H.in", "r", stdin);// freopen("H.out", "w", stdout);// clock_t st = clock();
#endifcin.tie(0);cout.tie(0);ios::sync_with_stdio(0);solve();#ifdef _DEBUG// cout << "COST: " << clock() - st << endl;
#endifreturn 0;
}

#include <iostream>
#include<cstdio>
using namespace std;
#define MAX 1000000
struct shuzu{long a[MAX] = {0};long len = 0;
}s;
long sort(shuzu &s){long min = s.a[0];long i= 0;long biao = 0;for(i = 1;i<s.len;i++){if(s.a[i]<min){min = s.a[i];biao = i;}}		return biao;
}
void del(shuzu &s,int x){long i;for(i = x;i<s.len;i++){s.a[i] = s.a[i+1];}s.len = s.len - 1;
}
int main(){long n,k;cin >> n >> k;s.len = n;for(int i = 0;i<n;i++){cin >> s.a[i];}for(int i = 0;i < k;i++){long x = sort(s);long shu = s.a[x];if(x == 0){s.a[x+1] += shu;}else if(x == s.len){s.a[x-1] += shu;}else{s.a[x+1] += shu;s.a[x-1] += shu;}del(s,x);	}for(int i = 0;i<s.len;i++){printf("%d ",s.a[i]);}return 0;
}

示例结果也正确。

I: 景区导游

// 景区导游
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5+5;
const int LOG = 20;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;// 建议直接去写板子，别看了int lg2[MAX];
int depth[MAX];
int st[MAX][LOG];
int dis[MAX];
vector<pair<int, int>> edge[MAX];void load_lg2() {lg2[0] = -1;for (int i = 1; i < MAX; i++) {lg2[i] = lg2[i / 2] + 1;}
}void build(int x, int pre, int level) {depth[x] = level;st[x][0] = pre;for (int i = 1; i <= lg2[depth[x]]; i++) {st[x][i] = st[st[x][i-1]][i-1];}for (pair<int, int> p : edge[x]) {int y = p.first, d = p.second;if (y == pre) continue;dis[y] = dis[x] + d;build(y, x, level + 1);}
}int lca(int x, int y) {if (depth[x] > depth[y]) swap(x, y);while (depth[x] < depth[y]) {y = st[y][lg2[depth[y]-depth[x]]];}if (x == y) return x;for (int i = lg2[depth[x]]; i >= 0; i--) {if (st[x][i] != st[y][i]) {x = st[x][i];y = st[y][i];}}return st[x][0];
}int a[MAX];
int rount[MAX];void solve() {int n, k;cin >> n >> k;for (int i = 1; i < n; i++) {int u, v, w;cin >> u >> v >> w;edge[u].push_back({v, w});edge[v].push_back({u, w});}dis[1] = 0;build(1, 1, 0);for (int i = 0; i < k; i++) {cin >> a[i];}int tot = 0;for (int i = 1; i < k; i++) {int f = lca(a[i-1], a[i]);rount[i] = dis[a[i-1]] - dis[f] + dis[a[i]] - dis[f];tot += rount[i];}cout << tot - rount[1] << ' ';  // 第一个for (int i = 1; i < k - 1; i++) {int f = lca(a[i-1], a[i+1]);// 中间置换cout << tot - rount[i] - rount[i+1] + dis[a[i-1]] - dis[f] + dis[a[i+1]] - dis[f] << ' ';}cout << tot - rount[k-1] << endl;  // 最后一个while (true) {int x, y;cin >> x >> y;cout << lca(x, y) << endl;}
}   int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);load_lg2();solve();return 0;
}

J: 砍树

// 砍树
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5+5;
const int LOG = 20;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;// 代码较长，建议从 solve 开始看int lg2[MAX];
int depth[MAX];
int st[MAX][LOG]; // pre[i] 即为 st[i][0]
int weight[MAX];
vector<pair<int, int>> edge[MAX]; // pre : suf, idxvoid load_lg2() {lg2[0] = -1;for (int i = 1; i < MAX; i++) {lg2[i] = lg2[i / 2] + 1;}
}void build(int x, int pre, int level) {depth[x] = level;st[x][0] = pre;for (int i = 1; i <= lg2[depth[x]]; i++) {st[x][i] = st[st[x][i-1]][i-1];}for (pair<int, int> p : edge[x]) {int y = p.first;if (y == pre) continue;build(y, x, level + 1);}
}int lca(int x, int y) {if (depth[x] > depth[y]) swap(x, y);while (depth[x] < depth[y]) {y = st[y][lg2[depth[y]-depth[x]]];}if (x == y) return x;for (int i = lg2[depth[x]]; i >= 0; i--) {if (st[x][i] != st[y][i]) {x = st[x][i];y = st[y][i];}}return st[x][0];
}void dfs(int x, int pre) {for (pair<int, int> p : edge[x]) {int y = p.first;if (y == pre) continue;dfs(y, x);weight[x] += weight[y];}
}void solve() {int n, m;cin >> n >> m;for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;edge[u].push_back({v, i});edge[v].push_back({u, i});}build(1, 0, 0);  // lca 初始化, 不能写 build(1, 1, 0)for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;int f = lca(u, v);// 记录差分weight[u]++;weight[v]++;weight[f]--;weight[st[f][0]]--;}dfs(1, 0);// 输出int res = -1;for (int x = 1; x <= n; x++) {if (weight[x] == m) {for (pair<int, int> p : edge[x]) {int y = p.first, idx = p.second;if (weight[y] == m) {res = max(res, idx);}}}}cout << res << endl;
}int32_t main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);load_lg2();solve();return 0;
}