Codeforces Round 935 (Div. 3)

发表于 更新于 分类于 阅读次数： 本文字数： 502 阅读时长 ≈ 2 分钟
Clear thinking requires courage rather than intelligence.

A. Setting up Camp

思路：

  • 先凑b，如果b和c的一部分结合起来不能整除3，那么就直接输出-1，因为不能满足每一个帐篷都是三个人的情况

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

1
2
3
4
5
6
7
8
9
10
11
void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;
    
    int t = b % 3;
    if (t + c < 3 && t != 0) {
        std::cout << "-1\n";
        return ;
    }
    std::cout << 1LL * a + (1LL * b + c + 2) / 3 << "\n";
}

B. Fireworks

思路：

  • 我们先求出在m + 1个时间单位里，a和b要放多少次，然后把答案一累加即可
  • 即 \(ans = \lceil \frac{m + 1}{a} \rceil + \lceil \frac{m + 1}{b} \rceil\)

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

1
2
3
4
5
6
void solve() {
    i64 a, b, m;
    std::cin >> a >> b >> m;   

    std::cout << (m + 1 + a - 1) / a + (m + 1 + b - 1) / b << "\n";
}

C. Left and Right Houses

思路：

  • 用前缀和维护整个序列的0和1的个数，然后进行枚举位置即可
  • 注意距离计算要用double ，不然会被卡

时间复杂度：\(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
void solve() {
    int n;
    std::cin >> n;

    std::string a;
    std::cin >> a;

    std::vector<int> z(n + 1), o(n + 1);
    for (int i = 0; i < n; i++) {
        if (a[i] == '1') {
            o[i + 1] = o[i] + 1;
            z[i + 1] = z[i];
        } else {
            z[i + 1] = z[i] + 1;
            o[i + 1] = o[i];
        }
    }

    int ans = 0, dist = 2E9;
    for (int i = 0; i <= n; i++) {
        int z1 = z[i];
        int o1 = o[n] - o[i];
        int stanl = (i + 1) / 2, stanr = (n - i + 1) / 2;
        if (z1 >= stanl && o1 >= stanr) {
            double t = abs(i - n * 1.0 / 2);
            if (t < dist) {
                dist = t;
                ans = std::max(ans, i);
            }
        }
    }
    std::cout << ans << "\n";
}

D. Seraphim the Owl

思路：

  • 可以发现，不管怎么取，我们一定会把 min(a[i], b[i])的那个元素取走。
  • 所以只需要用 sum 维护前n - m个最小价值之和，然后最后1个元素考虑加最小的那一个即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int n, m;
    std::cin >> n >> m;

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

    i64 ans = 1E18, sum = 0;
    for (int i = n; i > 0; i--) {
        if (i <= m) {
            ans = std::min(ans, sum + a[i]);
        }
        sum += std::min(a[i], b[i]);
    }
    std::cout << ans << "\n";
}