您现在的位置是：首页 >技术杂谈 >【2023年第十四届蓝桥杯C/C++ B组省赛】个人题解网站首页技术杂谈
【2023年第十四届蓝桥杯C/C++ B组省赛】个人题解
简介【2023年第十四届蓝桥杯C/C++ B组省赛】个人题解
目录
赛后总结
今天出成绩了，大一混了个省一，于是来写题解。
考试的时候挺粗心的，第一题把0月0日给算进去了，比答案大了点，痛失5分；第二题是填空，所以手动二分，貌似对了；第三题题意理解错了，只能过例样；第四题我是贪心做的，不过贪心是错的，没在意数据范围，应该用DFS的，能骗一点分吧；第五题，看出来是DP，但没想出来，测试只能过例样，感觉是全错；第六题，搜索两次即可，但好像没有考虑有斜角的情况，应该能骗大部分；第七题，当时写的纯暴力，后来打算再优化，不过没时间了；第八题，暴力模拟做的，骗分；第九题，完全没想到会考LCA，考前全都去练线段树和最短路了，所以用弗洛伊德写的，骗分；第十题，没想到也是考LCA的，原本想用两个并查集暴力写的，时间不够了，就输出了例样；
一些建议：如果可以用自己的键盘就用自己的，反正我考场的键盘，敲着手痛；规划好时间，我写完第8题的时候大概还有1个小时，全去搞第九题和第十题了，还不如去优化一下前面的代码。
总结：A了一道填空，混省一😋；
测试都是用的民间数据，官方oj上可能只能通过部分测试点。
【2023第十四届蓝桥杯C/C++ B组】赛题
试题 A: 日期统计（235）
解题思路
暴力搜索即可，注意月和日的限制条件以及去重。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int s[N];
int n = 100;
int ans[9];
unordered_map<string, int>mp;
int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void dfs(int pre, int k) {
if (k > 8) {
int x = ans[5] * 10 + ans[6];
if (x < 1 || x > 12) return;
int y = ans[7] * 10 + ans[8];
if (y < 1 || y > mday[x]) return;
string s;
for (int i = 1; i <= 9; i++) s.push_back(ans[i] + '0');
mp[s]++;
return;
}
for (int i = pre + 1; i <= 100; i++) {
if (k == 1 && s[i] == 2) {
ans[k] = s[i];
dfs(i, k + 1);
} else if (k == 2 && s[i] == 0) {
ans[k] = s[i];
dfs(i, k + 1);
} else if (k == 3 && s[i] == 2) {
ans[k] = s[i];
dfs(i, k + 1);
} else if (k == 4 && s[i] == 3) {
ans[k] = s[i];
dfs(i, k + 1);
} else if (k >= 5) {
ans[k] = s[i];
dfs(i, k + 1);
}
}
}
int main() {
for (int i = 1; i <= n; i++) cin >> s[i];
dfs(0, 1);
cout << mp.size();
return 0;
}需手动输入：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
试题 B: 01 串的熵（11027421）
解题思路
自己找规律，发现有单调性，直接二分，注意精确度，可能会有误差，最好验算一下；
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n = 23333333;
double ans = 11625907.5798;
double f(double x) {
double sum = 0;
double a0 = x / n;
double a1 = 1 - a0;
sum += (-a0 * log2(a0)) * x;
sum += (-a1 * log2(a1)) * (n - x);
return sum;
}
int find() {
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (f(mid) > ans) r = mid - 1;
else l = mid + 1;
}
return l;
}
int main() {
cout << find();
return 0;
}
试题 C: 冶炼金属
解题思路
找规律
参考代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a, b;
int mi = -1, ma = 0x3f3f3f3f;
int main() {
cin >> n;
while (n--) {
cin >> a >> b;
ma = min(ma, a / b);
mi = max(mi, a / (b + 1) + 1);
}
cout << mi << " " << ma << endl;
return 0;
}试题 D: 飞机降落
解题思路
数据范围较小，直接全排列把每一种情况都check一遍
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e1 + 5;
struct node {
int t, d, l;
} s[N];
int a[N];
int T, n;
void slove() {
do {
int now = 0;
int flag = 1;
for (int i = 1; i <= n; i++) {
int t = s[a[i]].t, d = s[a[i]].d, l = s[a[i]].l;
if (now > t + d) {
flag = 0;
break;
} else {
if (t > now) now = t + l;
else now = now + l;
}
}
if (flag) {
cout << "YES" << endl;
return;
}
} while (next_permutation(a + 1, a + n + 1));
cout << "NO" << endl;
}
int main() {
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i].t >> s[i].d >> s[i].l;
a[i] = i;
}
slove();
}
return 0;
}
试题 E: 接龙数列
解题思路
定义：表示前i个数以j结尾的最长接龙数列的长度
状态转移方程：
(a表示第i个数的首位，b表示第i个数的末位)
Base：每次转移前，得更新,更新方程
答案：(最少的删除次数即为原数列长度减去最长的接龙数列长度)
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n;
struct node {
int a, b;
} s[N];
int ans;
int f[N][10];
int main() {
cin >> n;
string ss;
for (int i = 1; i <= n; i++) {
cin >> ss;
s[i].a = ss[0] - '0';
s[i].b = ss.back() - '0';
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
f[i][j] = f[i - 1][j];
}
f[i][s[i].b] = max(f[i][s[i].b], f[i - 1][s[i].a] + 1);
}
for (int i = 0; i <= 9; i++) {
ans = max(ans, f[n][i]);
}
cout << n - ans;
return 0;
}试题 F: 岛屿个数
解题思路
从开始染色，把遇到的0全部染成2，这样没染色的部分，一定为环，接着再搜索环的个数即可。
注意：开始染色的时候，可能有斜角，得使用八向搜索；搜索环的时候则用四向搜索。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e1 + 5;
int T, m, n;
char g[N][N];
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};
int ans;
struct point {
int x, y;
};
void bfs1() {
queue<point>q;
g[0][0] = '2';
q.push({0, 0});
while (!q.empty()) {
point now = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
int tx = now.x + dx[i];
int ty = now.y + dy[i];
if (tx >= 0 && ty >= 0 && tx <= m + 1 && ty <= n + 1) {
if (g[tx][ty] == '0') {
g[tx][ty] = '2';
q.push({tx, ty});
}
}
}
}
}
void bfs2(int x, int y) {
queue<point>q;
g[x][y] = '2';
q.push({x, y});
while (!q.empty()) {
point now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int tx = now.x + dx[i];
int ty = now.y + dy[i];
if (tx >= 1 && ty >= 1 && tx <= m && ty <= n) {
if (g[tx][ty] == '0' || g[tx][ty] == '1') {
g[tx][ty] = '2';
q.push({tx, ty});
}
}
}
}
}
int main() {
cin >> T;
while (T--) {
cin >> m >> n;
memset(g, '0', sizeof(g));
ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> g[i][j];
}
}
bfs1();
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] == '1') {
ans++;
bfs2(i, j);
}
}
}
cout << ans << endl;
}
return 0;
}试题 G: 子串简写
解题思路
发现对于每一个，都只跟它后面
的个数有关，可以先求
的后缀和，再进行操作。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
int k;
string s;
char c1, c2;
int f[N];
ll ans;
int main() {
cin >> k >> s >> c1 >> c2;
int len = s.size();
s = " " + s;
for (int i = len; i >= 1; i--) {
f[i] = f[i + 1];
if (s[i] == c2) f[i] = f[i + 1] + 1;
}
for (int i = 1; i + k - 1 <= len; i++) {
if (s[i] == c1) ans += f[i + k - 1];
}
cout << ans;
return 0;
}试题 H: 整数删除
解题思路
可以用优先队列维护节点最值，再用静态链表维护两端的下标
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 5;
ll n, k, v;
struct node {
ll from, next;
ll val, id;
friend bool operator < (node x, node y) {
if (x.val == y.val) return x.id > y.id;
return x.val > y.val;
}
} s[N];
priority_queue<node>q;
void add(ll x) {
cin >> v;
s[x].from = x - 1;
s[x].next = x + 1;
s[x].val = v;
s[x].id = x;
q.push(s[x]);
}
void erase(ll x) {
s[s[x].from].next = s[x].next;
s[s[x].next].val += s[x].val;
s[s[x].next].from = s[x].from;
s[s[x].from].val += s[x].val;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) add(i);
s[0].next = 1;
while (k--) {
node now = q.top();
q.pop();
while (now.val != s[now.id].val) {
now.val = s[now.id].val;
q.push(now);
now = q.top();
q.pop();
}
erase(now.id);
}
for (int i = s[0].next; i != n + 1; i = s[i].next) cout << s[i].val << ' ';
return 0;
}
试题 I: 景区导游
解题思路
定义为根节点到编号为
节点的距离，那么
两点的最短距离为
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n, k;
int a[N];
struct edge {
ll ti, next;
};
ll dis[N], deep[N], f[N][25];
ll ans, sum;
vector<edge>g[N];
void dfs(int u, int fa, ll dist) {
deep[u] = deep[fa] + 1;
dis[u] = dist;
f[u][0] = fa;
for (int i = 1; (1 << i) <= deep[u]; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int i = 0; i < g[u].size(); i++) {
if (g[u][i].next == fa) continue;
else dfs(g[u][i].next, u, dist + g[u][i].ti);
}
}
int lca(int x, int y) {
if (deep[x] < deep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) {
if (deep[f[x][i]] >= deep[y]) x = f[x][i];
if (x == y) return x;
}
for (int i = 20; i >= 0; i--) {
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
inline ll get(int x, int y) {
return dis[x] + dis[y] - dis[lca(x, y)] * 2;
}
int main() {
cin >> n >> k;
int u, v, t;
for (int i = 1; i < n; i++) {
cin >> u >> v >> t;
g[u].push_back({t, v});
g[v].push_back({t, u});
}
dfs(1, 0, 0);
for (int i = 1; i <= k; i++) cin >> a[i];
for (int i = 1; i < k; i++) sum += get(a[i], a[i + 1]);
for (int i = 1; i <= k; i++) {
ans = sum;
if (i != 1) ans -= get(a[i], a[i - 1]);
if (i != k) ans -= get(a[i], a[i + 1]);
if (i != 1 && i != k) ans += get(a[i - 1], a[i + 1]);
cout << ans << ' ';
}
return 0;
}
试题 J: 砍树
解题思路
树上差分，套LCA模板
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n, m;
int s[N], id[N];
ll deep[N], f[N][25];
ll ans = -1;
struct edge {
ll id, next;
};
vector<edge>g[N];
void dfs(int u, int fa) {
deep[u] = deep[fa] + 1;
f[u][0] = fa;
for (int i = 1; (1 << i) <= deep[u]; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int i = 0; i < g[u].size(); i++) {
if (g[u][i].next != fa) {
dfs(g[u][i].next, u);
id[g[u][i].next] = g[u][i].id;
}
}
}
int lca(int x, int y) {
if (deep[x] < deep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) {
if (deep[f[x][i]] >= deep[y]) x = f[x][i];
if (x == y) return x;
}
for (int i = 20; i >= 0; i--) {
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
void add(int x, int y) {
s[x]++;
s[y]++;
s[lca(x, y)] -= 2;
}
void sum(int u, int fa) {
for (int i = 0; i < g[u].size(); i++) {
if (g[u][i].next != fa) {
sum(g[u][i].next, u);
s[u] += s[g[u][i].next];
}
}
}
int main() {
cin >> n >> m;
int u, v;
for (int i = 1; i < n; i++) {
cin >> u >> v;
g[u].push_back({i, v});
g[v].push_back({i, u});
}
dfs(1, 0);
for (int i = 1; i <= m; i++) {
cin >> u >> v;
add(u, v);
}
sum(1, 0);
for (int i = 1; i <= n; i++) {
if (s[i] == m && id[i] > ans) ans = id[i];
}
cout << ans;
return 0;
}
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效) - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》