2023第十四届蓝桥杯国赛 C/C++ 大学 B 组 (赛后记录)-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023第十四届蓝桥杯国赛 C/C++ 大学 B 组 (赛后记录)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

$2023 第十四届蓝桥杯国赛 C / C + + 大学 B 组$

点我查看题目PDF

前言

由于是学校期末复习周, 很多算法没有复习, 结果考了一堆板题 (悲

赛后代码记录

A题子 2023

直接跑暴力就行, 应该没啥问题

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define de(a) cout << #a << " = " << a << "\n";
#define int long long
using namespace std;

string s;
int res;
char op[] = {'2', '0', '2', '3'};

void dfs(int u, int cnt) {
    if (cnt == 4) {
        res++;
        return;
    }
    if (u >= sz(s)) return;

    if (s[u] == op[cnt]) dfs(u + 1, cnt + 1);
    dfs(u + 1, cnt);
}

string get(string s) {
    string res;
    for (auto &c: s) {
        if (c == '2' || c == '0' || c == '3')
            res += c;
    }
    return res;
}

void solve() {
    for (int i = 1; i <= 2023; i++) s += get(to_string(i));
    dfs(0, 0);
    de(res);
}


signed main() {
    IOS;

    int T = 1;
    // cin >> T; cin.get();

    while (T --) solve();

    return 0;
}

答案

res = 5484660609

B题双子数

筛一下可以作为 p 和 q 的素数, 然后暴力枚举判断就行, 实测跑的很快

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define de(a) cout << #a << " = " << a << "\n";
// #define int long long
#define int __int128
using namespace std;

constexpr int N = 1e7 + 10;
int primes[N];
int cnt;
bool vis[N];

void get_p(int n = sqrt(23333333333333) + 10) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) primes[cnt++] = i;
        for (int j = 0; i * primes[j] <= n; j++) {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void solve() {
    get_p();
    int res = 0;
    for (int i = 0; i < cnt; i++)
        for (int j = i + 1; j < cnt; j++) {
            int num = primes[i] * primes[i] * primes[j] * primes[j];
            if (num < 2333) continue;
            if (num > 23333333333333) break;
            res++;
        }
    cout << (long long)res;
}


signed main() {
    IOS;

    int T = 1;
    // cin >> T; cin.get();

    while (T --) solve();

    return 0;
}

错误答案

res = 947303

update
感谢群友让我知道我得分-5, 这里计算中long long爆掉了, 需要 __int128
正确答案

res = 947293

C题班级活动

more 表示所有id中人数多于两个的人数去掉匹配的 2 位剩下的总人数，one 表示只有一个的人数，如果 more 大于等于 one 输出 more，否则输出 more + （one-more）/ 2

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define de(a) cout << #a << " = " << a << "\n";
#define int long long
using namespace std;
int n;

void solve() {
    map<int, int> cnt;
    cin >> n;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        cnt[x]++;
    }

    int one = 0, more = 0;
    for (auto [x, c]: cnt) {
        if (c == 1) one++;
        else if (c > 2) more += c - 2;
    }

    if (more >= one) cout << more;
    else cout << more + (one - more) / 2;
}


signed main() {
    IOS;

    int T = 1;
    // cin >> T; cin.get();

    while (T --) solve();

    return 0;
}

D题合并数列

一眼双指针, 模拟一下过程就行了

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define de(a) cout << #a << " = " << a << "\n";
#define int long long
using namespace std;

constexpr int N = 1e7 + 10;
int n, m;
int a[N];
int b[N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i]; 
    for (int i = 1; i <= m; i++) cin >> b[i];

    int res = 0;
    int suma = 0, sumb = 0;
    int i = 1, j = 1;
    while (i <= n + 1 && j <= m + 1) {
        if (suma == sumb) suma += a[i++], sumb += b[j++];
        else if (suma < sumb) res++, suma += a[i++];
        else res++, sumb += b[j++];
    }

    cout << res;
}


signed main() {
    IOS;

    int T = 1;
    // cin >> T; cin.get();

    while (T --) solve();

    return 0;
}

E题数三角

是个原… (我没做过悲
附上原题连接
赛时直接 $O(n^3)$ 枚举了 (暴力
正解思路就是枚举所有顶点和该顶点能到的点的边长, 相同的顶点和边长可以组成等腰三角形, 但这样会出现三点共线的情况, 再把这一部分给减去就行

贴上正解代码 (感觉很对, 牛客的数据是过了

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define de(a) cout << #a << " = " << a << "\n";
#define all(a) a.begin(), a.end()
#define int long long
#define PII pair<int, int>
using namespace std;

int n, m, k;

void solve() {
    cin >> n;
    
    set<PII> vis;
    
    vector<PII> point(n);
    for (auto &p: point) {
        auto &[x, y] = p;
        cin >> x >> y;
        vis.insert(p);
    }

    auto get_dis = [] (PII &a, PII &b) {
        auto &[x1, y1] = a;
        auto &[x2, y2] = b;
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    };

    vector<PII> edge;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (i == j) continue;

            int eg = get_dis(point[i], point[j]);
            edge.emplace_back(i, eg);
        }

    auto check = [&] (int x, int y) {
        return vis.count((PII){x, y});
    };

    // 三点共线数 cnt
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            auto &[x1, y1] = point[i];
            auto &[x2, y2] = point[j];
            int dx = x1 + x2, dy = y1 + y2;
            if (dx % 2 || dy % 2) continue;
            cnt += check(dx / 2,  dy / 2);
        }

    sort(all(edge));
    edge.emplace_back(-1, -1);  // 用来计算最后一个点的情况

    auto calc = [] (int &x) {
        return x >= 2? (x * (x - 1) / 2) : 0;
    };

    int las_point = -1, las_dis = -1;
    int c = 0;

    int ans = 0;  // 不考虑三点共线的情况的所有 共起点, 等边长 的三角形
    for (auto &[po, dis]: edge) {
        if (po == las_point && dis == las_dis) {
            c++;
        } else {
            ans += calc(c);
            c = 1, las_point = po, las_dis = dis;
        }
    }

    cout << ans - cnt;  // 把 所有情况 - 三点共线的情况 = 答案
}


signed main() {
    IOS;

    int T = 1;
    // cin >> T; cin.get();

    while (T --) solve();

    return 0;
}

F题删边问题

没复习缩点, 暴力都很难写, 直接输出 -1 了, 哭死, 等复习板子之后再补, 感觉缩点之后很容易求, 板题 + 1

G题 AB 路线

很明显的分层图, 但由于没有复习算法, 压根没想起来有分层图这个玩意, 赛时骗的分, 赛后很快就写出了, 再次悲伤, 代码很板, 板题 + 1

思考 (直接 bfs 是否满足最短路呢)

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define de(a) cout << #a << " = " << a << "\n";
#define int long long
using namespace std;

constexpr int N = 1000 + 10;
int n, m, k;
char g[N][N];
int dist[N][N][11];  // 把所有的情况记录下来
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int bfs(int sx, int sy) {
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy][1] = 0;
    
    queue<tuple<int, int, int>> q;  // x y 以及到达该点的 c
    q.emplace(sx, sy, 1);
    while (q.size()) {
        auto [x, y, c] = q.front();
        q.pop();
        if (x == n && y == m) return dist[n][m][c];

        bool turn = false;  // 是否应该换字母走
        if (c == k) turn = true;
        
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;

            if (!turn && g[x][y] == g[a][b]) {
                if (dist[a][b][c + 1] > dist[x][y][c] + 1) {
                    dist[a][b][c + 1] = dist[x][y][c] + 1;
                    q.emplace(a, b, c + 1);
                }
            }

            if (turn && g[x][y] != g[a][b]) {
                if (dist[a][b][1] > dist[x][y][c] + 1) {
                    dist[a][b][1] = dist[x][y][c] + 1;
                    q.emplace(a, b, 1);
                }
            }
        }
    }

    return -1;  // 没到达返回 -1
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> g[i] + 1;
    cout << bfs(1, 1);    
}


signed main() {
    IOS;

    int T = 1;
    // cin >> T; cin.get();

    while (T --) solve();

    return 0;
}

H题抓娃娃

狠狠的吐槽题面, 那么重要的条件为什么不直接在题面中提出来, 而是隐藏在下一页的数据范围里, 本来想过这个做法, 但被自己推翻了, 结果数据中不存在能推翻这个做法的情况…赛时无奈写的暴力, 狠狠的悲伤
思路: 由于数据范围中给了一个很重要的条件, 就是查询的区长度间一定大于所有的线段, 也就是说, 只要线段的中点落在查询的区间, 那么他一定是被包含的, 由于计算中点需要除法, 容易出精度问题, 我们把所有的坐标映射成原来的两倍, 那么中点一定也是整数坐标了, 然后跑个前缀和即可

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define de(a) cout << #a << " = " << a << "\n";
#define int long long
using namespace std;

constexpr int N = 1e6 + 10;
int n, m;
int s[N * 2];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
        s[l + r]++;  // 中点坐标其实是 (l + r) / 2, 但映射成了 l + r
    }
    
    for (int i = 1; i < 2 * N; i++) s[i] += s[i - 1];

    while (m--) {
        int L, R; cin >> L >> R;
        cout << s[2 * R] - s[2 * L - 1] << "\n"; // 差分
    }
}


signed main() {
    IOS;

    int T = 1;
    // cin >> T; cin.get();

    while (T --) solve();

    return 0;
}

I题拼数字

不会, 特判了几个暴力跑出来的数据, 其他的都输出的 -1

等待大神题解

J题逃跑

看见有概率果断没写, 输出样例了文章来源地址https://www.toymoban.com/news/detail-489972.html

总结

有原题很离谱, 板题也好多, 评价是不如省赛
发挥不太好, 希望有奖 (求求

到了这里，关于2023第十四届蓝桥杯国赛 C/C++ 大学 B 组 (赛后记录)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

2023第十四届蓝桥杯国赛 C/C++ 大学 B 组 (赛后记录)

前言

赛后代码记录

A题子 2023

B题双子数

C题班级活动

D题合并数列

E题数三角

F题删边问题

G题 AB 路线

H题抓娃娃

I题拼数字

J题逃跑

总结

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

2023第十四届蓝桥杯国赛 C/C++ 大学 B 组 (赛后记录)

前言

赛后代码记录

A题 子 2023

B题 双子数

C题 班级活动

D题 合并数列

E题 数三角

F题 删边问题

G题 AB 路线

H题 抓娃娃

I题 拼数字

J题 逃跑

总结

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

A题子 2023

B题双子数

C题班级活动

D题合并数列

E题数三角

F题删边问题

H题抓娃娃

I题拼数字

J题逃跑