第十二届蓝桥杯C++ B组代码

题目见这

试题A 空间

#include <iostream>

using namespace std;

int main() {
    printf("%d", 256 * 1024 * 1024 / 4);
    return 0;
}

试题B 卡片

#include <iostream>

using namespace std;

int cnt[10];

bool check(int x)
{
    while(x){
        int t = x % 10;
        cnt[t] --;
        if(cnt[t] < 0) return false;
        x /= 10;
    }
    return true;
}

int main()
{
    for(int i = 0;i <= 9;i ++) cnt[i] = 2021;

    int j = 1;
    while(1){
        if(check(j)) j ++ ;
        else break;
    }
    cout << j - 1 << endl; // 这里要 -1

    return 0;
}

试题C 直线

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 250000;
int cnt;

struct Segment {
    double k;
    double b;

    bool operator<(const Segment &other) const {
        if (k != other.k) return k < other.k;
        return b < other.b;
    }
} seg[N];

int main() {
    for (int x1 = 0; x1 < 20; x1++)
        for (int y1 = 0; y1 < 21; y1++)
            for (int x2 = 0; x2 < 20; x2++)
                for (int y2 = 0; y2 < 21; y2++)
                    if (x1 != x2) {
                        double k = (double) (y1 - y2) / (x1 - x2);
                        double b = y1 - k * x1;
                        seg[cnt++] = {k, b};
                    }

    sort(seg, seg + cnt);
    int res = 0;
    for (int i = 1; i < cnt; i++) {
        if (fabs(seg[i].k - seg[i - 1].k) > 1e-8 || fabs(seg[i].b - seg[i - 1].b) > 1e-8) res++;
    }
    printf("%d\n", res + 21);
    return 0;
}

试题D 货物摆放

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 100010;
int cnt;
LL ap[N];

int main() {
    LL n = 2021041820210418;

    for (LL i = 1; i * i <= n; i++)
        if (n % i == 0) {
            ap[cnt++] = i;
            if (n / i != i) ap[cnt++] = n / i;
        }

    int res = 0;
    for (int i = 0; i < cnt; i++)
        for (int j = 0; j < cnt; j++) 
            for (int k = 0; k < cnt; k++) {
                LL x = ap[i], y = ap[j], z = ap[k];
                if (x * y * z == n)
                    res++;
            }

    printf("%d\n", res);

    return 0;
}

试题E 路径

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2300, M = N * 50;
int h[N], ne[M], e[M], w[M], idx;
int dist[N];
bool st[N];
int q[N];
int n = 2021;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void add(int a, int b, int d) {
    e[idx] = b;
    w[idx] = d;
    ne[idx] = h[a];
    h[a] = idx++;
}

int spfa() {
    int hh = 0, tt = -1;
    q[++tt] = 1;
    dist[1] = 0;
    st[1] = true;
    while (hh <= tt) {
        int t = q[hh++];
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    st[j] = true;
                    q[++tt] = j;
                }
            }
        }
    }
    return dist[n];
}

int main() {
    memset(dist, 0x3f, sizeof dist);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= 2020; i++)
        for (int j = max(1, i - 21); j <= min(n, i + 21); j++) {
            int d = gcd(i, j);
            add(i, j, i / d * j);
        }
    printf("%d\n", spfa());

    return 0;
}

试题F 时间显示

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
LL n;

int main() {
    scanf("%lld", &n);
    n /= 1000;
    int h = n / 3600 % 24;
    int m = n % 3600 / 60;
    int s = n % 3600 % 60;
    printf("%.2d:%.2d:%.2d", h, m, s);

    return 0;
}

试题G 砝码沉重

#include <iostream>

using namespace std;

const int N = 110, M = 200010;
int a[N];
int n, m;
bool f[N][M];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        m += a[i];
    }

    f[0][0] = true;
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j <= m; j++) 
            f[i][j] = f[i - 1][j] || f[i - 1][j + a[i]] || f[i - 1][abs(j - a[i])];


    int res = 0;
    for (int i = 1; i <= m; i++)
        if (f[n][i]) res ++;
    printf("%d\n", res);

    return 0;
}

试题H 杨辉三角

#include <iostream>

using namespace std;

typedef long long LL;
int n;

LL c(int a, int b) {
    LL res = 1;
    for (int i = a, j = 1; j <= b; i--, j++) {
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
}

bool check(int k) {
    LL l = k * 2;
    LL r = max((LL) n, l);
    while (l < r) {
        LL mid = l + r >> 1;
        if (n <= c(mid, k)) r = mid;
        else l = mid + 1;
    }
    if (c(l, k) == n) {
        LL res = l * (l + 1) / 2 + k + 1;
        printf("%lld\n", res);
        return true;
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 16;; i--)
        if (check(i)) break;
    return 0;
}

试题I 双向排序

#include <iostream>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
int a[N], ans[N];
PII stk[N];
int top;
int n, m;

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int p, q;
        scanf("%d%d", &p, &q);
        if (!p) {
            while (top && stk[top].first == 0) q = max(q, stk[top--].second);
            while (top >= 2 && stk[top - 1].second <= q) top -= 2;
            stk[++top] = {0, q};
        } else if (top) {
            while (top && stk[top].first == 1) q = min(q, stk[top--].second);
            while (top >= 2 && stk[top - 1].second >= q) top -= 2;
            stk[++top] = {1, q};
        }
    }
    int k = n, l = 1, r = n;
    for (int i = 1; i <= top; i++) {
        int a = stk[i].first, b = stk[i].second;
        if (a == 0)
            while (r > b && l <= r) ans[r--] = k--;
        else
            while (l < b && l <= r) ans[l++] = k--;
        if (l > r) break;
    }

    if (top & 1)
        while (l <= r) ans[l++] = k--;
    else
        while (l <= r) ans[r--] = k--;

    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}

试题J 括号序列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5010, MOD = 1e9 + 7;

int n;
char str[N];
LL f[N][N];

LL work() {
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        if (str[i] == '(') {
            for (int j = 1; j <= n; j++)
                f[i][j] = f[i - 1][j - 1];
        } else {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
            for (int j = 1; j <= n; j++)
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
        }

    for (int i = 0; i <= n; i++)
        if (f[n][i])
            return f[n][i];
    return -1;
}

int main() {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    LL l = work();
    reverse(str + 1, str + n + 1);
    for (int i = 1; i <= n; i++)
        if (str[i] == '(') str[i] = ')';
        else str[i] = '(';
    LL r = work();
    printf("%lld\n", l * r % MOD);
    return 0;
}