Educational Codeforces Round 182 (div2) • santisify Site

A Cut the Array#

题目描述#

给定数组 $A$ , 需要输出满足以下的 $l$ , $r$ ：

$s_{1} = \sum^{l}_{i=1}A_{i} \ Mod\ 3$

$s_{2} = \sum^{r}_{i=l + 1}A_{i} \ Mod\ 3$

$s_{3} = \sum^{n}_{i=r + 1}A_{i} \ Mod\ 3$

$s_{1}$ , $s_{2}$ , $s_{3}$ 互不相同或者都相同。若不存在输出 $0 \ 0$

解题思路#

由于 $n$ 的数据范围较小，我们可以直接枚举每个 $l$ , $r$ ，满足条件直接输出即可.

参考代码#

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

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

    for (int l = 1; l < n; l ++) {
        for (int r = l + 1; r < n; r ++) {
            int s1 = s[l], s2 = s[r] - s[l], s3 = s[n] - s[r];
            if (s1 % 3 == s2 % 3 && s2 % 3 == s3 % 3) {
                std::cout << l << ' ' << r << std::endl;
                return;
            }
            if (s1 % 3 != s2 % 3 && s1 % 3 != s3 % 3 && s2 % 3 != s3 % 3) {
                std::cout << l << ' ' << r << std::endl;
                return;
            }
        }
    }
    std::cout << "0 0" << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin . tie(nullptr), std::cout . tie(nullptr);
    int ___ = 1;
    std::cin >> ___;
    while (___ --) solve();
}

cpp

B Maximum Cost Permutation#

Maximum Cost Permutation ↗

题目描述#

给定一个长度为 $n$ 的数组, 数组中的数都为非负整数，并且正整数不重复，现在将数组中的 $0$ 替换为正整数，并且与已有的不重复。

现定义代价为：将这个数组变为递增的数组，所操作的区间大小。

输出最大的代价

解题思路#

我们可以发现要想要代价最大就需要将数组尽可能的变为递减的数组，那么就可以将尽可能大的数放在前面，这样就可以使得代价最大

参考代码#

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), ct(n + 1, 0), q;
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
        ct[a[i]] ++;
    }

    for (int i = 1; i <= n; i ++) {
        if (ct[i] == 0) q.push_back(i);
    }
    std::reverse(q.begin(), q.end());
    int opt = 0;
    for (int i = 0; i < n; i ++) {
        if (a[i] == 0) {
            a[i] = q[opt ++];
        }
    }
    int l = 0, r = n - 1;
    while (a[l] == l + 1 && l + 1 < n) l ++;
    while (a[r] == r + 1 && r >= 0) r --;

    if (l > r) {
        std::cout << 0 << std::endl;
    } else {
        std::cout << r - l + 1 << std::endl;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int ___ = 1;
    std::cin >> ___;
    while (___ --) solve();
}

cpp

C Non-Descending Arrays#

Non-Descending Arrays ↗

题目描述#

两个数组 $a$ , $b$ 。你可以选择一些下标 $i$ ，使得这些下标对应的位置交换。最后要使得两个数组都是升序。求方案数。

解题思路#

显然只有交换和不交换两个状态。那么记 $dp[i][0/1]$ 表示第个位置交换/不交换使得前缀升序的方案数，那么考虑 $i - 1$ 交不交换，看两个位置是否合法。

参考代码#

代码省略取模类可参考jly算法模板 ↗，当然也可以选择边加边模

#include<bits/stdc++.h>
// 此处放置取模类

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1), b(n + 1);
    std::vector dp(n + 1, std::array<Z, 2>{});

    for (int i = 0; i < n; i ++) std::cin >> a[i + 1];
    for (int i = 0; i < n; i ++) std::cin >> b[i + 1];
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 1; i <= n; i ++) {
        if (a[i] >= a[i - 1] && b[i] >= b[i - 1]) {
            dp[i][0] += dp[i - 1][0];
            dp[i][1] += dp[i - 1][1];
        }
        if (a[i] >= b[i - 1] && b[i] >= a[i - 1]) {
            dp[i][0] += dp[i - 1][1];
            dp[i][1] += dp[i - 1][0];
        }
    }
    std::cout << dp[n][1] + dp[n][0] << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    std::cin >> _;
    while (_ --) solve();
}

cpp

D Price Tags#

Price Tags ↗

题目描述#

一个数组 $a$ ，和一个正整数 $y$ ，将数组的每个数都变为 $\lceil\frac{a_{i}}{x}\rceil$ 。

代价为: 将变化后与变化前出现相同的数逐个删除，剩余的数的个数 $w$ , 变化后的数组 $a$ 的总和 $s$ ，计算 $w \times y + s$ 的最大值。

解题思路#

由于数组元素都是向上取整，可以发现，在一个区间 $[(x-1)*m+1, x * m]$ 在做运算后都是 $m$ ，那么我们就可以对 $a$ 数组进行区间处理。

记 $ma$ 为 $a$ 中最大值，那么对于一个 $x$ ，所有数操作后的值域都在 $[1, \frac{ma}{x}]$ 之间，那么考虑枚举 $x$ ，对于一个值 $j$ ，除 $x$ 向上取整后会变成的数的范围为 $[(j - 1)*x+1, j*x]$ ，用前缀和记录这个范围原本有多少数，就可以得到和原本 $j$ 的个数的差异。最后计算出答案即可

参考代码#

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
    int n, c, ma = -1e8;
    std::cin >> n >> c;
    std::vector<int> a(n), ct(200005, 0);
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
        ct[a[i]] ++;
        ma = std::max(ma, a[i]);
    }

    if (ma == 1) {
        std::cout << n << std::endl;
        return;
    }

    auto s = ct;
    for (int i = 1; i < 200005; i ++) {
        s[i] += s[i - 1];
    }

    int ans = -1e18;
    for (int x = 2; x <= ma; x ++) {
        int m = (ma + x - 1) / x;
        int res = 0;
        for (int j = 1; j <= m; j ++) {
            int l = (j - 1) * x + 1, r = std::min(ma, j * x);
            if (l > ma) {
                break;
            }
            int w = s[r] - s[l - 1];
            res += w * j;
            res -= c * std::max(0ll, w - ct[j]);
        }
        ans = std::max(res, ans);
    }

    std::cout << ans << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    std::cin >> _;
    while (_ --) solve();
}

cpp