牛客周赛 Round 17

A.游游的正方形披萨

思维

考虑是一个正方形，并且要满足长宽越近越好，而且大家等面积，假设我们竖着切了一刀明显长宽差距就很大了，这个时候横着切一刀就平衡了一点，所以简单笔画一下得出，一半横着一半竖着是最优的，横着x刀会变成x+1块横着的，所以横竖用乘积

void solve()
{
    cin>>n>>m;
    int half=m/2;
    int ans=(half+1)*(m-half+1);
    double res=1.0*n*n/(ans);
    cout<<LF(2)<<res<<endl;
    
    return ;
}

B.游游的字母翻倍

暴力

是不是觉得我们要使用什么高级数据结构但是我们通过看数据范围可以得出直接暴力模拟即可，丑陋写法如下

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    
    while(m--){
        string ans;
        int l,r; cin>>l>>r;
        for(int i=1;i<l;i++) ans+=s[i];
        
        for(int i=l;i<=r;i++){
            ans+=s[i];
            ans+=s[i];
        }
        
        for(int i=r+1;i<=n;i++) ans+=s[i];

        n=ans.size();
        for(int i=0;ans[i];i++) s[i+1]=ans[i];
    }
    for(int i=1;i<=n;i++) cout<<s[i];
    
    return ;
}

C.数组平均

贪心+前缀和

我们明显有一个思想就是影响结果最明显的就是最大值和最小值，那么我直接贪心的改变最大值和最小值，所以直接就枚举改变最小值的数量和最大值的数量即可，用前缀和来维护变化的值

int a[N],b[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];
    
    if(m==n){
        cout<<LF(7)<<0.00<<endl;
        return ;
    }
    double res=3e18;
    for(int i=0;i<=m;i++){
        int j=m-i;
        double sum=b[i]+b[n]-b[n-j];
        double mi=min(1.0*a[i+1],sum*1.0/m);
        double ma=max(1.0*a[n-j],sum*1.0/m);
        res=min(ma-mi,res);
    }
    cout<<LF(7)<<res<<endl;
    return ;
}

D.游游出游 二分+dijkstra 典型

题目一开始就带有限制意思也就是我们不知道最大可以背多重，但是我们可以明显发现具有单调性，这就很很好办，直接用二分，同时要小于h怎么判断抵达呢？我们直接用dijkstra跑一边对于不满足的边不加入即可，对剩下的边跑dijkstra就好了，注意无解所以再check一次判断是不是无解就好

vector<TUP> g[N];
int d[N];
bool st[N];
 
bool check(int mid){
    memset(d,0x3f,sizeof d);
    memset(st,0,sizeof st);
    d[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.emplace(0,1);
    while(!q.empty()){
        auto [dist,u]=q.top(); q.pop();
        if(st[u]) continue;
        st[u]=true;
        for(auto&[v,w,d1]:g[u]){
            if(w<mid) continue;
            if(d[v]>d[u]+d1){
                d[v]=d[u]+d1;
                q.emplace(d[v],v);
            }
        }
    }
    return d[n]<=h;
}
void solve()
{
    cin>>n>>m>>h;
    while(m--){
        int u,v,w,d; cin>>u>>v>>w>>d;
        g[u].push_back({v,w,d});
        g[v].push_back({u,w,d});
    }
     
    int l=0,r=2e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    if(!check(l)) cout<<-1<<endl;
    else cout<<l<<endl;
    
    return ;
}

这场比较简单QWQ,最后一题比较经典一定要掌握思想，以及第三题的贪心策略