F. We Were Both Children
题意:n只青蛙初始在0处,每只青蛙都有一个a[i]表示青蛙每次能跳a[i],我们可以在1~n的位置处放置一个陷阱,每只青蛙经过陷阱后会掉进陷阱,求最多能捕获多少只青蛙。
思路:我们观察a[i]的范围很大是1e9,但是只有n以内的数据是有效的,其他数据都是无效的,所以直接舍去,然后统计有效数字出现的次数,对于i,他会经过i * 1, i * 2, i * 3, …,我们直接去枚举这些出现过的数,然后给n范围以内的这些他们经过的数上面加上,当前i的数量,因为每次跳i步的青蛙可能不知一个
也就是说我们枚举的范围是n + n/+ n/3 + n/4 + … + 1这个复杂度就是调和级数。
代码很简单如下:
#include
#define LL long long
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
LL a[N], n;
void solve()
{
cin >> n;
map<int, int>mp, cnt;
for(int i = 1; i <= n; ++ i)
{
int xx; cin >> xx;
if(xx > n) continue;
a[i] = xx;
mp[xx] ++;
}
for(auto item : mp)
{
int k = item.x;
for(int j = 1; j <= n / k; ++ j)
cnt[j * k] += mp[k];
}
int ans = 0;
for(auto item : cnt)
ans = max(item.y, ans);
cout << ans << endl;
}
int main()
{
int t;
// freopen("1.in", "r", stdin);
cin >> t;
while(t --) solve();
return 0;
}