牛客小白月赛83

发表于 更新于 分类于 阅读次数： 本文字数： 548 阅读时长 ≈ 2 分钟
Prevention is better than cure.

A. 小天的金银铜铁

思路：

  • 直接模拟判断即可

时间复杂度：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int a, b, c, d, e;
    std::cin >> a >> b >> c >> d >> e;

    int A, B, C, D;
    std::cin >> A >> B >> C >> D;

    i64 sum = A * a + B * b + C * c - d * D;
    std::cout << (sum > e ? "YES\n" : "NO\n");
    
    return 0;
}

B. 小天的魔法

思路：

我们可以将所有情况分为：

  • 不使用 \(a_i\) , 全部使用 \(b_i\)

  • 交替使用 \(a_i\) 和 \(b_i\)

在两者取一个最小值即可

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, x;
    std::cin >> n >> m >> x;

    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
    }
    
    std::sort(a.rbegin(), a.rend());
    std::sort(b.rbegin(), b.rend());

    int ne = x;
    std::vector<int> an(2);
    for (int i = 0; i < m; i++) {
        if (ne <= 0) {
            break;
        }
        if (ne >= b[i]) {
            ne -= b[i];
            an[1] += 1;
        }
    }

    for (int i = 0; i < std::min(n, m); i++) {
        int t = a[i] * b[i];
        if (x <= 0) {
            break;
        }
        if (x >= t) {
            x -= t;
            an[0] += 2;
        } else {
            if (x <= b[i]) {
                an[0] += 1;
                x -= b[i];
            } else {
                x -= t;
                an[0] += 2;
            }
        }
    }

    if (x) {
        if (n < m) {
            for (int i = std::min(n, m); i < m; i++) {
                if (x <= 0) {
                    break;
                }
                if (x >= b[i]) {
                    x -= b[i];
                    an[0] += 1;
                }
            }
        }
    }

    if (x > 0 && ne > 0) {
        std::cout << "-1\n";
        return 0;
    }

    if (ne > 0) {
        std::cout << an[0] << "\n";
    } else {
        std::cout << std::min(an[0], an[1]) << "\n";
    }

    return 0;
}

C. 小天的 Minecraft

思路：

可以做出铜镐的情况可以分为以下3种：

  • \(16\) 个铜粒 \(P_1\)
  • \(12\) 个铜粒和 \(4\) 个银粒 \(P_2\)
  • \(12\) 个铜粒和 \(4\) 个金粒 \(P_3\)

那么运用二项分布的知识

  • \(P_1\) = \((\frac{a}{16})^{16}\)

  • \(P_2\) = \(C^{12}_{16} \times (\frac{a}{16})^{12} \times (\frac{b}{16})^4\)

  • \(P_3\) = \(C_{16}^{12} \times (\frac{a}{16})^{12} \times (\frac{c}{16})^4\)

\(\therefore ans = P_1 + P_2 + P_3\)​

时间复杂度：\(O(N^2)\)

附：\(N = 20\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
constexpr int N = 20;
int C[N][N];

void solve() {
    double a, b, c;
    std::cin >> a >> b >> c;

    double c1 = pow(a / 16, 16);
    double c2 = C[16][12] * pow(a / 16, 12) * pow(b / 16, 4);
    double c3 = C[16][12] * pow(a / 16, 12) * pow(c / 16, 4);

    std::cout << c1 + c2 + c3 << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);

    for (int i = 0; i < 20; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
        }
    }

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}