CF1788D Moving Dots 题解

jiangtaizhe001 · 2023-03-13 21:05:29 · 题解

可能更好的阅读体验

题目传送门
题目翻译

题目解析

考虑怎样才能产生贡献，显然对于留下的相邻的 l,r，需要让 l 向右，r 向左即可产生 1 的贡献。
接下来就是考虑如何计算 l 向右 r 向左的方案数，其实就是计算左右两边最多可以留下的个数 x，方案数就是 2^x。
考虑把左右两边的分开计算。

我们发现，如果我们要让 l 向右，枚举右边的 l+1 到 n 作为 l 右边相邻的数，那么最左边可以留下的个数是单调不增的，所以枚举每一个 l，我们用双指针扫一次就好了。
另一边同理。时间复杂度就是 \Theta(n^2)。

int n,a[maxn],le[maxn][maxn],ri[maxn][maxn]; ll ans,pw[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    n=read(); int i,j,k; pw[0]=1;
    for(i=1;i<=n;i++) a[i]=read(),pw[i]=pw[i-1]*2%MOD;
    for(i=1;i<n;i++){
        k=i-1;
        for(j=i+1;j<=n;j++){
            while(a[i]-a[k]<=a[j]-a[i]&&k) k--;
            ri[i][j]=k;
        }
    }
    for(i=2;i<=n;i++){
        k=i+1;
        for(j=i-1;j>=1;j--){
            while(a[i]-a[j]>a[k]-a[i]&&k<=n) k++;
            le[i][j]=n-k+1;
        }
    }
    for(i=1;i<n;i++) for(j=i+1;j<=n;j++)
        ans+=pw[ri[i][j]+le[j][i]],ans%=MOD;
    print(ans); return 0;
}