CF构造题1600-1800(1)

D. Same Count One(Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!))

题意

给定 (n) 个长度为 (m) 的 01 序列,每次操作可以选择两个序列a1, a2,并选择一个(pos), std::swap(a1[pos], a2[pos]), 求是每个序列中的 (1) 的个数都相等所需的最小操作数。

思路

可以发现 ((1) 的总数 ) (bmod n neq 0) 时, 是无解的。

(avg =) ((1) 的总数 ) (/ n), 我们可以把这 (n) 个序列分为两类,严格小于 (avg) 的 和严格大于 (avg) 的,其他的序列可以丢掉。

严格大于 (avg) 的序列都可以为 严格小于 (avg) 的序列补充 (1), 直到 严格大于 (avg) 的序列 (1) 的个数等于 (avg) 或者 严格小于 (avg) 的序列 (1) 个数等于 (avg)

直接模拟即可。

实现

void solve_problem() {
    int n, m;
    std::cin >> n >> m;
    std::vector a(n, std::vector(m, 0));
    int avg = 0;
    for (int i = 0;i > a[i][j];
            avg += a[i][j];
        }
    }
    if (avg % n == 0) {
        if (n == 1) {
            std::cout > q1, q2;
        for (int i = 0; i  avg) q2.push_back({cnt, i});
        }
        int ans1 = 0;
        std::vector<:array>> ans2;
        for (int i = 1; i 

D. Watch the Videos(2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams))

题意

(n) 个大小随意的视频和 (1) 个大小为 (m) 的磁盘,视频要下载到磁盘中才可以开始观看,下载第 (i) 个视频花费 (a_i) 的时间,开始下载第(i)个视频时,磁盘中要至少有(a_i)的空间才可以开始,下载完成需要花费 (1) 的时间观看完,看完之后视频立刻被从磁盘中删除,求看完所有视频需要的时间。(一次只能下载一个视频,观看视频的时候可以开始下载视频)

思路

最坏的答案(每次看完一个视频后才开始下载下一个视频), 计算方法为:

[ans = n + sum_{i = 1}^n a_i
]

可以发现如果在观看视频时下载视频,答案就可以 (-1)

要想使答案最小,只需要尽可能多的在观看视频时开始下载视频即可。

假设视频序列 (a) 从小到大排序, 那么可以找到一个最大的 (pos (1leq pos leq n)), 使得序列

[[a_{pos},a_1,a_{pos-1},a_2,a_{pos-2},a_3,cdots]
]

相邻两个数的和小于等于 (m)

按照这个序列观看,有 (pos - 1) 个视频是在正在观看视频时开始下载的。可以使答案减少 (pos - 1)

(pos) 是满足单调性的,因此可以二分来找到最大的 (pos)

实现

void solve_problem() {
    int n, m;
    std::cin >> n >> m;
    std::vector a(n);
    for (auto &x : a) {
        std::cin >> x;
    }
    std::sort(a.begin(), a.end());
    auto check = [&](int x) {
        int l = 0, r = x - 1;
        while (l  m - a[l]) return false;
            r--;
            l++;
        }
        return true;
    };
    int l = 1, r = n, ans = 0;
    while (l > 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    std::cout 

D. Range = √Sum(Codeforces Round #836 (Div. 2))

题意

构造一个长度为 (n) 的数组 (a_1,a_2, a_3, dots,a_n),使 (a_i) 各不相同,且 (max(a_1,a_2, a_3, dots,a_n) - min(a_1,a_2, a_3, dots,a_n) = sqrt{a_1,a_2, a_3, dots,a_n})

思路

(n) 为偶数时, 数组为:

[frac{n}{2},frac{n}{2} + 1,cdots ,n,n + 1,n + 2,n + frac{n}{2}.
]

数组可以被分成 (frac{n}{2}) 组,每组的和都为 (2n)

(n) 为奇数时,我们尝试 (max(a) - max(b) = n + 1), 因此数组的和应为 (n^2 + 2n + 1)

尝试使用 (n - 1) 个数分为 (frac{n-1}{2}) 组,每组和为 (2(n+1)), 组成的数组和为 (n^2 - 1)

此时这 (n - 1) 个数为:

[frac{n - 1}{2} + 2,frac{n - 1}{2} + 3,cdots,frac{n - 1}{2} + frac{n - 1}{2},n + 2,n + 3,cdots,n + frac{n - 1}{2} + 1
]

知道了最小项,最大项也可以计算出来 (n + frac{n - 1}{2} + 3)

这时数组的和为:

[n^2 - 1 + n + frac{n - 1}{2} + 3 = n^2 + n + frac{n - 1}{2} + 2
]

距离 (n^2 + 2n + 1) 还需要:

[begin{aligned}
(n^2 + 2n + 1) - (n^2 + n + frac{n - 1}{2} + 2) &= n - frac{n - 1}{2} - 1\
&=frac{2n - n + 1 - 2}{2}\
&=frac{n - 1}{2}
end{aligned}
]

我们可以让 第 (frac{n - 1}{2} + 1) 项到第 (n - 1) 项都 (+1) 来抵消掉 (frac{n - 1}{2})

因为第 (n - 1)(n + frac{n - 1}{2} + 1) 与 第 (n)(n + frac{n - 1}{2} + 3) 相差 (2),所以 (+1) 操作不会使数组产生重复的数。

此时我们的数组已经构造完成:

[frac{n - 1}{2} + 2,frac{n - 1}{2} + 3,cdots,frac{n - 1}{2} + frac{n - 1}{2},n + 3,n + 4,cdots,n + frac{n - 1}{2} + 2,n + frac{n - 1}{2} + 3
]

实现

void solve_problem() {
    int n;
    std::cin >> n;
    if (n % 2 == 0) {
        for (int i = 0; i 

文章来源于互联网:CF构造题1600-1800(1)

THE END
分享
二维码