传送门:

AtCoder

洛谷


题目大意:

N个互不相同的整数,其中第i小的整数为S_i。求将它们分成两个集合X,Y,并且X集合中任意两个数的差\geqslant AY集合中任意两个数的差\geqslant B的方案数。

解题思路:

考虑把序列拆成若干段,然后交替放入两个集合当中。

我们设f_i表示已经划分到第i位,且第i位划分到集合X当中的方案数,设g_i表示已经划分到第i位,且第i位划分到集合Y中的方案数。

我们考虑如何用f更新gg更新f同理)。显然,f_i可以转移到g_j当且仅当满足下列条件:

  • S_{j+1}-S_i \geqslant A
  • S_{i+1 \cdots j}中任意两个相邻的数的差\geqslant B

设区间[l_i,r_i]表示f_i能转移到g_i的范围,而显然l_i由条件1决定,r_i则由条件2决定,且显然对于任意l_i,l_j(i < j)l_j \geqslant l_ir_i同理。因此我们就可以在\rm DP的时候维护一下l_ir_i,每次转移就相当于把g_{l_i \cdots r_i}加上f_i。可以把g差分一下,也就是把g_{l_i}加上f_ig_{r_i+1}减去f_i,后面用g转移的时候求一下前缀和就好了。

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int maxn=1e5+10;
const ll  inf=0x7f7f7f7f7f7f7f7f;
int n,f[maxn],g[maxn];ll A,B,a[maxn];
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int main(){
    n=read();A=read();B=read();
    for(int i=1;i<=n;i++)a[i]=read();
    a[0]=-inf;a[n+1]=inf;f[0]=g[0]=1;
    int prea=0,preb=0,nowa=0,nowb=0;
    for(int i=1;i<=n;i++){
        if(a[i]-a[i-1]<A)prea=i-1;
        if(a[i]-a[i-1]<B)preb=i-1;
        while(nowa<i-1&&a[i+1]-a[nowa+1]>=A)nowa++;
        while(nowb<i-1&&a[i+1]-a[nowb+1]>=B)nowb++;
        if(nowa>=preb)g[i]=preb?(f[nowa]-f[preb-1]+mod)%mod:f[nowa];
        if(nowb>=prea)f[i]=prea?(g[nowb]-g[prea-1]+mod)%mod:g[nowb];
        f[i]=(f[i]+f[i-1])%mod;g[i]=(g[i]+g[i-1])%mod;
    }write(((((f[n]-f[n-1])%mod+g[n])%mod-g[n-1])%mod+mod)%mod);
    return 0;
}

发表评论