题解：P11455 [USACO24DEC] Cowdepenence G

ZBH_799 · 2025-08-13 20:02:08 · 题解

题目分析

暴力

我们可以暴力枚举每个 x，然后把所有两两距离不超过 x 的同种的奶牛放进同一个友谊小组，即可得到答案。

优化

记 ans_x 表示两两距离不超过 x 时的答案。

通过观察样例可知，x 越大，不同的 ans_x 就越少，且 ans_x 单调不递增。因此对于当前枚举的 x，我们可以二分最后一个 ans_y 和 ans_x 相等的 y。但是当 x 很小时，不同的 ans_x 很多，怎么办呢？考虑根号分治。

设 B 表示根号分治的阈值：

当 x \le B 时暴力求解，时间复杂度为 O(nB)。

当 x \gt B 时采用上面的算法求解。因为不同的 ans_x 最多有 \frac{n}{B} 个，所以时间复杂度为 O(\frac{n}{B}n\log_2{n})。

由基本不等式，得时间复杂度为 O(nB+\frac{n}{B}\log_2{n}) \ge O(\sqrt{n^2\log_2{n}})，当且仅当 B=\sqrt{n\log_2{n}} 时等号成立。

AC code

#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
#define fr first
#define sc second
using ll=long long;
using db=double;
using i128=__int128;

const int N=1e5+5;
int n,a[N],b[N];
vector<int>pos[N];

int getans(int x,int y){
    int cnt=0,lst=-n;
    for(auto p:pos[x]) if(p-lst>y) cnt++,lst=p;
    return cnt;
}

void add(int l,int r,int v){b[l]+=v,b[r+1]-=v;}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]].push_back(i);
    }

    int B=sqrt(n*log2(n));
    for(int i=1;i<=n;i++){
        if(pos[i].empty()) continue;
        for(int j=1;j<=B;j++) add(j,j,getans(i,j));
        for(int j=B+1;j<=n;j++){
            int tmp=getans(i,j),l=j,r=n;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(getans(i,mid)>=tmp) l=mid;
                else r=mid-1;
            }
            add(j,l,tmp);j=l;
        }
    }

    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];
        cout<<b[i]<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--) solve();
    return 0;
}