题解 CF1850F We Were Both Children

· · 题解

Update on 2023/7/23 18:52：经管理员 @CSP_Sept 提醒，修改整除符号表示。

题意

给定 n 个整数 a，你需要找到一个整数 x \in [1,n] 使得 \sum\limits_{i=1}^n[a_i \mid x] 最大。

分析

这一道题根本就不需要筛因数！

其实只要你稍微优化一下暴力，这个是可以过的。

如果你不优化就会像我的同学一样被 Hack。

我们可以用一个 std::map 存储有多少只距离为 x 的青蛙。

设一个 b 数组表示 b_i 为青蛙会经过 i 这个位置的只数。

然后对于每一个 x\mid i，只需要每一次加距离为 x 青蛙的只数就可以了，如果每一次遍历都只加一个会显得十分浪费。

还有一个小优化就是特判 a_i=1，这种情况可以特殊处理，因为它对于每一个位置都是可行的，所以单独讨论。

最坏情况下，时间复杂度是 O(n\sum\limits_{i=1}^n\dfrac{1}{i}) \approx O(n \log n)，使用 std::map 维护需要再乘一个 \log n，所以总的时间复杂度为 O(n \log^2 n)。

代码

//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<utility>
int n,a[200002],b[200002];
std::map<int,int> M;
void solve(){
    M.clear();
    scanf("%d",&n);
    memset(b,0,sizeof(int)*(n+1));//清空数组，并不需要清空全部。
    int s=0;//为 1 的个数。
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==1) ++s;//特判为 1 的情况。
        else if(a[i]<=n) ++M[a[i]];//如果大于 n 则不需要考虑。
    }
    for(std::pair<int,int> it:M){
        for(int i=it.first;i<=n;i+=it.first) b[i]+=it.second;//暴力加答案。
    }
    int ans=s;
    for(int i=1;i<=n;i++)ans=std::max(ans,b[i]+s);//当前位置加一的个数即为当前答案，然后取最大值。
    printf("%d\n",ans);
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}