题解 CF1146D 【Frog Jumping】

2019-04-22 09:14:21


应该可以想到一个O(n) 的做法 求出 $\sum_{i=1}^{n}f(i)$

就是bfs,每次加入一个点i是时候,判断之前 i-a 是否之前可以到达

如果可以,那么点i可以到达,并用点i bfs扩展一波即可

这样每个点最多被遍历1次,所以是O(n)的


然后我们打表找规律,发现当 n > 2*max(a,b)的时候,f(n) = $\frac{n}{gcd(a,b)}+1$

然后在 $i <= 2*max(a,b)$ 时暴力做,否则用规律就行了

比赛的时候其实我找到规律了,但是忘记了小数据可以暴力做这种操作,一直推式子

直到最后10min我才做出来这题。我太菜了

不过总算让 ChthollyTree 上紫了


#include<bits/stdc++.h>
using namespace std;

#define int long long
#define LL long long
#define INF (LL)(0x3f3f3f3f)*(LL)0x3f3f3f3f
#define MAXN 300005 

LL n,m;
LL a,b,x;
LL ans = 0;
LL an[MAXN];
bool f[MAXN];
queue<int>q;

LL gcd(LL x,LL y) {
    if(x%y != 0) return gcd(y,x%y);
    return y; 
} 

LL orz(LL x) {
    return x*(x+1)>>1;
}

LL sqz(LL x,LL mo)
{
    if(x % mo == 0) return x/mo;
    else return x/mo+1;
}

LL stO(LL n) {
    return orz((n+1)/x)*x + ((n+1)%x)*(sqz(n+1,x));
}

int bfs(int i)
{
    int ans = 0;
    f[0] = 1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        ans ++;
        if(x+a <= i && !f[x+a]) {
            f[x+a] = 1;
            q.push(x+a);
        }
        if(x-b >= 0 && !f[x-b]) {
            f[x-b] = 1;
            q.push(x-b); 
        }
    }
    return ans;
}

signed main()
{
    cin >> n >> a >> b;

    q.push(0);
    an[0] = 1;
    f[0] = 1;
    bfs(0);
    for(int i = 1; i <= max(a,b)*2; i ++) {
        if(i-a >= 0 &&f[i-a]) {
            f[i] = 1;
            q.push(i);
            an[i] = an[i-1]+bfs(i);
        } else {
            an[i] = an[i-1];
        }
    }

    x = gcd(a,b); 
    if(a > b)
      swap(a,b);

        for(int i = 0; i < min(n+1,2*b); i ++) { 
            ans += an[i];
        }
        if(n >= 2*b)
            ans += stO(n) - stO(2*b-1);     
    }
    cout<<ans;
    return 0;
 }