bzoj5461 Minimax 题解
2024-10-20 08:25:51
https://www.lydsy.com/JudgeOnline/problem.php?id=5461
看到题目,必将m种权值离散化。
首先是一个显然的dp设计。
设$f(i,j)$表示第i个节点,最终取值为j(已离散化)的概率。
因为树上的节点儿子数不超过2,不妨设值k出现在左儿子上。
则有$f(x,k)=f(ls,k)*(pmx_x*\sum \limits_{j=1}^{k-1}f(rs,j)+pmn_x*\sum \limits_{j=k+1}^{m}f(rs,j))$
初态是$f(leaf,val[leaf])=1$,答案直接对$f(1)$统计即可。
从实际含义上理解,正确性是显然的。
所以dp前预处理前缀和,可以做到$O(n^2)$。
因为树上情况比较特殊,加上保证只有不超过两个儿子,并不自然地想到了线段树合并。
如果是叶子,插入权值为1的节点。
否则进行两个儿子的线段树合并。
在线段树合并的同时,维护两棵线段树当前子树的前缀后缀和。
如果递归到其中一棵树为空,给另一棵树打上乘一个值的标记就可以了。
最后$dfs(root[1])$统计答案。
该题复杂度为$O(mlogn)$,
证明:
线段树合并复杂度等于$merge$函数调用次数。
$merge$函数调用一次,除非遇到(线段树上的)叶子节点,必定销毁一个节点。
并且,线段树是二叉树,
也就是说遇到的(线段树上的)叶子节点个数不会多于销毁的节点个数。
只在遇到(题中树上的)叶子节点时插入了$mlogn$个节点,故得证。
最新文章
- Oracle Partition By 的使用
- JAVA Socket 编程学习笔记(二)
- RabbitMq 应用
- CentOS7编译安装Nginx-1.8.1和编译参数
- C++全局变量的声明和定义
- 微软TechEd2013大会将在北京、上海召开!
- -_-#【HTML】同一个标签页打开
- FineUI表单验证
- hdu4506小明系列故事——师兄帮帮忙 (用二进制,大数高速取余)
- 修改已经提交到远端的git commit信息
- Next-Key Locks
- Unity 坐标 转换 详解 World世界坐标 Screen屏幕坐标 View视口坐标 GUI坐标 NGUI坐标 localPosition相对父级坐标
- 图片支持get请求访问
- react-native中的动画
- Huawei® ENSP &; VRP CheatSheet
- django中的null=true,blank=true,这个讲得清楚点
- git merge和git rebase的区别
- 【BZOJ2395】【Balkan 2011】Timeismoney 最小乘积生成树
- python文件操作-r、w、a、r+、w+、a+和b模式
- azure 最佳实践 -- 保持冗余
热门文章
- IDEA报错Plugin ";XXX"; was not loaded: required plugin ";Java EE: EJB, JPA, Servlets"; is disabled.
- VIM编辑器使用的小技巧
- 微信小程序调用云函数出错 Error: errCode: -404011 cloud function execution error | errMsg: cloud.callFunction:fail cloud function service error code -501005, error message Environment not found;
- elasticsearch 分词后聚合
- PCA 从线性变换的角度理解
- z = z*z + c的分型图如何画
- tensorflow批量读取数据
- Python装饰器与闭包
- sed命令基本用法
- Proxy监听对象的数据变化,处理绑定数据很有用