Codeforces Round 618 (Div. 2)

发表于 更新于 分类于 阅读次数： 本文字数： 723 阅读时长 ≈ 3 分钟
Love is not only a sentiment but also an art.

A. Non-zero

题目大意：

  • 可以选择一个整数a[i]，然后将其+1，然后询问最后是否可以使得这个序列的总和以及乘积不为0

思路：

  • 我们只需要统计一下sum的值，以及0的个数，只要sum + cnt等于0，那么就输出cnt + 1，否则输出cnt
  • 因为我们可以在保证乘积不为0的情况下，加1使得和也不为0

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

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

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

    if (sum + cnt == 0) {
        std::cout << cnt + 1 << "\n";
    } else {
        std::cout << cnt << "\n";
    }
}

B. Assigning to Classes

题目大意：

  • 将2n个整数划分为两个集合，这两个集合的元素个数要满足都是奇数，然后求他们的中位数最小差值

思路：

  • 直接排序后按照下标的奇偶性分开取，最后就发现两个集合中的中位数的差就是a[n] - a[n - 1]，毕竟这两个集合是单调的

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

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

    std::vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    std::cout << a[n] - a[n - 1] << "\n";
}

C. Anu Has a Function

思路：

  • 可以发现，只要我们把最高位的那个数放在首位，然后其他的位置不管怎么放，最后的结果一定是最大的，因为|操作就等价于取max(0/1)，所以只要我们最高位那个元素是最大的，那么最后的函数运算结果一定都比其他的数大

时间复杂度：\(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

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

    int ans = 0;
    for (int i = 30; i >= 0; i--) {
        int cnt = 0, p = 0;
        for (int j = 0; j < n; j++) {
            if (a[j] >> i & 1) {
                p = j, cnt++;
            }
        }
        if (cnt == 1) {
            ans = p;
            break;
        }
    }
    std::cout << a[ans] << " ";
    for (int i = 0; i < n; i++) {
        if (ans != i) {
            std::cout << a[i] << " ";
        }
    }

    return 0;
}

E. Water Balance

思路：

  • 要使这个序列字典序最小，那么从前往后一定要是比之前的高位小的数，这个过程可以用单调队列来模拟
  • 每次我们在这个队列里插入一个当前元素的值和当前缓存序列的长度，只要 \(sum_{now} > a_{highest} \times len\) 就退出继续缩减的过程，最后输出整个序列即可

时间复杂度：\(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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(9);

    int n;
    std::cin >> n;

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

    std::deque<std::pair<i64, i64>> q;
    for (int i = 1; i <= n; i++) {
        i64 cur = a[i], len = 1;
        while (!q.empty() && q.back().second * cur <= q.back().first * len) {
            cur += q.back().first;
            len += q.back().second;
            q.pop_back();
        }
        q.push_back({cur, len});
    }

    while (!q.empty()) {
        for (int i = 1; i <= q.front().second; i++) {
            std::cout << 1.0 * q.front().first / q.front().second << "\n";
        }
        q.pop_front();
    }

    return 0;
}