Codeforces Round 929 (Div. 3)

发表于 更新于 分类于 阅读次数： 本文字数： 894 阅读时长 ≈ 3 分钟
The future belongs to those who believe in the beauty of their dreams.

A. Turtle Puzzle: Rearrange and Negate

思路：

  • 因为可以任意排序，所以只需要输出每一个数绝对值的总和

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

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

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i] = abs(a[i]);
    }
    std::cout << std::accumulate(a.begin(), a.end(), 0) << "\n";
}

B. Turtle Math: Fast Three Task

思路：

  • 每次可以进行删除一个数或者选一个数加1
  • 如果最终的余数(mod)为0，就一定不需要操作
  • 如果余数为2，或者序列中存在某个数的余数等于mod，就只需要操作1次
  • 否则一定需要2次

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

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

    int sum = std::accumulate(a.begin(), a.end(), 0);
    int mod = sum % 3;
    if (mod == 0) {
        std::cout << "0\n";
        return ;
    }

    if (std::count(a.begin(), a.end(), mod) || mod == 2) {
        std::cout << "1\n";
    } else {
        std::cout << "2\n";
    }
}

C. Turtle Fingers: Count the Values of k

思路：

  • 首先我们观察这个式子 \(l=k\times a^{x} \times b^{y}\)
  • 可以看出，\(a^x\) 和 \(b^y\) 一定是 \(l\) 的因子，那么，我们可以得到 \(\begin{cases} l \space \% \space a^x = 0 \\ l \space \% \space b^y = 0 \end{cases}\)​
  • 然后我们直接枚举 \(a\) 和 \(b\) 的指数即可，然后推导出 \(k = \frac{\frac{l}{a^x}}{b^y}\)

时间复杂度：\(O(log_al \times log_b(l / i))\)

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    int a, b, l;
    std::cin >> a >> b >> l;

    std::set<int> st;
    for (int i = 1; l % i == 0; i *= a) {
        for (int j = 1; l / i % j == 0; j *= b) {
            st.insert(l / i / j);
        }
    }
    std::cout << st.size() << "\n";
}

D. Turtle Tenacity: Continual Mods

思路：

  • 一个序列所有数从左到右互相取模，可以发现，只要最小的数在最前面，那么一定最终答案不为0
  • 所以，我们可以判断，最小的数的个数，如果为1，那么一定可以
  • 如果在除去最小的数的剩下的序列中，找到一个数mod min != 0，那么一定可以，因为它的余数一定比min更小，那就可以把这个数放到那个最小的数前面，构成一个以更小的数开头的新序列

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

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

    int min = a[0];
    if (std::count(a.begin(), a.end(), min) == 1) {
        std::cout << "YES\n";
        return ;
    }
    for (int i = 1; i < n; i++) {
        if (a[i] % min != 0) {
            std::cout << "YES\n";
            return ;
        }
    }
    std::cout << "NO\n";
}

E. Turtle vs. Rabbit Race: Optimal Trainings

题目大意为：

  • 给你一个序列，你可以获得分数，只要你可以在[l, r]这个区间内获得尽可能多的能量，但不能大于u，当然，你也可以获得超出给定值(u)的能量，但这样会使你的能量减少。求一个你可以获得最多能量的区间右端点r。

思路：

  • 可以先求个前缀和，这样就保证了单调性，然后二分右端点
  • 只要发现r == n时，u - sum[l, r] < s[l, r + 1] - u，那么输出r
  • 否则s[l, r + 1] - u < u - sum[l, r]，这样可以获得更大的分数，输出r + 1

时间复杂度：\(O(q\times logn)\)

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
void solve() {
    int n;
    std::cin >> n;

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

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

    int q;
    std::cin >> q;

    while (q--) {
        int l, u;
        std::cin >> l >> u;

        int left = l, right = n;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (u + s[l - 1] >= s[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (left == n || u - (s[right] - s[l - 1]) < s[right + 1] - s[l - 1] - u) {
            std::cout << right << " ";
        } else {
            std::cout << right + 1 << " ";
        }
    }
    std::cout << "\n";
}