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 ) O(n^3) O(n3)枚举了 (暴力
正解思路就是枚举所有顶点和该顶点能到的点的边长, 相同的顶点和边长可以组成等腰三角形, 但这样会出现三点共线的情况, 再把这一部分给减去就行

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

#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题 逃跑

看见有概率果断没写, 输出样例了

总结

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