禅与园林艺术（garden）

上了大学之后，小W和小Z一起报了一门水课，在做作业时遇到了问题。

有一个长度为nn的数列{ai}，为一列树木的美观值。

现在有mm次询问，每次给出三个数l,r,p

询问对于所有的l≤l′≤r′≤r，(al′+al′+1+⋯+ar′) mod p的最小值。

输入

第一行为两个正整数nn和mm，表示数列的长度和询问的个数。

第二行为nn个整数，为a1∼ana1∼an。

接下来mm行，每行三个数l,r,pl,r,p，代表一次询问。

输出

对于每次询问，输出一行一个整数表示要求的结果。

solution

一道好题。

首先可以发现一个区间，如果长度>p 答案一定是0

因为不同的前缀最多p个。

那么小于p的暴力统计即可

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int n,m,a[110005],l,r,p,flag[105];

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    for(;m;m--){

        scanf("%d%d%d",&l,&r,&p);

        if(r-l>=p){puts("0");continue;}

        int sum=0,ans=1e9;

        for(int i=0;i<p;i++)flag[i]=0;

        flag[0]=1;

        for(int i=l;i<=r;i++){

            sum+=a[i];sum%=p;

            for(int j=sum;j>=0;j--)if(flag[j]){ans=min(ans,sum-j);break;}

            flag[sum]++;

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

禅与园林艺术（garden）

禅与园林艺术（garden）

输入

输出

最新文章

热门文章