题目传送门
引
大家都知道集合吧,原谅我喜欢说废话
解法
先钦定 A > B A>B A>B,
先把数排好序得到数组 a a a,考虑先解决集合 X X X的问题,
设计状态:
明显只有一维( n < = 1 e 5 n<=1e5 n<=1e5),所以有:
f i : X 集合最后放的是第 i 个数,对于前 i 个数来说 X , Y 都合法的方案数 f_i:X集合最后放的是第i个数,对于前i个数来说X,Y都合法的方案数 fi:X集合最后放的是第i个数,对于前i个数来说X,Y都合法的方案数
发现后 ( n − i ) (n-i) (n−i)个放在 Y Y Y的数我们未保证合法,但是我们之后特判一下就好了
状态转移
设 f i f_i fi由 f j f_j fj转移而来
考虑有哪些 j j j可以贡献:
1. i > j i>j i>j(废话)
2. a i − a j ≥ A a_i-a_j\ge A ai−aj≥A(差值大于 A A A)
3. max { a k − a k − 1 } ≥ B , k ∈ ( j , i ) \max\{a_k-a_{k-1}\}\ge B,k\in(j,i) max{ak−ak−1}≥B,k∈(j,i)(满足 Y Y Y集合的要求)
则: f i = ∑ f j f_i=\sum f_j fi=∑fj
code:
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7,N=1e5+7;
int n,l,r;
int f[N],sum[N];
ll A,B;
ll a[N];
int main(){scanf("%d%lld%lld",&n,&A,&B);if(A<B) swap(A,B);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for (int i=1;i+2<=n;++i)if (a[i+2]-a[i]<B) return puts("0"),0;a[0]=0;f[0]=sum[0]=1;for(int i=1;i<=n;i++) {while(a[i]-a[r+1]>=A) r++;if(l<=r) {f[i]=(1ll*f[i]+1ll*sum[r])%mod;if(l) f[i]=(1ll*f[i]-1ll*sum[l-1]+mod)%mod;}sum[i]=(1ll*sum[i-1]+1ll*f[i])%mod;if(a[i]-a[i-1]<B) l=i-1;}int ans=0;for(int i=n;~i;i--){ ans=(1ll *ans+1ll*f[i]) %mod;if(i<n && a[i+1]-a[i] <B) break;}printf("%d\n",ans);
}