Codeforces Round 947 (Div. 1 + Div. 2)

发表于 更新于 分类于 阅读次数： 本文字数： 710 阅读时长 ≈ 3 分钟
Just do it, come on, guys!

A. Bazoka and Mocha's Array

题目大意：给我们一个数组，我们可以把它划分为两个子数组，然后交换位置，问是否可以让这个数组不降序

思路：

  • 可以发现，只能左右交换的话，那不就是在一个长度为 \(n\) 的数组后面，接上一个原始数组么，然后枚举长度 \(n\)，然后判断是否存在长度为 \(n\) 的数组不降序。

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

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;

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

    for (int i = 0; i < n; i++) {
        if (std::is_sorted(a.begin() + i, a.begin() + i + n, std::less())) {
            std::cout << "Yes\n";
            return ;
        }
    }
    std::cout << "No\n";
}

B. 378QAQ and Mocha's Array

题目大意：给我们一个数组，问是否可能选取两个元素，然后使得所有的数都可以被这两个元素的任意一个整除(也可以两个都整除)。

思路：

  • 首先，可以想到，\(min(a_i)\) 一定要选，因为比它大的数一定不能被它整除，然后，我们直接暴力枚举剩下的数 \((2 \sim n)\) 中是否存在一个数，可以把不能被 \(a_1\) 整除的所有数都整除即可。

时间复杂度：\(O(n \times (logn + \sqrt 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
46
47
void solve() {
    int n;
    std::cin >> n;

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

    if (std::count(a.begin(), a.end(), 1) != 0) {
        std::cout << "Yes\n";
        return ;
    }

    std::set<int> set;
    for (int i = 0; i < n; i++) {
        set.insert(a[i]);
    }

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

    int cur = 0;
    std::vector<int> p;
    for (int i = 0; i < n; i++) {
        if (a[i] % a[0] == 0) {
            cur++;
        } else {
            p.push_back(a[i]);
        }
    }

    for (int i = 1; i < n; i++) {
        int cur = 0;
        for (int j = 0; j < p.size(); j++) {
            if (p[j] % a[i] == 0) {
                cur++;
            } else {
                break;
            }
        }
        if (cur == p.size()) {
            std::cout << "Yes\n";
            return ;
        }
    }
    std::cout << "No\n";
}

C. Chamo and Mocha's Array

题目大意：给我们一个数组，每次可以选取一个区间 \([l, r]\) ，将这个区间覆盖为 \([l, r]\) 的中位数，问把整个数组 \(a\) 全部覆盖为同一个数，这个数的最大可能值

思路：

  • 可以发现，每次我们选取连续的长度为 \(3\) 的子数组，然后将这个区间覆盖为它的中位数，这样可以做到将所有的区间都置为同一个数。同时，这是最优的策略。我们统计所有连续长度为 \(3\) 的子数组的中位数的最大值。这就是最终的最大中位数。
  • \(n = 2\) 的数组要特判。

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

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    if (n == 2) {
        std::cout << std::min(a[0], a[1]) << "\n";
    } else {
        i64 ans = 0;
        for (int i = 1; i + 1 < n; i++) {
            int min = std::min({a[i - 1], a[i], a[i + 1]});
            int max = std::max({a[i - 1], a[i], a[i + 1]});
            ans = std::max(ans, 1LL * a[i - 1] + a[i] + a[i + 1] - min - max);
        }
        std::cout << ans << "\n";
    }
}