首页 > 其他分享 >ICPC2021Kunming G Find the Maximum 题解

ICPC2021Kunming G Find the Maximum 题解

时间:2023-12-28 22:56:40浏览次数:43  
标签:ch frac int 题解 sum mid ICPC2021Kunming ans Find

Question

Find the Maximum

给出一个树,每个点有一个权值 \(b_n\),求一条树上路径 \(V\),要求 \(\frac{\sum_{u\in V (-x^2+b_u x)}}{|V|}\) 最大,其中 \(x\) 是自己选择的一个树

Solution

先转化一下 \(\frac{\sum_{u\in V (-x^2+b_u x)}}{|V|}\), 得到

\[\frac{\sum_{u\in V (-x^2+b_u x)}}{|V|}\le \frac{1}{4}(\frac{\sum_{u\in V}b_u}{|V|})^2 \]

也就是要求 \(\frac{\sum_{u\in V} b_u}{|V|}\) 的最值

可以二分枚举最后的答案 \(\frac{\sum_{u\in V} b_u}{|V|}\ge mid\) 得到

\[\frac{\sum_{u\in V} b_u}{|V|}\ge mid \Leftrightarrow \sum_{u\in V} b_u-mid\times |V| \ge 0\Leftrightarrow \sum_{u\in V} (b_u-mid) \ge 0 \]

只需要找一条路径满足 \(\sum_{u\in V} (b_u-mid) \ge 0\) 就好了

用树形 DP 去找就好了,定义 \(c_u=b_u-mid\)

这里看到清华的一种比较好的 DP 方法,定义 \(dp[x]\) 表示从 \(x\) 节点开始的一段连续的最大和,\(ans[x]\) 表示 \(x\) 子树内的最大路径和

转移时

for(int v:G[u]){
	ans[x]=max(ans[x],dp[x]+dp[v]);
	dp[x]=max(dp[x],dp[v]+c[x]);
	ans[x]=max(ans[x],ans[v]);
}

最后只需要判断 \(F[1]\) 是否大于 \(1\) 即可


考虑另外一种做法

一条长度大于或等于 \(4\) 的路径都能拆成 \(2\) 条长度大于 \(1\) 的路径,而这 \(2\) 条长度大于 \(1\) 的路径中必然满足其中 \(1\) 条的平均值不大于拆分前的平均值,所以最后选择的路径长度肯定为 \(2\) 或 \(3\)

Code

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const double INF=1e5,eps=1e-12;
int n;
double ans;
vector<int> a,fa,vs;
vector<vector<int> > G;
vector<double> c,F;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

void dfs(int x,int f){
    fa[x]=f;
    for(auto v:G[x]) if(v!=f) dfs(v,x);
    vs.push_back(x);
}


bool check(double mid){
    for(auto x:vs){
        F[x]=-1e100;
        c[x]=a[x]-mid;
        for(auto v:G[x]) if(v!=fa[x]){
            F[x]=max(F[x],c[x]+c[v]);
            c[x]=max(c[x],c[v]+a[x]-mid);
            F[x]=max(F[x],F[v]);
        }
    }
    return F[1]>=0;
}

int main(){
    n=read();
    
    a.assign(n+1,0);G.assign(n+1,vector<int>());c.assign(n+1,0); F.assign(n+1,0); fa.assign(n+1,0);

    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++){
        int u,v;u=read();v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    
    check(3);

    double L=0,R=INF;
    double ans1=-INF;
    for(int i=1;i<=60;i++){
        double mid=(R+L)/2;
        if(check(mid)) {L=mid;}
        else R=mid;
    }
    ans1=L;
    
    for(int i=1;i<=n;i++) a[i]=-a[i];
    
    L=0,R=INF;
    double ans2=-INF;
    for(int i=1;i<=60;i++){
        double mid=(R+L)/2;
        if(check(mid)) {L=mid;}
        else R=mid;
    }
    ans2=L;

    ans=max(fabs(ans1),fabs(ans2));
    // printf("%.6lf %.6lf\n",ans1,ans2);
    printf("%.4lf\n",ans*ans/4);
    // cout<<clock()<<endl;
    return 0;
}

标签:ch,frac,int,题解,sum,mid,ICPC2021Kunming,ans,Find
From: https://www.cnblogs.com/martian148/p/17933762.html

相关文章

  • .in'ig.status: error: cannot find input file: `
    交叉编译libaac库,源码下载地址https://sourceforge.net/projects/faac/解压unzipfaac-1.28.zipcdfaac-1.28.zip执行./bootstrap时出现如下错误#./bootstrap-bash:./bootstrap:/bin/sh^M:badinterpreter:Nosuchfileordirectory原因是bootstrap的文件......
  • vue前端node内存溢出问题解决
    前端项目运行时,如果经常运行慢,崩溃停止服务,报如下错误:FATALERROR:CALL_AND_RETRY_LASTAllocationfailed-JavaScriptheapoutofmemory(JavaScript堆内存不足) 原因:因为在Node中,通过JavaScript使用内存时只能使用部分内存(64位系统:1.4GB,32位系统:0.7GB),这个时候,如......
  • openssh升级对应问题解决方案
    问题1:./openssl:errorwhileloadingsharedlibraries:libssl.so.1.1:cannotopensharedobjectfile:Nosuchfileordirectory解决方案:cp/usr/local/openssl1.1.1/lib/libssl.so.1.1/lib64/cp/home/tydl/openssl-1.1.1u/libcrypto.so.1.1/lib64/ 问题2:/etc/ssh/s......
  • 「题解」Codeforces 1427G One Billion Shades of Grey
    感谢127的指导/ll\(|h_u-h_v|=\max(0,h_u-h_v)+\max(0,h_v-h_u)\),那么可以把它看成这样的问题:\[\min\{\sum_{(u,v)}\max(0,h_u-h_v+w_{u,v})c_{u,v}\}\]对偶一下,问题就变为:如果两个格子相邻就互相连容量为\(c_{u,v}=1\),费用为\(w_{u,v}=0\)的边,跑最大费用循环流。为了限......
  • 「题解」P9747 「KDOI-06-S」签到题
    一个区间合法的充要条件是存在\(x\)满足其为区间按位或,并且《\(x\)左侧所有数或起来》《\(x\)右侧所有数或起来》二者有其一为\(x\)。扫描线扫右端点,不同的按位或将左端点分为\(\logA\)个区间,对于每个区间\([l,r]\)先在区间按位或\(v\)在序列中存在位置的vector中......
  • CF396C On Changing Tree 题解
    CF396C考虑将贡献表示出来:\(\forallv\in\text{subtree}_u\),\(v\)会加上\(x-(dep_v-dep_u)k\),然后发现这个东西可以维护整棵子树,即把\(x,dep_u\timesk\)和\(dep_v\timesk\)分开计算,然后\(dep_v\)可以最后再管,就变为子树加,单点和了。用树状数组维护dfs序即可。......
  • TinyMCE富文本编辑器粘贴图片自动上传问题解决
    TinyMCE编辑器支持粘贴图片,但是自动会将图片转换成base64编码,这样将内容提交到后台,数据会很大。  图|TinyMCE本文内容配置TinyMCE(版本:5.10.0)向编辑器中粘贴图片自动上传到后台,以下为配置代码:tinymce.init({selector:'#textarea',plugins:'previewautolink......
  • Ping不通问题解决 windows 查看对端MAC地址 ARP -a
    Ping不通问题解决   Linux查看ARP信息指南(linux查看arp) ARP(地址解析协议)是TCP/IP协议提供的网络层协议,通过ARP可以查看网络层面上当前可连接的本地网络内每个主机的MAC地址。 ##查看系统的ARP信息 Linux系统中查看ARP信息的方法有很多,下面简单介绍几种常见的查......
  • 完美解决SqlServer2012启动报错(cannot find one or more components.Please reinstall
    原因:默认安装在C:\ProgramFiles(x86)\MicrosoftVisualStudio10.0文件夹,以支持sqlserver2012.(我之前不小心把这个文件夹删除了)。解决方案:下载了visualstudio2010Isolatedshell完美解决问题,下载后安装就能正常运行SqlServer2012了,其他SqlServer版本请下载visualstudio......
  • 题解 P9993【[Ynoi Easy Round 2024] TEST_133】
    就硬把线段树3和数列分块入门2揉到一起出。维护原数组\(a\)及其历史最大值\(hist\),对每个块,维护块内\(a\)升序排序后结果\(p\)、块内\(a\)升序排序后历史最大值前缀和\(prehist\)、块加标记\(add\)、块历史和加标记\(histadd\)。下传标记和区间修改操作仿照线......