蒟蒻的小窝

蒟蒻的小窝

题解 P6434 【「EZEC-1」甜品】

posted on 2020-08-21 20:59:07 | under 题解 |

首先先预处理,把每个甜品按照从小到大排序(因为方案总数只考虑 $k$ 种甜品的搭配,不考虑排列顺序),然后找出吃每个甜品所能吃的下一种甜品的左端点和右端点。但普通的处理时间复杂度就是 $n^2$ 的,必须要把时间复杂度降下来。我们发现,把甜品排完序后,每个甜品的后一个能吃的甜品都是连续并且递增的,而且下一个甜品所能吃的后一个甜品只需要在前一个的基础上左端点往右缩进,右端点往右推,果断用单调队列(如果只看出连续而没发现可以在上一次的基础上往右推的话就只能用二分,但这是 $O(nlogn)$ 的还是会超时【无奈】【摊手】)。然后开一个数组 $f[j][i]$,表示在吃了第 $j$ 个的时候吃到 $i$,所能吃到的最大值。有了这个基础,那我们就从右往左推,造出前缀和之后用容斥就能 $O(1)$ 算出这个值,最后累加一下 $f[k][i](i是1---n)$ 就是第一问的答案,时间复杂度算上预处理近似是 $O(n*k)$。

对于第二问,我们说,只要这个甜品往右吃能吃到 $k$ 个,那么它所累加的值就对比在它左边的大!那么只需从右往左找,只要有一个甜品能吃 $k$ 个,那么答案就累加上它,再把 $k--$,继续从n开始往左枚举, $k=0$ 时就输出答案就ok了,第二问的时间复杂度也近似是 $O(n*k)$。

Code:

#include<bits/stdc++.h>
using namespace std;
const int TT=1000000007;
struct ZS{
    int l,r;
}b[2000002];
int n,k,l,r,ans,lsth,lstt;
int hed,til;
int a[2000002],maxn[2000002];
int s[10][2000002];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
int main(){
    n=read();k=read();l=read();r=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+1+n);k--;
    for(int i=1;i<=n;i++){
        while(hed<=n+1&&a[hed]<a[i]*l)
        hed++;
        while(til<=n&&a[til+1]<=a[i]*r)
        til++;til=min(til,n);
        if(hed<=n)b[i].l=hed,b[i].r=til;
    }
    for(int i=1;i<=n;i++)s[0][i]=1;
    for(int j=1;j<=k;j++){
        for(int i=1;i<=n;i++)s[j-1][i]=(s[j-1][i]+s[j-1][i-1])%TT;
        for(int i=1;i<=n;i++)s[j][i]=(s[j-1][b[i].r]-s[j-1][b[i].l==0?-1:max(i,b[i].l-1)]+TT)%TT;
    }
    for(int i=1;i<=n;i++)ans=(ans+s[k][i])%TT;
    printf("%d\n",ans);
    if(!ans){printf("0\n");return 0;}ans=0;
    for(int i=n;i>=1;i--)if(s[k][i]){
        int now=i;ans+=a[i];
        for(int j=k-1;j>=0;j--){
            for(int g=b[now].r;g>=b[now].l;g--)
            if(s[j][g]-s[j][g-1]){ans=(ans+a[g])%TT;now=g;break;}
        }
        break;
    }
    printf("%d\n",ans);
    return 0;
}