$$2023第十四屆藍(lán)橋杯國賽C/C++大學(xué)B組$$

• 點(diǎn)我查看題目PDF

前言

由于是學(xué)校期末復(fù)習(xí)周, 很多算法沒有復(fù)習(xí), 結(jié)果考了一堆板題 (悲

賽后代碼記錄

A題 子 2023

直接跑暴力就行, 應(yīng)該沒啥問題

#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題 雙子數(shù)

篩一下可以作為 p 和 q 的素?cái)?shù), 然后暴力枚舉判斷就行, 實(shí)測跑的很快

#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;
}

• 錯(cuò)誤答案

res = 947303

• update
  感謝群友讓我知道我得分-5, 這里計(jì)算中long long爆掉了, 需要 __int128
• 正確答案

res = 947293

C題 班級活動(dòng)

more 表示所有id中人數(shù)多于兩個(gè)的人數(shù)去掉匹配的 2 位剩下的總?cè)藬?shù)，one 表示只有一個(gè)的人數(shù)，如果 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題 合并數(shù)列

一眼雙指針, 模擬一下過程就行了

#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題 數(shù)三角

是個(gè)原… (我沒做過 悲
附上原題連接
賽時(shí)直接 $O(n^3)$枚舉了 (暴力
正解思路就是枚舉所有頂點(diǎn)和該頂點(diǎn)能到的點(diǎn)的邊長, 相同的頂點(diǎn)和邊長可以組成等腰三角形, 但這樣會(huì)出現(xiàn)三點(diǎn)共線的情況, 再把這一部分給減去就行

• 貼上正解代碼 (感覺很對, 牛客的數(shù)據(jù)是過了

#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});
    };

    // 三點(diǎn)共線數(shù) 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);  // 用來計(jì)算最后一個(gè)點(diǎn)的情況

    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;  // 不考慮三點(diǎn)共線的情況的所有 共起點(diǎn), 等邊長 的三角形
    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;  // 把 所有情況 - 三點(diǎn)共線的情況 = 答案
}


signed main() {
    IOS;

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

    while (T --) solve();

    return 0;
}

F題 刪邊問題

沒復(fù)習(xí)縮點(diǎn), 暴力都很難寫, 直接輸出 -1 了, 哭死, 等復(fù)習(xí)板子之后再補(bǔ), 感覺縮點(diǎn)之后很容易求, 板題 + 1

G題 AB 路線

很明顯的分層圖, 但由于沒有復(fù)習(xí)算法, 壓根沒想起來有分層圖這個(gè)玩意, 賽時(shí)騙的分, 賽后很快就寫出了, 再次悲傷, 代碼很板, 板題 + 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 以及到達(dá)該點(diǎn)的 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;  // 是否應(yīng)該換字母走
        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;  // 沒到達(dá)返回 -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題 抓娃娃

狠狠的吐槽題面, 那么重要的條件為什么不直接在題面中提出來, 而是隱藏在下一頁的數(shù)據(jù)范圍里, 本來想過這個(gè)做法, 但被自己推翻了, 結(jié)果數(shù)據(jù)中不存在能推翻這個(gè)做法的情況…賽時(shí)無奈寫的暴力, 狠狠的悲傷
思路: 由于數(shù)據(jù)范圍中給了一個(gè)很重要的條件, 就是查詢的區(qū)長度間一定大于所有的線段, 也就是說, 只要線段的中點(diǎn)落在查詢的區(qū)間, 那么他一定是被包含的, 由于計(jì)算中點(diǎn)需要除法, 容易出精度問題, 我們把所有的坐標(biāo)映射成原來的兩倍, 那么中點(diǎn)一定也是整數(shù)坐標(biāo)了, 然后跑個(gè)前綴和即可

#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]++;  // 中點(diǎn)坐標(biāo)其實(shí)是 (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題 拼數(shù)字

不會(huì), 特判了幾個(gè)暴力跑出來的數(shù)據(jù), 其他的都輸出的 -1

• 等待大神題解

J題 逃跑

看見有概率果斷沒寫, 輸出樣例了文章來源地址http://www.zghlxwxcb.cn/news/detail-489972.html

總結(jié)

• 有原題很離譜, 板題也好多, 評價(jià)是不如省賽
• 發(fā)揮不太好, 希望有獎(jiǎng) (求求

到了這里，關(guān)于2023第十四屆藍(lán)橋杯國賽 C/C++ 大學(xué) B 組 (賽后記錄)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！