题解：CF1188C Array Beauty

AK_heaven · 2024-11-26 22:14:29 · 题解

Array Beauty

这道题目有两个关键的 trick：

• 1. 我们对数组进行了排序。为什么是对的？我们来思考一下，最后我们在选出 k 个数字以后我们计算贡献又会强行使得数组有序，原因很简单，因为 |b_i - b_j| 如果 b_i < b_j，那么绝对值就会使得 b_i 和 b_j 交换位置，而因为取 \min，所以值域相近的两个数字会在一起。所以这道题目不管如何，最后答案在计算时数组一定是有序的。这也说明了排序是正确的，并且对于解题有着一定帮助。
• 2. 我们直觉告诉我们，我们需要枚举每种可能的答案，因为答案值域很小，或者说根据结论，要使最小间隙最大，就必须要均匀分配间隙，也就是说对于数列 \{1, 2, 3, 4, 5, 6, 7\}，我们应当选择出类似 \{1, 3, 5, 7\}，这样才能做到最大，而不是 \{1, 2, 3, 7\}，看着最大的大，但是最小的也更小了。于是枚举答案可行。
• 3. 在枚举每种答案时，我们定义出了一个状态 F_{i, j, 0/1}，强制选择第 i 个数字，并且已经选了 j 个数字，有没有到达 \min 答案时的方案数，由于状态是两维的，转移枚举 i 又是 O(n) 的，考虑前缀和优化明显要考虑很多东西，例如容斥，等等。于是我们考虑 状态前缀化，然后转化为差分数组求出答案。则状态设为 F_{i, j} 表示前 i 个数字，且强制选 i，已经选了 j 个数字，且满足间隙大于等于枚举答案的方案数。

转移直接双指针 + 前缀和即可，我称之为 双前组合。

The code

#include<bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

using namespace std;

const int N = 1005 + 10;
const int mod = 998244353;

ll a[N], n, k, ans[1000001], F[1005][N], sum[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    cin >> n >> k;
    L(i, 1, n) cin >> a[i];
    sort(a+1, a+n+1);
    R(i, (a[n]-a[1])/(k-1), 0) {
        F[0][0] = sum[0][0] = 1;
        int p = 0;
        L(j, 1, n) {
            while(p < j && a[j] - a[p+1] >= i) p++;
            L(x, 0, k) {
                if(x) F[j][x] = sum[p][x-1];
                sum[j][x] = (sum[j-1][x] + F[j][x]) % mod;
            }
            ans[i] = (ans[i] + F[j][k]) % mod;
        }
//      cout << ans[i] << '\n';
    }
    ll Ans = 0;
    R(i, (a[n]-a[1])/(k-1), 0)
      Ans = (Ans + 1LL * (ans[i] - ans[i+1] + mod) % mod * i % mod) % mod;
    cout << Ans << '\n';
    return 0;
}