[典藏题记001]D. Frog Jumping(数论+图论+思维+暴力)

题目传送门 写这题脑细胞快死完了，看了大佬的题解又研究了半天。 简单讲一下我的做法： 这题可以小范围暴力，大范围找出规律。 $设h(i)为要到达点i的最小x$。 那么$ans=$$\sum _{i=0}^n(n-h(i)+1)(如果点i可以到达)$

然后有一个性质就是： 如果点i可达，那么一定满足：$i|gcd(a,b)$

即对于x>a+b,可以保证$h(i)=i$$,对于(i|gcd(a,b))的点$ 想象一个长度为$a+b+1$的线段，线段上的每一个点要么可以往左，要么可以往右，两者可以同时成立，但不可能都不成立。在总共经历了$a/(gcd(a,b))$次后跳和一定次数前跳后，一定可以到达点$i$. 这里用到了一个结论：就是两个互质的数a和b,($a+i\ast b(0<=i<a))$中的每个数对a的模数都不一样,然后其余$i$的取值根据鸽巢定理显然会造成重复。 因为取模时间复杂度很高，这里我们要用公式一次求出这部分的答案。

对于$x<=a+b$的部分暴力求解即可。我这里用了$dijkstra$堆优化来进行每个点的松弛操作。

#include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN 200005 ll a,b; ll n,m; int dis[MAXN]; int inf=2e9; struct node{ ll val; ll x; bool operator <(const node&a)const{ if(a.val==val) return x>a.x; return val>a.val; } }; inline int check(int x) { if(x>=0&&x<=m)return 1; return 0; } int main() { ll ans=0; priority_queue<struct node>q; scanf("%lld%lld%lld",&n,&a,&b); m=min(n,a+b); for(int i=1;i<=m;i++) dis[i]=inf; for(int i=0;i<=m;i+=a) { dis[i] = i; q.push({dis[i],i}); } while(!q.empty()) { node now = q.top(); q.pop(); ll x = now.x; if (check(x + a)) { if (max(dis[x ],(int)(x+a)) < dis[x+a]) { dis[x + a] = max(dis[x],(int)(x+a)); q.push({dis[x + a], x + a}); } } if (check(x - b)) { if (dis[x - b] > dis[x]) { dis[x - b] = dis[x]; q.push({dis[x - b], x - b}); } } } for(int i=0;i<=m;i++) if(dis[i]!=inf) ans+=(n-dis[i]+1); if(n>a+b) { ll g=__gcd(a,b); ll c=a+b+1; c=c-c%g+g-g*(c%g==0); ll d=n-n%g; ll sum=(n-d+1+n-c+1)*((d-c+g)/g)/2; ans+=sum; } cout<<ans<<endl; }