题解：CF1188C Array Beauty

Array Beauty

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

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

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

The code

CPP

#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;
}

题解：CF1188C Array Beauty

文章操作

Array Beauty

相关推荐

评论

题解：CF1188C Array Beauty