第九届蓝桥杯C++ B组代码

题目

试题A 第几天

答案：125

试题B 明码

#include <iostream>

using namespace std;

void decode(int x) {
    for (int i = 7; i >= 0; i--) {
        if (x >> i & 1) printf("*");
        else printf(" ");
    }
}

int main() {
    int x, y;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 16; j++) {
            cin >> x >> y;
            decode(x);
            decode(y);
            cout << endl;
        }
        cout << endl;
    }

    long long ans = 1;
    for (int i = 1; i <= 9; i++) {
        ans *= 9;
    }
    cout << ans;
    return 0;
}

答案：387420489

试题C 乘积尾零

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

void mul(vector<int> &A, int b) {
    vector<int> res;
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t = A[i] * b + t;
        res.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        res.push_back(t % 10);
        t /= 10;
    }
    A = res;
}

int main() {
    vector<int> A;
    A.push_back(1);
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++) {
            int x;
            scanf("%d", &x);
            mul(A, x);
        }
    int res = 0;
    for (int i = 0; i < A.size(); i++) {
        if (A[i] == 0) res ++;
        else break;
    }
    printf("%d\n", res);
    return 0;
}

答案：31

试题D 测试次数

#include <iostream>

using namespace std;

int f[4][1010];

int main() {
    int n = 1000;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = j;

    for (int i = 2; i <= 3; i++)
        for (int j = 1; j <= n; j++) 
            for (int k = 1; k <= j; k++) 
                f[i][j] = min(f[i][j], max(f[i - 1][k - 1], f[i][j - k]) + 1);

    printf("%d\n", f[3][n]);

    return 0;
}

试题E 快速排序

#include <stdio.h>

int quick_select(int a[], int l, int r, int k) {
    int p = rand() % (r - l + 1) + l;
    int x = a[p];
    {
        int t = a[p];
        a[p] = a[r];
        a[r] = t;
    }
    int i = l, j = r;
    while (i < j) {
        while (i < j && a[i] < x) i++;
        if (i < j) {
            a[j] = a[i];
            j--;
        }
        while (i < j && a[j] > x) j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        }
    }
    a[i] = x;
    p = i;
    if (i - l + 1 == k) return a[i];
    if (i - l + 1 < k) return quick_select(a, i + 1, r, k - (i - l + 1)); //填空
    else return quick_select(a, l, i - 1, k);
}

int main() {
    int a[100];
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("%d\n", quick_select(a, 0, n - 1, 5));
    return 0;
}

试题F 递增三元数组

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 100010;
int a[N], b[N], c[N];
int sa[N], sc[N];
int n;

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

    for (int i = 1; i <= N; i++) {
        a[i] = a[i] + a[i - 1];
        c[i] = c[i] + c[i - 1];
    }

    LL res = 0;
    for (int i = 1; i <= n; i++) {
        int t = b[i];
        sa[i] = a[t - 1];
        sc[i] = c[N - 1] - c[t];
        res = res + (LL) sa[i] * sc[i];
    }
    printf("%lld\n", res);
    return 0;
}

试题G 螺旋折线

#include <iostream>

using namespace std;
typedef long long LL;
LL x, y;

int main() {
    scanf("%lld%lld", &x, &y);
    LL k = max(abs(x), abs(y));
    LL res = 4 * k * k;
    if (x >= y) res = res + abs(x - k) + abs(y - k);
    else res = res - abs(x - k) - abs(y - k);
    printf("%lld\n", res);
    return 0;
}

试题H 日志统计

#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;

const int N = 100010;
int cnt[N];
bool st[N];
int n, k, d;

PII seg[N];

int main() {
    scanf("%d%d%d", &n, &d, &k);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &seg[i].first, &seg[i].second);
    sort(seg, seg + n);
    for (int i = 0, j = 0; i < n; i++) {
        int s = seg[i].first, di = seg[i].second;
        cnt[di]++;
        while (s - seg[j].first >= d) {
            cnt[seg[j].second]--;
            j++;
        }
        if (cnt[di] >= k) st[di] = true;
    }

    int res = 0;
    for (int i = 0; i < N; i++)
        if (st[i])
            printf("%d\n", i);
    return 0;
}

试题I 全球变暖

#include <iostream>

using namespace std;
typedef pair<int, int> PII;

const int N = 1010;
char g[N][N];
bool st[N][N];
PII q[N * N];
int n;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int x, int y, int &total, int &bound) {
    total = 0;
    bound = 0;
    int hh = 0, tt = 0;
    q[0] = {x, y};
    st[x][y] = true;

    while (hh <= tt) {
        PII t = q[hh++];
        total++;
        bool flag = false;
        for (int i = 0; i < 4; i++) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= n) continue;
            if (st[a][b]) continue;
            if (g[a][b] == '.') {
                flag = true;
                continue;
            }
            q[++tt] = {a, b};
            st[a][b] = true;
        }
        if (flag) bound++;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%s", g[i]);

    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (g[i][j] == '#' && !st[i][j]) {
                int total = 0;
                int bound = 0;
                bfs(i, j, total, bound);
                if (total == bound) res++;
            }
        }
    printf("%d\n", res);
    return 0;
}

试题J 最大乘积

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010;
const LL MOD = 1000000009;
int n, k;
int a[N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    LL res = 1;
    LL sign = 1;
    int l = 0, r = n - 1;
    if (k & 1) {
        res = a[r--];
        if (res < 0)
            sign = -1;
        k--;
    }
    while (k) {
        LL x = (LL) a[l] * a[l + 1], y = (LL) a[r] * a[r - 1];
        if (x * sign > y * sign) {
            res = x % MOD * res % MOD;
            l += 2;
        } else {
            res = y % MOD * res % MOD;
            r -= 2;
        }
        k -= 2;
    }

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

    return 0;
}