We Were Both Children

问题建模

给定n个青蛙每次跳跃的距离，青蛙从0点开始向右跳跳，问1~n中最多青蛙到达的点，青蛙到达的数量为多少。

问题分析

1.分析到达的点与跳跃距离的关系

对于每一个点，能到达该点的青蛙其跳跃距离必然为该点距离的因数，则我们只需要遍历每个点，计算该点有多少个跳跃距离为其因数的青蛙即可。

2.方法1倍数法累计每个点所能达到的青蛙数

对于1~n的每个距离，考虑该距离的倍数所能到达的点，然后该点累加上该距离对应的青蛙数

代码

#include<bits/stdc++.h>#define x first
#define y second
#define C(i) str[0][i]!=str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N =2e5+10,INF=0x3f3f3f3f;
int cnt[N];void solve() {  int n;cin >>n;memset(cnt,0,sizeof(int)*(n+1));for(int i=0;i<n;i++){int x;scanf("%d",&x);if(x<=n)    cnt[x]++;///统计距离为x小于等于n青蛙的个数}for(int i=n;i>=1;i--){///倒序考虑每个距离为倍数的点，不倒序会多加for(int j=2*i;j<=n;j+=i){cnt[j]+=cnt[i];}}cout <<*max_element(cnt+1,cnt+n+1)<<"\n";
}   int main() {int t = 1;cin >> t;while (t--) solve();return 0;
}

方法2试除法累计每个点能到达的青蛙数

对于1~n的每个点，累加所有跳跃距离为其因数的青蛙数

代码

#include<bits/stdc++.h>#define x first
#define y second
#define C(i) str[0][i]!=str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N =2e5+10,INF=0x3f3f3f3f;
int cnt[N];void solve() {  int n;cin >>n;memset(cnt,0,sizeof(int)*(n+1));for(int i=0;i<n;i++){int x;scanf("%d",&x);if(x<=n)    cnt[x]++;}for(int i=n;i>=1;i--){for(int j=1;j<=i/j;j++){///试除法累加能到达点i的每个跳跃距离为其因数的青蛙数  if(i%j==0){if(i!=j)    cnt[i]+=cnt[j];if(i!=i/j&&j!=i/j)  cnt[i]+=cnt[i/j];    }}}cout <<*max_element(cnt+1,cnt+1+n)<<"\n";
}   int main() {int t = 1;cin >> t;while (t--) solve();return 0;
}