https://codeforces.com/contest/1146/problem/D

题意

有一只青蛙,一开始在0位置上,每次可以向前跳a,或者向后跳b,定义\(f(x)\)为青蛙在不跳出区间[0,x]能跳到多少个不同的位置上,计算\(\sum^m_{i=0}f(i)\)

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

  • 计算点贡献,计算有多少个区间包含i即i的贡献,设d[i]为走到i经过的最大的点,假如i点能走到,那么包含他的区间就是[d[i],d[i]+1,d[i]+2,...,n]
  • 裴蜀定理有\(ax+by=gcd(a,b)\),即一定能走到gcd(a,b)的倍数上
  • 假如i>a+b,则d[i]=i(关键)
  • 所以对于\(i<a+b\)的点,用最短路计算出d[i],暴力统计区间
  • 在a+b区间内,最贪心的走法是能向后走就像后走,这样能把该走的点走完

代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int inf=1e9;
ll n;
int a,b;
int d[500005],vi[500005];
struct N{
    int x,d;
    N(int x=0,int d=0):x(x),d(d){}
    bool operator <(const N& rhs)const{
        return d>rhs.d;        //优先队列反着来
    }
};
void dij(int n){
    priority_queue<N>Q;
    for(int i=0;i<=n;i++){d[i]=inf;vi[i]=0;}
    d[0]=0;
    Q.push(N(0,0));
    while(!Q.empty()){
        N u=Q.top();Q.pop();
        if(vi[u.x])continue;
        vi[u.x]=1;
        if(u.x-b>=0&&d[u.x-b]>d[u.x]){
            d[u.x-b]=d[u.x];
            Q.push(N(u.x-b,d[u.x-b]));
        }
        if(u.x+a<=n&&max(u.x+a,d[u.x])<d[u.x+a]){
            d[u.x+a]=max(u.x+a,d[u.x]);
            Q.push(N(u.x+a,d[u.x+a]));
        }
    }
}
int main(){
    cin>>n>>a>>b;
    ll g=__gcd(a,b);
    dij(a+b);
    ll ans=0;
    for(int i=0;i<=a+b;i++)ans+=max(0ll,n-d[i]+1);
    ll cnt=n/g-(a+b)/g;
    if(cnt>0){
        ll tp=1ll*(1+n)*cnt;
        ll l,r;
        for(r=n;r>a+b;r--)if(r%g==0)break;
        for(l=a+b+1;l<=n;l++)if(l%g==0)break;
        ans+=tp-1ll*(l+r)*cnt/2;
    }
    cout<<ans;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄