官方题解｜排位赛#4题解Q5、Q6

AC君

2024-02-18 13:22:56

发布于：浙江

126阅读

0回复

0点赞

官方题解｜排位赛#4题解Q5、Q6

前情提要：排位赛#4题解Q1-Q4
赛事地址：排位赛#4
直播预告：1月20日（周六）下午4点-6点 B站ACGO官方账号排位赛#4复盘（欢迎观看大型翻车现场）
直播主讲：アイドル老师：小码王C++ 信奥算法讲师，3年C++算法竞赛教学经验，第47届国际大学生程序设计竞赛亚洲区域赛铜奖。

Q5 排列

提示

不考虑整齐度，如何交换元素让所有元素归位，能够使得交换的次数最少？

题目解析

如果不考虑整齐度，交换元素让所有元素归位，我们可以考虑让每个元素直接回到他的位置试试看。以样例 [2, 1, 4, 5, 3] 为例，为了方便我们令 t 为待交换元素（搁置元素）。
令 t = 2，放回到它的位置 i = 2，此时 a[2] = 1，把 1 设为搁置元素。
此时 t = 1，数组为 [2, 2, 4, 5, 3]；
然后我们再将搁置元素 t = 1 放到 i = 1，此时数组为 [1, 2, 4, 5, 3]，下标为 1, 2 的元素已归位。
同理我们可以使用以上方法使剩余元素归位。

不难发现，每一轮交换总是从一个位置 $i$ 开始，然后回到 $i$ 结束，形成一个环。

每个元素只会与其所在环内的元素交换，且让一个有 $m$ 个元素的环的所有元素归位，只需要 $m-1$ 次交换。

接着我们考虑交换次数受限制的情况。比如对于一个大小为 $m$ 的环，我们可以交换元素的次数只有 $k(1 \le k < m - 1)$ 次，那么对于这个大小为 $m$ 的环，我们最多只能使 $k$ 个元素归位。

由于题目中我们让每个元素归位获得的 整齐度 是不一样的，所以对于一个环我们如果只能归位有限个元素，显然应该选择优先归位权重（ 整齐度 ）更大的元素。所以归位一个环内的元素时，可以将环内元素按照权重从大到小排序，优先归位权重更大的元素。

接下来问题便可以转化成：数组中不在自己位置上的元素形成 $n$ 个环，对于每个环可以选择归位若干个元素 $b_i (1 \le i \le n)$ ，限制为 $b_1 + b_2 + \cdots + b_n \le k$ 。
那么由于每个元素归位的权重不同，对于每个大小为 $m$ 的环，实际上我们只需要关注在环中选择归位元素的数量即可，不需要枚举环中具体归位哪些元素。即选择 环中归位的元素数量 即可。

那么这里问题便转化为了一个 分组背包 问题：
有 $n$ 个环，最多操作 $k$ 次。
每个环可以选择归位元素的数量。
环 $i$ 选择归位 $j$ 个元素的操作次数为

$v_{ij} = \begin{cases} j - 1, &\text{if j = m}\\ j, &\text{if j < m} \end{cases}$

获得的 整齐度 为 $sum_{ij}$ 即环 $i$ 中权重最大的 $j$ 个元素的 整齐度 之和。
求解每个环选择归位多少个元素，操作次数总和不超过 $k$ ，且获得的 整齐度 最大。

对于本题的答案就是分组背包处理完后的答案加上已经在位置上的元素的 整齐度 之和。

AC代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> a(n), v(n);
    for (auto &x : a) cin >> x, --x;
    for (auto &x : v) cin >> x;
    vector<i64> dp(k+1);
    i64 res = 0;
    vector<int> st(n);
    for (int lo = 0; lo < n; ++lo) {
        // 位置正确直接累加整齐度
        if (a[lo] == lo) {
            res += v[lo];
            continue;
        }
        // 已处理过的环内元素跳过
        if (st[lo] == 1) continue;
        // 处理环内元素
        vector<i64> sum;
        int hi = lo;
        do {
            sum.push_back(v[hi]);
            st[hi] = 1;
            hi = a[hi];
        } while (hi != lo);
        // 从大到小排序并求前缀和
        sort(sum.rbegin(), sum.rend());
        partial_sum(begin(sum), end(sum), begin(sum));
        // 分组背包
        int m = sum.size();
        for (int i = k; i > 0; --i) {
            for (int j = min(m - 1, i); j > 0; --j)
                if (j == m - 1)
                    dp[i] = max(dp[i], dp[i-j] + sum[j]);
                else
                    dp[i] = max(dp[i], dp[i-j] + sum[j-1]);
        }
    }
    cout << res + dp[k] << '\n';
    return 0;
}

复杂度分析

找出整个数组的所有环的时间复杂度为 $O(n)$ 。
对于分组背包的问题，时间复杂度为 所有物品数量的总和 $\times$ 背包容量，本题 所有物品数量的总和 显然不超过 $n$ ，总的时间复杂度为 $O(n \cdot k)$ 。

Q6 相似排列

提示1

设 $p[x]$ 是 $x$ 在排列 $a$ 中的位置（下标）。

由于 $MEX([a_{p[0]}])=1$ ，所以 $0$ 在排列 $b$ 中的位置只能是 $p[0]$ 。

提示2

$1$ 可以放在排列 $b$ 中的什么位置？

提示3

假设 $p[0] < p[1]$ ；
如果 $p[2] < p[0]$ ， $2$ 可以放在排列 $b$ 中的哪些位置？
如果 $p[2] > p[1]$ ， $2$ 可以放在排列 $b$ 中的哪些位置？
如果 $p[0] < p[2] < p[1]$ ， $2$ 可以放在排列 $b$ 中的哪些位置？

题目解析

令 $p[x]$ 为 $x$ 在排列 $a$ 中的位置（下标）。

由于 $MEX([a_{p[0]}])=1$ ，所以 $0$ 在排列 $b$ 中的位置只能是 $p[0]$ 。

接下来讨论 $1$ 可以放在排列 $b$ 中的位置。

假设 $p[0] < p[1]$ ，那么
对于所有区间 $[l, r](l \le p[0] < p[1] \le r)$ ，有 $MEX([b_l, \ldots, b_r]) > 1$ ;
对于其他区间 $[l, r](p[0] \le l \le r \le p[1])$ ，有 $MEX([b_l, \ldots, b_r]) \le 1$ 。

所以， $1$ 必然只能放在 $p[1]$ 这个位置。

我们以一个更具体的例子来说明：

假设 $p[0] < p[1]$ ，不难发现以下性质:
A. 对于区间 $[p[0], p[1]]$ , 有 $MEX([b_{p[0]}, \ldots, b_{p[1]}]) > 1$ ；
B. 对于区间 $[p[0], x](p[0] < x < p[1])$ ，有 $MEX([b_{p[0]}, \ldots, b_{x}]) = 1$ 。
若 $b_{p[1]} \neq 1$ ，令 $x$ 为 $1$ 在 $b$ 中的位置，考虑以下两种情况：
1. $x < p[0]$ 或 $p[1] < x$ :
此时 $x$ 在区间 $[p[0], p[1]]$ 外，此时 $MEX([b_{p[0]}, \ldots, b_{p[1]}]) = 1$ 与 $A$ 矛盾。
2. $p[0] < x < p[1]$ :
此时 $x$ 在区间 $[p[0], p[1]]$ 内，此时 $MEX(b_{p[0]}, \ldots, b_{x}) > 1$ 与 $B$ 矛盾。

将区间 $[p[0], p[1]]$ 作为当前区间 $[l, r]$ 并继续考虑 $2$ 可以放在排列 $b$ 中的位置。

若 $p[2] \in [l, r]$ ，那么
对于所有区间 $[x, y](x \le l < r \le y)$ ，有 $MEX([b_x, \ldots, b_y]) > 2$ ；
对于其他区间 $[x, y](l < x \le y < r )$ ，有 $MEX([b_x, \ldots, b_y]) \le 2$ 。

只要 $2$ 在区间 $[l, r]$ 内就能够满足以上两个条件，所以 $2$ 可以放在区间 $[l, r]$ 内的任何一个位置（除了已经被占用的位置），所以当 $p[2] \in [l, r]$ 时， $2$ 可以放置的位置数量为 $(r - l + 1) - 2$ 。

否则， $2$ 只能放在排列 $b$ 中的 $p[2]$ 这个位置上。并且当前区间被扩展至包含 $p[2]$ ，变为 $[p[2], r]$ 或 $[l, p[2]]$ 。

容易看出后续的数字 $3, 4, \ldots, n - 1$ 都可以这样处理。

令 $k$ 为当前处理的数字，若 $k \in [l, r]$ ，说明 $k$ 可以放置的位置数量为 $(r - l + 1) - k$ 。否则将当前区间扩展至包含 $p[k]$ 。

最终问题的答案就是每个元素可以放置位置数量的乘积。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> a(n), b(n);
        for (auto &x : a) cin >> x;
        for (int i = 0; i < n; ++i)
            b[a[i]] = i;
        int l = b[0], r = b[0], res = 1;
        for (int i = 1; i < n; ++i) {
            if (b[i] < l)
                l = b[i];
            else if (b[i] > r)
                r = b[i];
            else
                res = res * (r - l + 1LL - i) % MOD;
        }
        cout << res << '\n';
    }
    return 0;
}