首页 > 其他 > 详细

洛谷10月月赛R2·浴谷八连测R3 -Chtholly-T1

时间:2017-10-22 10:33:56      阅读:308      评论:0      收藏:0      [点我收藏+]

原题链接:https://www.luogu.org/problem/show?pid=3932

月赛的时候只做了这一道题,而且暴力还写炸了。。。

 

其实,并不需要算很多的前缀和的

a[i]表示i位置的物品数

dis[i]表示每个储物点与一号的距离

sum表示前i个储物点(物品数*距离)的和

在x<l的时候,ans=Σ(dis[i]-dis[x])*a[i]=Σ(a[i]*dis[i]-a[i]*dis[x])=Σ(a[i]*dis[x])-dis[x]*Σ(a[i])

同理,x>r时,ans=dis[x]*Σ(a[i])-Σ(a[i]*dis[x]);

发现这两种公式明显可以用前缀和优化,a[i]和dis[i]在读入过程中算出他们的前缀和,sum[i]=a[i]*dis[i]

于是x<l时的计算式就变成了这样:ans=sum[r]-sum[l-1]+dis[x]*(a[r]-a[l-1])

而x>=l&&x<=r时,将区间分为[l,x-1][x+1,r]两部分分别计算即可

注意减法的取模问题,不论是暴力还是正解我都是挂在这个地方。

本题的减法很多,写个函数来处理减法的取模会方便很多

 

#include<cstdio>
const long long c=19260817;
void read(long long &y)
{
    y=0;char x=getchar();
    while(x<0||x>9) x=getchar();
    while(x>=0&&x<=9)
    {
        y=y*10+x-0;
        x=getchar();
    }
}
long long ch(long long s,long long t)
{
    return (s-t+c)%c;
}
long long sum[200005],dis[200005],a[200005],x,l,r,ans;
int n,m;
int main()
{
//    freopen("68.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=2;i<=n;i++)
    {
        read(dis[i]);
        dis[i]=(dis[i]+dis[i-1])%c;
    }
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        sum[i]=(sum[i-1]+(a[i]*dis[i])%c)%c;
        a[i]=(a[i]+a[i-1])%c;
    }
    for(int i=1;i<=m;i++)
    {
        ans=0;
        read(x);read(l);read(r);
        if(x<l) ans=ch(ch(sum[r],sum[l-1]),(dis[x]*ch(a[r],a[l-1]))%c);
        if(x>=l&&x<=r)
        {
            ans+=ch(ch(sum[r],sum[x]),(dis[x]*ch(a[r],a[x]))%c);
            ans+=ch((dis[x]*ch(a[x],a[l-1]))%c,ch(sum[x],sum[l-1]));
            ans%=c;
        }
        if(x>r) ans=ch((dis[x]*ch(a[r],a[l-1]))%c,ch(sum[r],sum[l-1]));
        printf("%lld\n",ans);
    }
    return 0;
}

 

洛谷10月月赛R2·浴谷八连测R3 -Chtholly-T1

原文:http://www.cnblogs.com/zeroform/p/7707825.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!