专栏文章

题解：P11455 [USACO24DEC] Cowdepenence G

ZZBH_799
P11455题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioco4ps
此快照首次捕获于
2025/12/02 17:02
3 个月前
此快照最后确认于
2025/12/02 17:02
3 个月前
查看原文

题目分析

暴力

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

优化

记 ansxans_x 表示两两距离不超过 xx 时的答案。
通过观察样例可知，xx 越大，不同的 ansxans_x 就越少，且 ansxans_x 单调不递增。因此对于当前枚举的 xx，我们可以二分最后一个 ansyans_y 和 ansxans_x 相等的 yy。但是当 xx 很小时，不同的 ansxans_x 很多，怎么办呢？考虑根号分治。
设 BB 表示根号分治的阈值：
当 x≤Bx \le B 时暴力求解，时间复杂度为 O(nB)O(nB)。
当 x>Bx \gt B 时采用上面的算法求解。因为不同的 ansxans_x 最多有 nB\frac{n}{B} 个，所以时间复杂度为 O(nBnlog⁡2n)O(\frac{n}{B}n\log_2{n})。
由基本不等式，得时间复杂度为 O(nB+nBlog⁡2n)≥O(n2log⁡2n)O(nB+\frac{n}{B}\log_2{n}) \ge O(\sqrt{n^2\log_2{n}})，当且仅当 B=nlog⁡2nB=\sqrt{n\log_2{n}} 时等号成立。

AC code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...