#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int inf=0x3f3f3f3f; int L,S,T,M; long long pos[5000000]; long long f[5000000]; long long a[5000000]; void calc(){ long long ANS=0; for(long long i=1;i<=M;i++){ if(pos[i]%S==0) ANS++; } cout<<ANS; return ; } int main(){ }

首先这道题的状态转移方程十分好推，即: 但是这道题的数据却是1e9的，开数组肯定爆。 那么我们就想到了离散化。 即mod 2520–lcm(1,…,10)，因此从一个点出发，无论青蛙能跳的距离是多少，它一定可以到达距离2520处。所以在前方2520没有石头时，可以将当前点向后移2520或者将后面的点向前移2520。 AC代码

显然是dp，空的地方就是随便走就行了，完全可以不用老老实实的去看，我们可以把路径压缩，更简单地说就是如果后面的一个石头与前面的一个石头距离太远，我们可以把后面一个石头推到前一个石头附近，至于这个量是多少呢，可以用1000。