牛客小白月赛91

发表于 更新于 分类于 阅读次数： 本文字数： 618 阅读时长 ≈ 2 分钟
A bad excuse is worse than none.

A. Bingbong的化学世界

思路：

  • 这几个苯环的二元取代物都有独有的特点，只需要特判判断这些独有的特点即可

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

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

    if (a[2][5] == '/') {
        std::cout << "o\n";
    } else if (a[0][3] == '|' && a[5][3] == '|') {
        std::cout << "p\n";
    } else {
        std::cout << "m\n";
    }
    
    return 0;
}

B. Bingbong的数数世界

思路：

  • 如果 n 为奇数，那么 Bing 可以拿的数字数量比 Bong 多一个，无论 Bong 怎么拿，Bing都可以保持最终一定获胜，所以 n 为奇数，就是 Bing 的必胜态
  • 如果 Bing 可以拿的奇数的数量为奇数，且 Bing 的可操控数值的数量大于等于 Bong，那么 Bing 一定赢，无论 Bong 怎么操作都无法扭转局面

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    int n;
    std::cin >> n;

    if (n & 1) {
        std::cout << "Bing\n";
    } else {
        if (((n + 1) / 2) % 2 == 1) {
            std::cout << "Bing\n";
        } else {
            std::cout << "Bong\n";
        }
    }
}

C. Bingbong的蛋仔世界

思路：

  • 分情况讨论，将当前点和安全区域的最短时间求出来，然后比较即可

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

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

    auto get = [&](int x, int y, int a, int b) {
        return abs(x - a) + abs(y - b);
    };

    int t = std::max((n - 1) / 2, (m - 1) / 2);
    
    int ans = 0;
    for (int i = 0; i < k; i++) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;

        int dist;
        if (n % 2 == 0 && m % 2 == 0) {
            dist = std::min({
                get((n - 1) / 2, (m - 1) / 2, x, y),
                get((n - 1) / 2, m / 2, x, y),
                get(n / 2, (m - 1) / 2, x, y),
                get(n / 2, m / 2, x, y)
            });
        } else if (n & 1 && m % 2 == 0) {
            dist = std::min(
                get(n / 2, m / 2, x, y),
                get(n / 2, (m - 1) / 2, x, y)
            );
        } else if (n % 2 == 0 && m & 1) {
            dist = std::min(
                get(n / 2, m / 2, x, y),
                get((n - 1) / 2, m / 2, x, y)
            );
        } else {
            dist = get(n / 2, m / 2, x, y);
        }
        ans += dist <= t;
    }
    std::cout << ans << "\n";

    return 0;
}

D. Bingbong的奇偶世界

思路：

  • 如果当前这个位置是偶数，那么 dp[i] = dp[i - 1] + cnt + 1 这里的 +1 为当前这个数位
  • 如果当前这个位置为奇数，那么 cnt += 1 因为当遇到偶数时，需要更新当前的方案数

时间复杂度：\(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
constexpr int P = 1E9 + 7;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    i64 ans = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        if ((s[i] - '0') % 2 == 0) {
            ans = (ans + cnt + 1) % P;
        }
        cnt = cnt * 2 % P; // 方案数
        if (s[i] != '0') {
            cnt = (cnt + 1) % P;
        }
    }
    std::cout << ans << "\n";

    return 0;
}