牛客小白月赛88

发表于 更新于 分类于 阅读次数： 本文字数： 608 阅读时长 ≈ 2 分钟
Beauty is found within.

A. 超级闪光牛可乐

思路：

  • 直接找到最大的哪个价值的字符，然后输出 \(\lceil \frac{x + max - 1}{max} \rceil\) 个最大价值的字符即可

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

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int x;
    std::cin >> x;

    int n;
    std::cin >> n;

    int mx = 0;
    char a = 'a';
    for (int i = 0; i < n; i++) {
        char c;
        int w;
        std::cin >> c >> w;
        if (w > mx) {
            mx = w;
            a = c;
        }
    }

    int m = (x + mx - 1) / mx;

    for (int i = 0; i < m; i++) {
        std::cout << a;
    }
    
    return 0;
}

B. 人列计算机

思路：

  • 本题最大的难点在于空格的输入，模拟即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::vector<std::string> g(5);
    for (int i = 0; i < 5; i++) {
        std::getline(std::cin, g[i]);
    }

    if (std::isdigit(g[1][0]) && std::isdigit(g[3][0])) {
        int A = g[1][0] - '0', B = g[3][0] - '0';
        if (g[2][5] == '&') {
            std::cout << (A & B) << "\n";
        } else {
            std::cout << std::min(1, A + B) << "\n";
        }
    } else {
        int A = g[2][0] - '0';
        std::cout << int(A == 0) << "\n";
    }

    return 0;
}

C. 时间管理大师

思路：

  • 题目的h >= 3，所以只需要判断m即可，我们只需要用map或者set维护一个点集即可

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

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::map<std::pair<int, int>, bool> mp;
    std::vector<std::pair<int, int>> c(n);
    for (auto &[h, m] : c) {
        std::cin >> h >> m;

        if (m >= 5) {
            mp[{h, m - 5}] = true;
            mp[{h, m - 3}] = true;
            mp[{h, m - 1}] = true;
        } else if (m == 4) {
            mp[{h - 1, 59}] = true;
            mp[{h, m - 3}] = true;
            mp[{h, m - 1}] = true;
        } else if (m == 3) {
            mp[{h - 1, 58}] = true;
            mp[{h, m - 3}] = true;
            mp[{h, m - 1}] = true;
        } else if (m == 2) {
            mp[{h - 1, 57}] = true;
            mp[{h - 1, 59}] = true;
            mp[{h, m - 1}] = true;
        } else if (m == 1) {
            mp[{h - 1, 56}] = true;
            mp[{h - 1, 58}] = true;
            mp[{h, m - 1}] = true;
        } else if (m == 0) {
            mp[{h - 1, 55}] = true;
            mp[{h - 1, 57}] = true;
            mp[{h - 1, 59}] = true;
        }
    }

    std::cout << mp.size() << "\n";
    for (auto [x, y] : mp) {
        std::cout << x.first << " " << x.second << "\n";
    }
    return 0;
}

D. 我不是大富翁

思路：

  • dp状态：dp[i][j]表示经过第i轮后，是否可以站在j位置
  • dp状态转移方程：dp[i][j] |= dp[i - 1][lst]

时间复杂度：\(O(n \times m)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(m + 1);
    for (int i = 1; i <= m; i++) {
        std::cin >> a[i];
    }

    std::vector dp(m + 1, std::vector<int>(n + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < n; j++) {
            int lst = (j + a[i]) % n;
            dp[i][j] |= dp[i - 1][lst];
            lst = ((j - a[i]) % n + n) % n;
            dp[i][j] |= dp[i - 1][lst];
        }
    }
    std::cout << (dp[m][0] ? "YES\n" : "NO\n");
    
    return 0;
}