博客
关于我
T4牛半仙的魔塔(增强版)
阅读量:301 次
发布时间:2019-03-03

本文共 3352 字,大约阅读时间需要 11 分钟。

题目描述

牛半仙的妹子被大魔王抓走了,牛半仙为了就他的妹子,前往攻打魔塔。

魔塔为一棵树,牛半仙初始在一号点。

牛半仙有攻击,防御,血量三个属性。

除一号点外每个点都有魔物防守,魔物也有攻击,防御,血量三个属性。

每个怪物后面都守着一些蓝宝石,获得1蓝宝石可增加1防。

牛半仙具有突袭属性,所以遇到魔物后会率先发动攻击,然后牛半仙和魔物轮换地攻击对方。

一个角色被攻击一次减少的血量是对方的攻击减去自己的防御。

当一个角色的血量小于等于 0 时,他就会死亡。

当牛半仙第一次到达某个节点时会与这个节点的魔物发生战斗。

当一个魔物死亡后,这个魔物所在的节点就不会再产生新的魔物。

现在牛半仙想知道他打死魔塔的所有魔物后的最大血量。

输入描述:

第一行一个 n 代表节点数。 随后 n-1 行,每行两个数 i,j,表示 i 与 j 节点有边相连。

随后一行,三个数,依次为勇士的血量、攻击、防御。 随后 n-1 行,每行四个数,依次为怪物的血量、攻击、防御,和其守着的蓝宝石数量。

输出描述:

一个数,代表最大血量。如果牛半仙在打死魔塔的所有魔物之前就已经死亡了,则输出 -1。

备注:

对于100%的数据: n ≤ 1 0 5 n \le 10^5 n105,树

对于100%的数据:有牛半仙血量 < 5 ∗ 1 0 18 <5*10^{18} <51018,攻击 = 2000 =2000 =2000,盔甲防御 = 0 =0 =0。怪物血量为 3000 3000 3000 ~
1 0 6 10^6 106,攻击 5 × 1 0 5 5×10^5 5×105 7 × 1 0 5 7\times 10^5 7×105,防御 ≤ 1000 \leq 1000 1000,打完一只怪后获得的蓝宝石数量为 1 1 1 5 5 5

官方题解看懂 自己琢磨了一下想通了

所以写个通俗 ju ruo 点儿的

考虑第 i i i个攻击的怪

记第 i i i个怪有 b i b_i bi个蓝宝石

因为怪的血量和攻击和防御是不变的 勇士的攻击也是不变的

所以它会被勇士攻击 ⌈ 血 量 勇 士 攻 击 − 防 御 ⌉ \lceil\dfrac{血量}{勇士攻击-防御}\rceil

并攻击勇士 ⌈ 血 量 勇 士 攻 击 − 防 御 ⌉ − 1 \lceil\dfrac{血量}{勇士攻击-防御}\rceil -1 1 轮 可直接求出 记为 h i h_i hi

造成的伤害为 h i × ( 攻 击 − 初 始 防 御 − ∑ j = 1 i − 1 b i ) h_i\times (攻击-初始防御-\sum_{j=1}^{i-1}b_i) hi×(j=1i1bi)

总伤害为 ∑ i = 1 n h i × ( 攻 击 − 初 始 防 御 − ∑ j = 1 i − 1 b i ) \sum_{i=1}^n h_i\times (攻击-初始防御-\sum_{j=1}^{i-1}b_i) i=1nhi×(j=1i1bi)

求这个的最小值 即求 ∑ i = 1 n h i × ∑ j = 1 i − 1 b i \sum_{i=1}^n h_i\times \sum_{j=1}^{i-1}b_i i=1nhi×j=1i1bi 的最大值

可以推出按照权值 t i = h i b i t_i=\dfrac{h_i}{b_i} ti=bihi 升序排出来的答案最优

证明:若最优的情况为: h 1 , h 2 . . . h n h_1,h_2...h_n h1,h2...hn 。 交换 i i i, i + 1 i+1 i+1答案的改变量是 h i × b i + 1 − h i + 1 × b i < 0 h_i\times b_{i+1}-h_{i+1}\times b_i<0 hi×bi+1hi+1×bi<0

h i b i < h i + 1 b i + 1 \dfrac{h_i}{b_i}<\dfrac{h_{i+1}}{b_{i+1}} bihi<bi+1hi+1 得证 (感性理解也可)

考虑贪心 我们先攻击 t i t_i ti 小的 再攻击大的

显然不行 比如一个 t i t_i ti大的点有很多 t i t_i ti 小的子节点

这里给出一个结论

若儿子节点 y y y t t t 小于父亲节点 x x x t t t
那么攻击了的父亲节点 x x x 过后 会立即攻击儿子 y y y (这里好好想想为什么)

根据这个结论 我们可以从权值最小的节点开始 若节点 y y y 的权值小于父亲 x x x

这就意味着会连续攻击 x , y x,y x,y
我们就把 y y y 合并到 x x x 上 合并成一个大点

这个大点的权值 t t t 变成 ∑ h i ∑ b i \dfrac{\sum h_i}{\sum b_i} bihi

证明:若 1 1 1号节点和 2 2 2节点要连续攻击 比较下面两种情况对答案的贡献

① 按 1 , 2 , 3 1,2,3 1,2,3 h 2 × b 1 + h 3 × ( b 1 + b 2 ) h_2\times b_1+h_3\times (b_1+b_2) h2×b1+h3×(b1+b2)

② 按 3 , 1 , 2 3,1,2 3,1,2 h 1 × b 3 + h 2 × ( b 3 + b 1 ) h_1\times b_3+h_2\times (b_3+b_1) h1×b3+h2×(b3+b1)

①-②得 h 3 ( b 1 + b 2 ) − ( h 1 + h 2 ) b 3 h_3(b_1+b_2)-(h_1+h_2)b_3 h3(b1+b2)(h1+h2)b3

比较答案大小即比较的是 h 1 + h 2 b 1 + b 2 \dfrac{h_1+h_2}{b_1+b_2} b1+b2h1+h2 h 3 b 3 \dfrac{h_3}{b_3} b3h3 的大小 所以大点的权值为 ∑ h i ∑ b i \dfrac{\sum h_i}{\sum b_i} bihi 得证

从权值最小的节点开始 若点 y y y 的权值小于父亲所在的大点 x x x 就把 y y y 合并到 x x x 上 合并成一个大点

处理完后就从根节点开始 贪心地选择可以到达点中 权值最小的点

所形成的顺序就是攻击怪物的顺序了

#include 
#define N 210000using namespace std;typedef long long ll;int n;int f[N],nxt[N],data[N],num,fa[N],ff[N];ll ans;bool tag[N];struct node{ ll val,siz,pos;}h[N];inline bool operator <(node x,node y){ return 1ll*x.val*y.siz>1ll*y.val*x.siz; }inline void add(int x,int y){ nxt[++num]=f[x]; f[x]=num; data[num]=y; }priority_queue
q;inline int findf(int x){ return fa[x]==x?x:fa[x]=findf(fa[x]); }inline void dfs(int x){ int y; for(int i=f[x];i;i=nxt[i]){ y=data[i]; if(y==ff[x])continue; ff[y]=x; dfs(y); }}int main(){ cin>>n; ll x,y,z,a,b; for(int i=1;i

讲得不清楚就问哦 毕竟蒟蒻描述能力真的…不太好

转载地址:http://yahl.baihongyu.com/

你可能感兴趣的文章
Mysql8 数据库安装及主从配置 | Spring Cloud 2
查看>>
mysql8 配置文件配置group 问题 sql语句group不能使用报错解决 mysql8.X版本的my.cnf配置文件 my.cnf文件 能够使用的my.cnf配置文件
查看>>
MySQL8.0.29启动报错Different lower_case_table_names settings for server (‘0‘) and data dictionary (‘1‘)
查看>>
MYSQL8.0以上忘记root密码
查看>>
Mysql8.0以上重置初始密码的方法
查看>>
mysql8.0新特性-自增变量的持久化
查看>>
Mysql8.0注意url变更写法
查看>>
Mysql8.0的特性
查看>>
MySQL8修改密码报错ERROR 1819 (HY000): Your password does not satisfy the current policy requirements
查看>>
MySQL8修改密码的方法
查看>>
Mysql8在Centos上安装后忘记root密码如何重新设置
查看>>
Mysql8在Windows上离线安装时忘记root密码
查看>>
MySQL8找不到my.ini配置文件以及报sql_mode=only_full_group_by解决方案
查看>>
mysql8的安装与卸载
查看>>
MySQL8,体验不一样的安装方式!
查看>>
MySQL: Host '127.0.0.1' is not allowed to connect to this MySQL server
查看>>
Mysql: 对换(替换)两条记录的同一个字段值
查看>>
mysql:Can‘t connect to local MySQL server through socket ‘/var/run/mysqld/mysqld.sock‘解决方法
查看>>
MYSQL:基础——3N范式的表结构设计
查看>>
MYSQL:基础——触发器
查看>>