第八届蓝桥杯省赛 C++ B组代码

题目

试题A 购物单

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

int main() {
    string shop_name;
    double price;
    string discount;

    double sum = 0;
    for (int i = 0; i < 50; i++) {
        cin >> shop_name >> price >> discount;
        if (discount == "半价") price *= 0.5;
        else {
            const char *s = discount.c_str();
            if (s[1] <= '9' && s[1] >= '0') {
                double d = ((double) (s[0] - '0') * 10 + (double) (s[1] - '0')) / 100;
                price *= d;
            } else {
                double d = ((double) (s[0] - '0') * 10) / 100;
                price *= d;
            }
        }
        sum += price;
    }
    cout << sum << endl;
    return 0;
}
// 答案：5200

试题B 等差素数列

#include <iostream>

using namespace std;
const int N = 10000010;
int primes[N], cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i])
            primes[cnt++] = i;

        for (int j = 0; primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    get_primes(10000000);
    for (int i = 0; i < cnt; i++) {
        int k = primes[i];
        bool flag;
        for (int d = 1; d <= 10000; d++) {
            flag = true;
            for (int n = 1; n <= 9; n++) {
                int t = k + n * d;
                if (st[t]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                printf("%d\n", d);
                break;
            }
        }
        if (flag) break;
    }
    return 0;
}
// 答案：210

试题C 承压计算

#include <iostream>
#include <cstring>

using namespace std;
const int N = 35;
double f[N][N];

int main() {
    int n = 30;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%lf", &f[i][j]);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            f[i][j] = f[i][j] + f[i - 1][j] / 2 + f[i - 1][j - 1] / 2;
        }
    }


    double max_val = -1e9, min_val = 1e9;
    for (int i = 1; i <= 30; ++i) {
        if (f[30][i] > max_val)max_val = f[30][i];
        if (f[30][i] < min_val)min_val = f[30][i];
    }

    printf("%.lf", 2086458231 / min_val * max_val);

    return 0;
}
// 答案：72665192664

试题D 方格分割

#include <iostream>
#include <cstring>

using namespace std;
const int N = 7;
int g[N][N];
int res;
bool st[N][N];

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

void dfs(int x, int y) {
    if (x == 0 || y == 0 || x == 6 || y == 6) {
        res++;
        return;
    }
    st[x][y] = true;
    st[6 - x][6 - y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || b < 0 || a > 6 || b > 6) continue;
        if (st[a][b]) continue;
        dfs(a, b);
    }
    st[x][y] = false;
    st[6 - x][6 - y] = false;
}

int main() {
    dfs(3, 3);
    printf("%d\n", res / 4);
    return 0;
}
// 答案：509

试题E 取数位

#include <stdio.h>

// 求x用10进制表示时的数位长度
int len(int x) {
    if (x < 10) return 1;
    return len(x / 10) + 1;
}

// 取x的第k位数字
int f(int x, int k) {
    if (len(x) - k == 0) return x % 10;
    return f(x / 10, k);
}

int main() {
    int x = 23574;
    printf("%d\n", f(x, 3));
    printf("%d\n", f(893275, 2));
}

试题F 最大公共子串

#include <stdio.h>
#include <string.h>

#define N 256

int f(const char *s1, const char *s2) {
    int a[N][N];
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int i, j;

    memset(a, 0, sizeof(int) * N * N);
    int max = 0;
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                a[i][j] = a[i - 1][j - 1] + 1;
                if (a[i][j] > max) max = a[i][j];
            }
        }
    }

    return max;
}

int main() {
    printf("%d\n", f("abcdkkk", "baabcdadabc"));
    printf("%d\n", f("aaakkkabababa", "baabababcdadabc"));
    printf("%d\n", f("abccbaacbcca", "ccccbbbbbaaaa"));
    printf("%d\n", f("abcd", "xyz"));
    printf("%d\n", f("ab", "ab"));
    return 0;
}

试题G 日期问题

#include <iostream>

using namespace std;

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_valid(int y, int m, int d) {
    if (!m || !d || m > 12 || d > 31) return false;
    if (y % 400 == 0 || y % 4 == 0 && y % 100) days[2] = 29;
    else days[2] = 28;
    if (d > days[m]) return false;
    return true;
}

int main() {
    int a, b, c;
    scanf("%d/%d/%d", &a, &b, &c);

    for (int i = 19600101; i <= 20591231; i++) {
        int y = i / 10000, m = i % 10000 / 100, d = i % 100;
        // printf("%d %d %d\n", y, m, d);
        if (is_valid(y, m, d)) {
            if (   y % 100 == a && m == b && d == c
                || y % 100 == c && m == b && d == a
                || y % 100 == c && m == a && d == b) {
                    printf("%d-%.2d-%.2d\n", y, m, d);
                }
        }
    }

    return 0;
}

试题H 包子凑数

#include <iostream>

using namespace std;
const int N = 110, M = 10000;
bool f[M];
int a[N];
int n;

int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}

int main() {
    scanf("%d", &n);
    int max_gcd = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        max_gcd = gcd(max_gcd, a[i]);
    }
    if (max_gcd != 1) {
        puts("INF");
        return 0;
    }

    f[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < M; j++) {
            if (j >= a[i]) f[j] |= f[j - a[i]];
        }

    int res = 0;
    for (int i = 1; i < M; i++)
        if (!f[i]) res++;

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

    return 0;
}

试题I 分巧克力

#include <iostream>

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

const int N = 100010;

PII Size[N];
int n, k;

int check(int x) {
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = res + (Size[i].first / x) * (Size[i].second / x);
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i++) 
        scanf("%d%d", &Size[i].first, &Size[i].second);

    int l = 0, r = 100000;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid) >= k) l = mid;
        else r = mid - 1;
    }
    if (check(l) >= k) printf("%d\n", l);

    return 0;
}

试题J k倍区间

#include <iostream>

using namespace std;
typedef long long LL;

const int N = 100010;
LL cnt[N], s[N];
int n, k;

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    LL res = 0;
    cnt[0] = 1;
    for (int i = 0; i < n; i++) {
        res += cnt[s[i] % k];
        cnt[s[i] % k]++;
    }

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

    return 0;
}