2023年第十四届蓝桥杯C++B组复盘_2023蓝桥杯c++b组

link管理

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

A: 日期统计（5分）

小蓝现在有一个长度为 $的范围之内。数组中的元素从左至右如下所示：$

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

现在他想要从这个数组中寻找一些满足以下条件的子序列：

子序列的长度为8；
这个子序列可以按照下标顺序组成一个yyyymmdd 格式的日期，并且要求这个日期是2023 年中的某一天的日期，例如20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的2023 年的日期。
对于相同的日期你只需要统计一次即可。

纯暴力的话就dfs，或者用8重循环。不妨再考虑下题目，由于对于相同的日期只需统计一次，因此可以查询每个2023年的日期能否由上面给的数字拼出来。这样既能有很好的效率，又能省去去重的过程。最终结果是 235 。
具体代码如下

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int numbers[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};
const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
    int ans = 0;
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= days[i]; j++) {
            string str = "2023";
            if (i < 10)str += "0";
            str += to_string(i);
            if (j < 10)str += "0";
            str += to_string(j);
            int k = 0;
            for (int l = 0; l < 100 && k < 8; l++) {
                if (numbers[l] == str[k] - '0') k++;
            if (k >= 8) ans++;
    cout << ans << endl;
    return 0;
B: 01 串的熵（5分）
 
对于一个长度为 $H(S)=-\frac{1}{3}\log_2(\frac{1}{3})-\frac{2}{3}\log_2(\frac{2}{3})-\frac{2}{3}\log_2(\frac{2}{3})=1.3083$ 
枚举一下0的个数，计算的时候要开double保证精度。结果是11027421（因为本题数据并不是很大，直接暴力枚举也可以，并不一定需要使用二分） 
暴力枚举： 
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int total = 23333333;
const double H = 11625907.5798;
int main() {
    for (int i = 0; i < total / 2; i++) {
        double ans = 0;
        ans -= 1.0 * i * i / total * log2(1.0 * i / total);
        ans -= 1.0 * (total - i) * (total - i) / total * log2(1.0 * (total - i) / total);
        if (abs(ans - H) < 1e-4) {
            cout << i << endl;
            return 0;
    return 0;
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int total = 23333333;
const double H = 11625907.5798;
int main() {
    int l = 0, r = total / 2;
    while (l < r) {
        int mid = (l + r) >> 1;
        double ans = 0;
        ans -= 1.0 * mid * mid / total * log2(1.0 * mid / total);
        ans -= 1.0 * (total - mid) * (total - mid) / total * log2(1.0 * (total - mid) / total);
        if (abs(ans - H) < 1e-4) {
            cout << mid << endl;
            return 0;
        if (ans > H) {
            r = mid;
        } else {
            l = mid + 1;
    return 0;
C: 冶炼金属（10分）
 
小蓝有一个神奇的炉子用于将普通金属




    
D: 飞机降落（10分）
 
    for (int i = 0; i < n; i++) {
        if (!st[i]) {
            if (t[i] + d[i] >= last) {
                st[i] = true;
                if (t[i] > last) dfs(u + 1, t[i] + l[i]);
                else dfs(u + 1, last + l[i]);
                st[i] = false;
            } else return;
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> t[i] >> d[i] >> l[i];
        for (int i = 0; i < N; i++) st[i] = false;
        flag = false;
        dfs(0, 0);
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    return 0;
E: 接龙数列（15分）
 
对于一个长度为




    
F: 岛屿个数（15分）
 
小蓝得到了一副大小为 
这个题蛮有意思的，如果不考虑子岛屿的话，基本上是白送分题hhh。如果考虑子岛屿就需要判断是不是成环，以及另一个岛屿是不是在这个成环的岛屿中。不妨换个思路看，如果一个岛屿不在另一个岛屿中，则这个岛屿在有水的地方（为’0’的地方）一定是跟外界连通的（注意此处的连通包括对角线这种连通）。可以用这个思路去写代码会更简单一些。 
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int dx[8] = {1, -1, 0, 0, -1, -1, 1, 1};
const int dy[8] = {0, 0, 1, -1, -1, 1, -1, 1};
int n, m;
char graph[60][60];
bool vis[60][60];
bool fill(int A, int B) {
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            vis[i][j] = false;
    queue<pair<int, int> > q;
    q.emplace(A, B);
    vis[A][B] = true;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) return true;
            if (graph[nx][ny] == '0' && !vis[nx][ny]) {
                vis[nx][ny] = true;
                q.emplace(nx, ny);
    return false;
void bfs(int A, int B) {
    queue<pair<int, int> > q;
    q.emplace(A, B);
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && graph[nx][ny] == '1') {
                graph[nx][ny] = '0';
                q.emplace(nx, ny);
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> graph[i][j];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (graph[i][j] == '1') {
                    if (!fill(i, j))
                        graph[i][j] = '0';
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (graph[i][j] == '1') {
                    ans++;
                    bfs(i, j);
        cout << ans << endl;
    return 0;
G: 子串简写（20分）
 
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如internationalization简写成i18n，Kubernetes 简写成K8s, Lanqiao 简写成L5o 等。




    
 
在本题中，我们规定长度大于等于H: 整数删除（20分）
 
给定一个长度为 
堆+链表。因为需要频繁删除元素，故考虑使用链表，又因为需要找最小，因此可以使用堆解决。这题最大会爆int，因此必须开long long。 
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
ll v[maxn], l[maxn], r[maxn];
void del(ll x) {
    r[l[x]] = r[x], l[r[x]] = l[x];
    v[l[x]] += v[x], v[r[x]] += v[x];
int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    r[0] = 1, l[n + 1] = n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        l[i] = i - 1;
        r[i] = i + 1;
        pq.emplace(v[i], i);
    while (k--) {
        auto p = pq.top();
        pq.pop();
        if (p.first != v[p.second]) {
            pq.emplace(v[p.second], p.second);
            k++;
        } else del(p.second);
    ll head = r[0];
    while (head != n + 1) {
        cout << v[head] << " ";
        head = r[head];
    return 0;
I: 景区导游（25分）
 
某景区一共有 $ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, k; cin >> n >> k; for (int i = 1; i < n; i++) { int u, v, z; cin >> u >> v >> z; e[u].emplace_back(v, z); e[v].emplace_back(u, z); dfs1(1, 1, 0); dfs2(1, 1); for (int i = 1; i <= k; i++) cin >> c[i]; for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] + get(c[i], c[i + 1]); ll pre = 0; for (int i = 1; i <= k; i++) { cout << pre + get(c[i - 1], c[i + 1]) + suf[i + 1] << " "; pre += get(c[i - 1], c[i]); return 0;$ 




    
J: 砍树（25分）
 
给定一棵由 $ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; e[u].emplace_back(v); e[v].emplace_back(u); dfs1(1, 1); dfs2(1, 1); for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; diff[u]++, diff[v]++, diff[lca(u, v)] -= 2; dfs(1, 0); ll ans = -1; for (int i = 0; i <= n; i++) if (diff[i] >= m) ans = i - 1; cout << ans << endl; return 0; 第15届蓝桥杯省赛已于2024年8月24日正式落下帷幕，比赛仍然采取线上形式。本次省赛初级组和中级组分开考试，上午是初级组，下午是中级组。这是Scratch初级组真题，试题包括两种题型，分别是选择题和编程创作题，其中选择题5道，都是和Scratch编程知识相关的题目，编程部分也是5道题，分别是猪八戒落地、游乐场、画西瓜、找不同和消除数字球。 这个炉子有一个称作转换率的属性V，V 是一个正整数，这意味着消耗V 个普通金属O 恰好可以冶炼出一个特殊金属X，当普通金属O 的数目不足V 时，无法继续冶炼。所以在地图周围一圈， 我们增加一圈0作为外海， dfs遍历外海每一个方格， 若与外海方格相邻的岛屿未被遍历过，那么这就是一个新的岛屿， 再用一个dfs去遍历这个岛。地图外的方格我们全部视为海， 与地图外的海连通的海都视为外海， 可以发现， 接触到了外海的岛屿， 就一定不是其它岛屿的子岛。对于每一条记录， 都可以求出转换率V的一个取值范围。 参加了两届蓝桥杯以及做过了往年的真题我的直观感受是蓝桥杯不再那么“暴力”了，而是逐渐趋向DP和搜素图论方面了。下面是第十四届蓝桥杯省赛C/C++ B组真题及题解，希望对阅读的你有所帮助。 先用边缘的海水进行bfs求出"真的海水"，然后再对所有岛屿进行BFS,此时BFS的时候非真的海水可以直接识别为陆地然后入队。每次用第i个数组开头的字母对应的数组更新f[i]，然后再用f[i]反过来更新bac即可。因此我们可以开一个数组f[i]表示前i个数字，以第i个结尾的最大接龙子序列。删最少数使得他是接龙序列，即求原序列的最大接龙子序列，然后用n减去。然后枚举开头的位置，二分出结尾在另一个数组的合法位置，直接累加答案。因此直接二分即可，顺便输出一下结果对应的函数值。set维护每个位置的值和要删的最小值。 思路：一开始我想错了，把子岛也求了。第一遍把岛屿外面的0全改成2（8方搜索），然后把里面的0改成1，第二for循环搜索遍历岛屿（四方搜索），看看有几个。假设一下，岛屿外是海，岛屿内是河。图中是有两个岛的，图1的3点是海，2点也是，2点8方可以搜到3，他们也算是联通的；思路：找到所有头l和尾r出现的位置，然后存起来。利用r[j] >= l[i] + k - 1这一关系,找出每一个头的总数，加和即可。思路：这题我写了几个数，发现就是取一堆数据的最小值的最大值，和最大值的最小值（人话：公共部分）。 第一次打蓝桥，寄了，300元买了两个脆脆鲨和一瓶水哈哈可以在下面民间网站提交测试教训 :（1）直接输出骗样例的别忘了先把题目的输入写上（2）读清楚题目要求 (3)一定要return 0;啊啊啊啊（4）devc++的输入窗口可以从属性哪里改成可复制(傻傻的自己敲案例)(5)把思路想好了再动手，(别白白浪费时间)$