F. We Were Both Children - 题解
比赛与标签
比赛: Codeforces Round 886 (Div. 4) 标签: brute force, implementation, math, number theory 难度: *1300
题目大意喵~
你好呀，指挥官！今天我们来帮助 Mihai 和 Slavic 解决一个关于青蛙跳跳的问题，喵~
题目是这样的：有 n 只可爱的青蛙，还有 n 个可以放置陷阱的位置（坐标从 1 到 n）。每只青蛙 i 都有一个自己的跳跃长度 a_i。
所有青蛙都从坐标 0 开始，每秒钟，青蛙 i 都会向前跳 a_i 的距离。也就是说，它的跳跃路径是 0, a_i, 2*a_i, 3*a_i, ... 这样无限延伸下去的。
我们的任务是，只能选择一个坐标（在 1 到 n 之间）放置一个陷阱，希望能抓住尽可能多的青蛙。只要一只青蛙的跳跃路径经过了我们放置陷阱的坐标，它就会被抓住。
那么，我们到底应该把陷阱放在哪里，才能抓到最多的青蛙呢？这就是我们要找出的答案啦，的说！
解题思路喵~
这个问题看起来有点复杂，但只要我们换个角度思考，就会变得非常清晰哦，喵~
核心洞察：什么时候青蛙会被抓住？
首先，我们来分析一下一只青蛙被抓住的条件。一只跳跃长度为 a 的青蛙，它的落点会是 a, 2a, 3a, ...。如果我们把陷阱放在坐标 x，那么这只青蛙会被抓住，当且仅当 x 是 a 的一个倍数！比如说，跳跃长度为 3 的青蛙会落在 3, 6, 9, ... 等位置，所以陷阱放在这些位置都能抓住它。
朴素的想法（会超时的说~）
一个最直接的想法是：我们遍历所有可能的陷阱位置 x (从 1 到 n)。对于每一个 x，我们再遍历所有的 n 只青蛙，检查 x 是否是青蛙跳跃长度 a_i 的倍数（也就是 x % a_i == 0）。这样我们就能计算出在每个位置能抓住的青蛙数量，最后取最大值就好啦。
但是，n 最大可以到 2 * 10^5，如果用这种 O(n^2) 的方法，n*n 会非常大，肯定会超时的说 T_T。我们得想个更聪明的办法！
换个角度看问题！
既然“为每个陷阱位置找青蛙”太慢了，那我们不如反过来想：“为每种青蛙，更新它能被哪些陷阱抓住”！
一只跳跃长度为 k 的青蛙，它会为所有坐标是 k 的倍数的地方（k, 2k, 3k, ...）的陷阱贡献 1 的捕捉数。
这个思路是不是很像筛法求素数的感觉？喵~ 这就是我们的突破口！
优雅的“筛法”解题步骤：
统计青蛙数量：首先，我们根本不需要关心每只青蛙的编号，只需要知道有多少只青蛙具有相同的跳跃长度。我们可以用一个数组
freq来统计，freq[k]表示跳跃长度为k的青蛙有多少只。- 一个重要的优化：如果一只青蛙的跳跃长度
a_i > n，它的第一跳就已经超过了所有可能的陷阱位置（1 到n）。所以，这种青蛙是永远不可能被抓住的！我们直接忽略它们就好啦，只统计a_i <= n的青蛙。
- 一个重要的优化：如果一只青蛙的跳跃长度
计算每个陷阱的得分：我们再创建一个数组
traps，traps[j]用来记录在位置j放陷阱能抓住的青蛙总数。开始“筛”！：现在，我们遍历所有可能的跳跃长度
k（从 1 到n）。- 如果
freq[k] > 0，说明存在跳跃长度为k的青蛙。 - 这些
freq[k]只青蛙，会落在所有k的倍数点上。所以，我们遍历k的所有倍数j = k, 2k, 3k, ...，只要j <= n，我们就给traps[j]加上freq[k]。 traps[j] += freq[k];这行代码的意义就是：所有freq[k]只跳跃长度为k的青蛙，都对j这个陷阱位置做出了贡献。
- 如果
找到最终答案：当我们的“筛法”结束后，
traps数组里就存好了在每个位置（1 到n）放陷阱能抓住的青蛙数量。我们只需要找到这个数组里的最大值，就是我们的答案啦！
举个例子：n=5, 青蛙跳跃长度 [1, 2, 3, 4, 5]
freq数组:freq[1]=1, freq[2]=1, freq[3]=1, freq[4]=1, freq[5]=1。traps数组初始化为全 0。- 开始筛：
k=1:freq[1]=1。更新traps[1],traps[2],traps[3],traps[4],traps[5]都+=1。k=2:freq[2]=1。更新traps[2],traps[4]都+=1。k=3:freq[3]=1。更新traps[3]+=1。k=4:freq[4]=1。更新traps[4]+=1。k=5:freq[5]=1。更新traps[5]+=1。
- 最终
traps数组：traps[1] = 1traps[2] = 1+1 = 2traps[3] = 1+1 = 2traps[4] = 1+1+1 = 3traps[5] = 1+1 = 2
- 最大值是
3，所以答案就是 3，喵~ 和示例一样呢！
代码实现喵~
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
// Function to solve a single test case
void solve() {
int n;
std::cin >> n;
// 步骤 1: 统计各种跳跃长度的青蛙数量，喵~
// 我们只关心跳跃长度 a_i <= n 的青蛙，因为如果 a_i > n，
// 青蛙的第一跳就已经超过了所有可能的陷阱位置啦。
std::vector<int> freq(n + 1, 0);
for (int i = 0; i < n; ++i) {
int a;
std::cin >> a;
if (a <= n) {
freq[a]++;
}
}
// 步骤 2: 计算在每个可能的陷阱位置能抓住的青蛙数。
// 在位置 'j' 的陷阱能抓住跳跃长度为 'k' 的青蛙，当且仅当 'j' 是 'k' 的倍数。
// 我们可以用一个类似筛法的方法高效地计算这个值。
// 对于每一种存在的跳跃长度 'k'，我们把它对应的青蛙数量 (freq[k])
// 加到所有是 'k' 的倍数的陷阱位置上。
std::vector<int> traps(n + 1, 0);
for (int k = 1; k <= n; ++k) {
// 如果存在跳跃长度为 k 的青蛙
if (freq[k] > 0) {
// 就把这些青蛙的贡献加到所有 k 的倍数位置上
for (int j = k; j <= n; j += k) {
traps[j] += freq[k];
}
}
}
// 步骤 3: 找到能抓住的最多青蛙数量。
// 这就是 'traps' 数组在有效陷阱坐标 [1, n] 上的最大值啦。
// traps[0] 不是一个有效的陷阱位置，所以我们从 traps.begin() + 1 开始找。
// 题目保证 n >= 1，所以 traps 数组至少有大小为 2，这个操作是安全的。
int max_frogs = 0;
if (n > 0) { // 加上一个小小的保护，虽然题目保证n>=1
max_frogs = *std::max_element(traps.begin() + 1, traps.end());
}
std::cout << max_frogs << "\n";
}
int main() {
// 快速 I/O，让程序跑得飞快~
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}复杂度分析喵~
时间复杂度: O(N log N) 的说。 主要的计算量在那个双层循环。外层循环从
k=1到n，内层循环的步长是k。总的操作次数大约是n/1 + n/2 + n/3 + ... + n/n。这是一个调和级数，它的和约等于n * log(n)。所以整体时间复杂度是O(n log n)，对于n = 2 * 10^5来说是完全可以通过的！空间复杂度: O(N) 的说。 我们主要使用了两个大小为
n+1的向量freq和traps来存储数据。所以空间消耗是和n成正比的，也就是O(n)。
知识点与总结喵~
这道题真是太有趣啦，它教会了我们一些很棒的技巧！
逆向思维: 这是解题的关键！当正向求解（遍历陷阱）复杂度太高时，尝试从另一个角度（遍历青蛙/跳跃长度）来思考问题，往往能发现更高效的解法。
筛法思想: 本题的解法本质上是一种筛法。这种“枚举因子/倍数”的技巧在数论问题中非常常见，比如著名的埃拉托斯特尼筛法（Sieve of Eratosthenes）求素数。掌握这种思想，以后遇到类似的问题就能迎刃而解啦！
预处理与频率统计: 通过一个
freq数组预先统计好数据，可以避免在核心逻辑中重复计算，让代码更清晰、更高效。这也是算法竞赛中常用的一个基本技巧。边界条件: 注意到
a_i > n的青蛙可以直接忽略，这是一个非常重要的优化，它把无限的跳跃路径问题，限制在了有限的1到n范围内。
希望这篇题解能帮助到你，喵~ 只要多思考，多练习，再难的题目也会变得像毛线球一样好玩！加油哦！