专栏文章

题解：CF1188C Array Beauty

CCuSObin_BiNSO4
CF1188C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqal6wq
此快照首次捕获于
2025/12/04 01:39
3 个月前
此快照最后确认于
2025/12/04 01:39
3 个月前
查看原文
这题我的想法倒是挺一波三折的——从想到一个会 T 的方法到发现如何优化这个方法。
首先，我们需要发现这是一道传统的拆贡献题——如果一个长度为 kk 序列的美丽值是 xx，那么我们会对于所有正整数 tt，统计美丽值 ≥t\ge t 的序列数量并把它加到答案里。这样一个序列最终就会为答案刚刚好好贡献 xx。
第一步肯定要对序列排好序，由于仅要求是子序列，所以打乱顺序不会对答案产生影响。接下来问题转化为对于所有正整数 tt，求美丽值 ≥t\ge t 的长度为 kk 的序列数量，也即相邻两项差值均 ≥t\ge t 的长度为 kk 的序列数量。
这个比较简单：设 RiR_i 表示第一个位置 xx 使得 ax−ai≥ta_x-a_i\ge t（如果不存在则为 n+1n+1），那么我们可以初始设 Ri=iR_i=i，然后在升序遍历 tt 时可以对于每个位置从 RiR_i 继续往后扫描——直到扫到满足条件的为止，来以总时间复杂度 O(n2)O(n^2) 处理出来。
然后设 fi,jf_{i,j} 表示第一项为原序列的第 ii 个位置且序列长度为 jj 的序列数量，则有：
fi,1=1,∀2≤j≤k,fi,j=∑y=Rinfy,j−1f_{i,1}=1,\forall 2\le j\le k,f_{i,j}=\sum_{y=R_i}^n f_{y,j-1}
明显，我们倒着处理 dp 值时可以使用后缀和优化。于是对于单个 tt，它的时间复杂度就是 O(nk)O(nk)。
最后我们想想我们要把 tt 处理到哪？明显，tt 最多处理到值域上界 Amax⁡=105A_{\max}=10^5，但是这样时间复杂度就是 O(Amax⁡nk+n2)O(A_{\max}nk+n^2)，爆炸了。
但是，tt 真的要处理到 Amax⁡A_{\max} 吗？做到这里的时候我又灵光一现：如果 (k−1)t>Amax⁡(k-1)t>A_{\max}，那么这个序列的第一项和最后一项差值便会大于 Amax⁡A_{\max}，这就矛盾了！
这样我们 tt 处理到 ⌊Amax⁡k−1⌋\lfloor\frac{A_{\max}}{k-1}\rfloor 即可！时间复杂度即为 O(Amax⁡k−1nk+n2)=O(Amax⁡n+n2)O(\frac{A_{\max}}{k-1}nk+n^2)=O(A_{\max}n+n^2)，成功通过。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;

int n,K,a[1005],nxt[1005],dp[1005][1005],pres[1005][1005],ans;
const int modp=998244353;

int main(){
	cin>>n>>K;for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);for(int i=1;i<=n;i++)nxt[i]=i+1;
	for(int o=1;o<=100000/(K-1);o++){
		for(int i=1;i<=n;i++)while(nxt[i]<=n&&a[nxt[i]]-a[i]<o)nxt[i]++;
		for(int i=n;i>=1;i--){
			dp[i][1]=1;for(int j=2;j<=K;j++)dp[i][j]=pres[nxt[i]][j-1];
			for(int j=1;j<=K;j++)pres[i][j]=(pres[i+1][j]+dp[i][j])%modp;
		}
		ans=(ans+pres[1][K])%modp;
	}
	cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...