Codeforces Round 924 (Div.2)

题目链接

Codeforces Round 924 (Div.2)

Problem A: Rectangle Cutting

  • 时间限制：1秒
  • 内存限制：256 MB

题目描述

　　给定一个长和宽都是整数的长方形，你可以尝试将它们先分割为两个边长都是整数的小长方形再组合成一个不同的长方形。注意，2×1 的长方形和 1×2 的长方形我们认为是同样的长方形，因为它们彼此的长和宽都分别相等，因此一个 1×2 的长方形你无法分割重组出新的长方形。现在给出长方形的长和宽，请问你是否能够分割重组出新的长方形？

  • 输入描述
    　　第一行，一个正整数 $t(1 \le t \le 10^4)$ ，表示接下来有 $t$ 组数据。
    　　接下来 $t$ 行，每行具有两个整数 $a,b(1\le a,b \le 10^9)$，表示当前这组数据给出的长方形的两条相邻边的长度（并不保证哪条一定更长）。

  • 输出描述
    　　对于每组数据，如果能组成新的长方形，那么输出一行“Yes”，否则输出一行“No”。

解题思路

　　由于分割后的长方形需要重新组合，那么它们至少要有一条边长度是一致的，所以一定是选取偶数长度的边从中间进行分割才有机会组合出新的长方形。那么如果给出的长方形边长都是奇数，必然无法实现目标。而如果都是偶数，那么必然可以实现目标。而如果只有一方是偶数，并且偶数方是奇数方的两倍，那么无法组合出新的长方形。

解题代码

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
#include <iostream>
using namespace std;

void solve()
{
    int a, b;
    cin >> a >> b;
    // 如果两条边都是奇数，那么没法分割成整数边的两个小长方形
    if (a % 2 && b % 2)
    {
        cout << "No\n";
        return;
    }
    // 如果两条边都是偶数，那么必然可以分割重组为新长方形
    if (a % 2 == 0 && b % 2 == 0)
    {
        cout << "Yes\n";
        return;
    }
    // 当只有一边是偶数时，如果偶数边的长度是奇数边的两倍，那么无法组合成新长方形
    if ((a % 2 == 0 && a == 2 * b) || (b % 2 == 0 && b == 2 * a))
    {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Problem B: Equalize

  • 时间限制：1秒
  • 内存限制：256 MB

题目描述

　　给定一个长度为 $n$ 的数组 $a_1,a_2,…,a_n$，你可以执行一次以下操作：

  1. 设计一个长度为 $n$ 的排列 $p_1,p_2,…,p_n$，所谓排列就是一个长度为 $n$ 的数组，其中的 $1,2,…,n$ 这 $n$ 个数各出现 $1$ 次。例如 $[1,2,3]$ 和 $[2,1,3]$都是长度为 $3$ 的排列，而 $[1,2,2]$ 不是。
  2. 将排列的元素值依次加到相应位置的素组元素中。即：对于所有的 $i=1,2,…,n$， 令 $a_i = a_i + p_i$。

　　问：在执行这样一次操作之后，最多能有多少个元素的数值会是一样的？

  • 输入描述
    　　第一行，一个正整数 $t (1\le t\le 2*10^4)$，表示接下来有 $t$ 组数据。
    　　每组数据具有两行，第一行，一个正整数 $n (1\le n \le 2 * 10^5)$，表示给出的数列的长度。
    　　第二行， $n$ 个整数，表示数列 $a_1,a_2,…,a_n (1\le a_i \le 10^9)$。
    　　数据保证对于所有组的 $n$ 总和不超过 $2*10^5$。

  • 输出描述
    　　每组数据输出一行，每行一个整数，表示等值元素的最大可能个数。

解题思路

　　我们必然要将一个排列的值加入到数组中，在将排列和数组都进行升序排序的情况下，排列是公差为 $1$ 的等差数列，最好的情况就是数组本身也是一个公差为 $1$ 的等差数列，这样可以让排列反过来恰好补齐。当然，数列可能也不会这么工整，可能是 $[1,1,2,3,3,4,7]$ 这样的，我们先计算它的差分数组（所谓差分数组就是记录该元素与上一个元素的差值，首元素没有上一个元素，直接取0）得到 $C=[0,0,1,1,0,1,3]$，我们的排列可以用来填补这些差值，比如 $C_i = 1$ 意味着这个元素和上个元素相差 $1$ ，我们可以分别放 $2,1$ 来补全差值。但是如果 $C_i = 0$，那么反而无法让它们保持相等。
　　要解决题目的问题，我们就要利用排列去消除差分数组中尽可能长的一段连续区间内的数。首先，为什么要是连续的区间？对于数组 $[1,2,100,150,151]$，它的差分数组是 $[0,1,98,50,1]$，其中有两个 $1$，但是如果只是消去这两个 $1$，中间的没有消去，那么这两个位置只是和相邻的上一个元素相等，彼此之间没有相等。而如果数组足够长，以至于你有足够多的排列元素可以让排序后的数组中不相邻的元素相等，那么你完全可以选择让中间的元素和前面的那个元素相等，这样花费的代价只会更低。
　　那么现在，排列的长度 $n$ 就可以视作为用于填补差值的剩余值，随着填补它会剩余越来越少。假设有差分数组 $C=[0,1,2,3,100,1,2,3]$ ，此时 $n=8$ ，我填补 $C_2=1$时，需要令 $p_1$ 为一个较大的数，然后 $p_2$ 比它小 $1$ ，比如 $p_1 = 8,p_2=7$，然后我要填补 $C_3=2$，我的 $p_3$ 又要比 $p_2$ 小 $2$ ，于是 $p_3=5$ ，以此类推， $p_4=2$， $C_5$ 就已经无法被填补了。那么不难发现，如果刚好够用的情况下，我们总共能够填补 $n-1$ 的数值，因为排列的最大值和最小值相差 $n-1$ 。
　　所以如果一个区间 $[L,R]$ 内的 $C_i$ 总和不超过 $n-1$ ，那么我们就有机会让里面的 $C_i \neq 0$ 所对应的元素相等。而里面起初 $C_i=0$ 的元素只能舍弃，无法保持相等。我们可以采用 双指针 算法来维护我们的最终答案。当发现一个区间 $[L,R]$ 的 $C_i$ 总和没有超过 $n-1$ 时，我们统计其区间内部原本的 $C_i=0$ 的元素个数，记为 $Z$ ，那么更行答案 $ans = \max(ans,L-R+1-Z + 1)$。这里最后为什么又加 $1$ 呢，因为前面只是计算填了多少个坑，让后面的元素值等于参照元素值，参照元素也要统计进去。

解题代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end() - 1);
    for (int i = n - 1; i > 0; --i)
    {
        arr[i] = arr[i] - arr[i - 1];
    }
    arr[0] = 0;
    int ans = 1;
    int tot = 0;
    int zero = 0;
    // [l ,r)
    int l = 0, r = 0;
    while (r < n)
    {
        if (tot < n)
        {
            ans = max(ans, r - l - zero + 1);
            tot += arr[r];
            if (arr[r] == 0)
            {
                zero++;
            }
            r++;
            continue;
        }
        tot -= arr[l];
        if (arr[l] == 0)
        {
            zero--;
        }
        l++;
    }
    if(tot < n){
        ans = max(ans, r - l - zero + 1);
    }
    cout << ans << '\n';
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Problem C: Physical Education Lesson

  • 时间限制：1秒
  • 内存限制：256 MB

题目描述

　　现在有这样的一个填数规则，给定一个大于 $1$ 的正整数 $k$ ，数列从首项开始往后填的值依次为 $1,2,…,k,k-1,…,2,1,2,…k,…$ 。当 $k=2$ 时，数列为 $1,2,1,2$ ，当 $k=3$ 时，数列为 $1,2,3,2,1,2,3,…$。不难发现，这样的数列每经过 $2k-2$ 个元素之后会开始新一轮循环。
　　现在给定一个正整数 $n$ 和 正整数 $x$，数据保证 $x < n$，请问 $k$ 有多少种取值可以使得填数后的数列第 $n$ 个位置上的值是 $x$ ？

  • 输入描述
    　　第一行，一个正整数 $t(1\le t\le 100)$，表示接下来有 $t$ 组数据。
    　　接下来 $t$ 行，每一行包含两个正整数 $n,x(1\le x < n\le 10^9)$。
  • 输出描述
    　　对于每组数据，输出一行，每行一个整数，表示 $k$ 的合法取值个数。

解题思路

　　循环部分的长度是 $2k-2$ ，循环中元素的值是先增大再减小（ $k=2$ 时除外）。如果所求的位置 $n$ 处于增大过程中，那么就是当前循环中的第 $x$ 个元素。于是有 $n \bmod{(2k-2)} = x$ （式1），其中 $ \bmod $ 表示取模运算，即取余数，$5 \bmod 3 = 2$。同理，如果 $n$ 处于减小过程中，那么就是当前循环的第 $k + (k-1) - (x) + 1 = 2k-x$ 个元素（当 $k>2$ 时有效），于是有 $n \bmod (2k-2) = 2k-x$ （式2）。
　　根据式1，可以得到：
$$
\begin{aligned}
& n = \lambda (2k-2) + x \quad (其中 \lambda 是待定的正整数)\\
\\
\Rightarrow \quad & k = \frac{n-x}{2 \lambda} + 1 \quad
\end{aligned}
$$
　　我们可以尝试不同的 $\lambda$ 值，如果得出的 $k$ 是大于1的正整数，并且它不小于 $x$ (因为 $k < x$ 时，数列根本不会出现 $x$ 这个值)，那么该 $k$ 值就可以计入答案。而实际上，从另一个角度考虑，我们并不是要逐个尝试 $\lambda$ 的值，而是去找 $n-x$ 的偶数因子，找到它的所有偶数因子，也就代表找到了 $\lambda$ 。寻找一个数 $v$ 因子有一种时间复杂度 $O(\sqrt{v})$ 的算法。当我们找到一对整数 $a,b$ 满足 $a*b=n-x$ 时，如果 $a$ 是偶数且 $b + 1 \ge x$，那么 $b + 1$ 就可以作为一个有效的 $k$ 值计入统计。如果 $b$ 是偶数且 $a+1 \ge x$，那么也将$a+1$计入统计。
　　同样地，根据式2，可以得到：
$$
\begin{aligned}
& n = \lambda (2k-2) + (2k - x) \quad (其中 \lambda 是待定的非负整数)\\
\\
\Rightarrow \quad & k = \frac{n+x-2}{2(\lambda + 1)} + 1
\end{aligned}
$$
　　注，这里为什么 $\lambda$ 可以取 $0$ 而上面的不行，因为题目数据限制 $x < n$，因此必不可能处于第一个循环的上升阶段，但是可能处于第一个循环的下降阶段。然后和之前的方法一样，找 $n+x-2$的偶数因子然后计入统计（这里还要满足算出来的 $k$ 大于 $2$），两个式子计入的统计要进行去重处理，因为它们可能得出同样的 $k$ 值。最后看看一共有多少个 $k$ 值被统计，就得到答案了。

解题代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

set<int> ans;
int n, x;

// 将val除以其偶数因子之后能得到的值放入ans(如果其结果大于x-1)
void calculate(int val)
{
    if (val & 1)
    {
        return;
    }
    int right = sqrt(val);
    for (int i = 1; i <= right; i++)
    {
        if (val % i != 0)
        {
            continue;
        }
        int tmp = val / i;
        if (i % 2 == 0 && tmp >= x - 1)
        {
            ans.insert(tmp);
        }
        if (tmp % 2 == 0 && i >= x - 1)
        {
            ans.insert(i);
        }
    }
    if (1 >= x - 1)
    {
        ans.insert(1);
    }
}

void solve()
{
    ans.clear();
    cin >> n >> x;
    if ((n - x) % 2 != 0)
    {
        cout << "0\n";
        return;
    }
    calculate(n - x);
    calculate(n + x - 2);
    cout << ans.size() << '\n';
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Problem D: Lonely Mountain Dungeons

  • 时间限制：1秒
  • 内存限制：256 MB

题目描述

　　有许多不同种族的人员来组成军队，他们会被分为多支队伍，被分配到不同的队伍且属于同一种族的每一对成员都会使整体的战斗力增加 $b$ ，如果一共有 $k$ 支队伍，那么整体的战斗力要扣除 $(k-1) * x$ 。队伍的数量至少为 $1$ ，请问，在给定 $n$ 个种族以及每个种族的人员数量以及 $b,x$ 的值时，能够得到的最大整体战斗力是多少？

  • 输入描述
    　　第一行，一个正整数 $t(1\le t \le 2* 10 ^ 4)$ 表示接下来有 $t$ 组数据。
    　　每一组数据第一行，三个整数 $n,b,x(1\le n\le 2*10^5,1\le b\le 10^6,0\le x\le 10^9)$ ，分别表示种族个数、上文中的贡献值基数以及分队的惩罚值基数。
    　　每一组数据第二行， $n$ 个正整数 $c_1,c_2,…,c_n(1\le c_i \le 2*10^5)$ ，分别表示 $n$ 个种族各自的成员数量。
    　　数据保证 $c_1+c_2+…+c_n$ 不超过 $2*10^5$。
  • 输出描述
    　　对于每组测试数据，输出一行，包含一个整数，表示整体能达到的最大战斗力。

解题思路

　　整体战斗力由两个部分组成，一个是队员所产生的贡献，一个是分队所造成的惩罚。分得队伍越多整体扣除掉的战斗力就越多（当 $x \neq 0$ 时），那么惩罚部分自然是随着队伍数量增加而单调下降的（以对总体的贡献来看，因此取负值）。而队员所产生的贡献必然是随着队伍增加而增加，最好的情况就是所有人都单独成为一支队伍，不会存在同族人员分配到同一队伍的情况，这样队员所产生的贡献就最大化了。贡献+惩罚，一个上升一个下降，惩罚函数是线性函数，贡献函数不好分析，我解题时只是盲猜一手函数整体最复杂的情况下导函数也只是单调变化的，具体没有去验证。导函数单调的情况下整体战斗力曲线可能会是先上升后下降或者先下降后上升，也可能是一直上升或者一直下降，对于这四种情况都可以用三分法来快速缩小最值点范围，从而很快能够得到最大值。
　　决定采用三分法之后，接下来就是如何计算这两个部分的值了，当将其分为 $k$ 队时有：
$$
\begin{aligned}
& A = -(k-1)*x\\
\\
& B = \sum_{i=1}^{n}{[\frac{k*\alpha * (k-1) * \alpha}{2} + (k-1) * \alpha * \beta + \frac{\beta *(\beta - 1)}{2}]} * b \\
\\
& (其中 \alpha = \lfloor \frac{c_i}{k} \rfloor, \beta = c_i \bmod k)\\
\\
& \text{Result} = A + B
\end{aligned}
$$
　　然后采用三分法计算出 Result 可能的最大结果即可。

解题代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
int n, b, x;
int c[200005];

// 当分成k队时的总战斗力
long long calculate(int k)
{
    long long tot = 0;
    for (int i = 1; i <= n; ++i)
    {
        int alpha = c[i] / k;
        int beta = c[i] % k;
        tot += ((long long)alpha * (k - 1) * alpha * k / 2 + (long long)(k - 1) * alpha * beta + (long long)beta * (beta - 1) / 2) * b;
    }
    return tot - (long long)(k - 1) * x;
}

void solve()
{
    cin >> n >> b >> x;
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i];
    }
    // 三分法
    int l = 1, r = 200000;
    long long ans = 0;
    while (l + 3 < r)
    {
        int m1 = l + (r - l) / 3;
        int m2 = m1 + (r - l) / 3;

        long long tmp1 = calculate(m1);
        long long tmp2 = calculate(m2);
        if (tmp1 > tmp2)
        {
            r = m2;
        }
        else
        {
            l = m1;
        }
    }
    for (int i = l; i <= r; ++i)
    {
        ans = max(ans, calculate(i));
    }
    cout << ans << '\n';
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}
Codeforces
#编程
Codeforces Round 924 (Div.2)
https://mxx23.github.io/2024/02/14/Codeforces-Round-924-Div-2/
作者
mxx
发布于
2024年2月14日
许可协议