2019 ICPC Asia Nanchang Regional E Eating Plan 离散化+前缀和

题意：

给你n个盘子，这n个盘子里面分别装着1！到n！重量的食物，对于每一个询问k，找出一个最短的区间，使得区间和 mod 998857459 大于或等于k

盘子数量 n<=1e5 询问次数 m<=1e4

题解：

坑点在于此题模数998857459=4*773*2803 是个合数，因此任何a>=2803 a！=0

因此，只需考虑非0的盘子作为端点，暴力枚举$(max(n,2802))^2$个区间。

我使用的方式是记录阶乘取模非0节点的值和位置，然后求前缀和

再枚举左右端点，记录区间和取模和区间长度

再将区间按照区间和从小到大排序

再把值从小到大的区间从后往前，维护取得大于等于该值所需区间长度的最小值。

询问时在排好序的区间数组上lower_bound，返回该点记录的最小区间长度.

#include<iostream>

#include<algorithm>

#include<vector>

#define MOD 998857459

#define INF 0x3f3f3f3f

using namespace std;

long long poww[];

long long res[];

//long long a[100005];

struct Array{

    long long val;

    long long index;

    long long sum;

}a[];

long long asiz=;

struct Ans{

    long long sum;

    long long len;

    long long minlen;

    friend bool operator < (const Ans &a,const Ans &b){

        return a.sum<b.sum;

    }

    friend bool operator > (const Ans &a,const Ans &b){

        return a.sum>b.sum;

    }

}ans[];

long long anssiz=;

//vector<Ans> ans;

int main(){

    poww[]=;

    for(long long i=;i<=;i++){

        poww[i]=1LL*poww[i-]*i%MOD;

        //printf("%lld\n",poww[i]);

    }

    long long n,m;

    scanf("%lld %lld",&n,&m);

    for(long long i=;i<=n;i++){

        long long t;

        scanf("%lld",&t);

        if(t<=){

            asiz++;

            a[asiz].index=i;

            a[asiz].val=poww[t];

        }

    }

    //a[1].sum=a[1].val;

    for(long long i=;i<=asiz;i++){

        a[i].sum=a[i-].sum+a[i].val;

    }

    //memset(res,INF,sizeof res);

    for(long long i=;i<=asiz;i++){

        for(long long j=i;j<=asiz;j++){

            //ans.push_back(aa);

            anssiz++;

            ans[anssiz].len=a[j].index-a[i].index+;

            ans[anssiz].sum=(a[j].sum-a[i-].sum)%MOD;

            //res[j-i+1]=max(res[j-i+1],a[j].sum-a[i-1].sum);

        }

    }

    sort(ans+,ans++anssiz);

    ans[anssiz].minlen=ans[anssiz].len;

    for(long long i=anssiz-;i>=;i--){

        ans[i].minlen=min(ans[i+].minlen,ans[i].len);

        //printf("*%lld %lld\n",ans[i].sum,ans[i].minlen);

    }

    //for(int i=1;i<=anssiz;i++){

        //printf("*%lld %lld %lld\n",ans[i].sum,ans[i].len,ans[i].minlen);

    //}

    for(long long i=;i<=m;i++){

        long long k;

        scanf("%lld",&k);

        Ans tmp;

        tmp.sum=k;

        long long aa=lower_bound(ans+,ans++anssiz,tmp)-ans;

        //printf("%lld\n",aa);

        if(aa==anssiz+)printf("-1\n");

        else printf("%lld\n",ans[aa].minlen);

    }

    return ;

}

巴特西

2019 ICPC Asia Nanchang Regional E Eating Plan 离散化+前缀和

最新文章

热门文章