[nowcoder 2020] 牛半仙的魔塔(增强版)

  • 时间:
  • 来源:互联网
  • 文章标签:

一、题目

点此看题

二、解法

值得一说的是本题的数据范围,你看他构造得这么恶心,就知道是为了避免某些情况。人的攻击力一定比怪高,那么人一定打的掉血。怪物的伤害很高,人无论如何都会掉血。这告诉我们只用求减免的伤害最多就行了,也不用多么麻烦的判无解(还没有无解的数据呢!)

不妨从贪心的角度思考,俗话说的好:十个贪心九个排。想要知道最优的选取顺序,可以排序!推理排序规则的方法就是我们看最好的排列方法满足什么条件,然后按照这个条件排就可以了,现在我带着你们来推一推,假设 i , j i,j i,j是两个相邻的怪物( i i i先被打, d d d是防御加成, h h h是战斗轮数):
d [ i ] h [ j ] ≥ d [ j ] h [ i ] d[i]h[j]\geq d[j]h[i] d[i]h[j]d[j]h[i] d [ i ] h [ i ] ≥ d [ j ] h [ j ] \frac{d[i]}{h[i]}\geq \frac{d[j]}{h[j]} h[i]d[i]h[j]d[j]那么我们可以按上述规则排序,但是问题是基于一个树形结构的,也就是排序的结果不一定在树形结构上合法,有些点是"阻挡"了另一些点的选取。怎么办?问题很复杂,考虑减小问题规模

怎么减小问题规模?我们去考虑当前性价比(也就是 d [ i ] h [ i ] \frac{d[i]}{h[i]} h[i]d[i])最高的点,如果他的父亲被选取了就会立即选他(这个结论看似有些跳跃,如果根据"阻挡"的关系还是有蛛丝马迹可寻的),因为这个点是当前性价比最高的,所以这样一定会被优先选择。

有了这个结论,我们可以用一种图论关系来表示这种阻挡下的选取,也就是当前取出最大性价比的点后,用并查集把他和父亲合并到一起,由于父亲还不知道什么时候被选取,我们就把他们缩成一个新的点,轮数和蓝宝石数都是原来的和,再插入到大根堆当中,这样我们就达到了减小问题规模的目的。

如果某一时刻这个父亲是 1 1 1所在的并查集,那么这个并查集就可以按顺序选取了。还有一个细节,合并的完后我们不需要删去原父亲的并查集,因为新点的性价比更高,我们只要保证不会多次操作同一个并查集即可,不难看出时间复杂度是 O ( n log ⁡ n ) O(n\log n) O(nlogn)

b y   t h e   w a y \tt by\space the\space way by the way,函数没打返回值给爷调吐了。

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int M = 100005;
#define int long long
int read()
{
    int num=0,flag=1;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();
    return num*flag;
}
int n,tot,f[M],a[M],b[M],c[M],d[M],h[M];
int vis[M],sc[M],fa[M],p[M],sh[M],sd[M];
vector<int> vc[M];
struct node
{
    int u;double t;
    bool operator < (const node &b) const
    {
        return t<b.t;
    }
};priority_queue<node> q;
struct edge
{
    int v,next;
}e[2*M];
void dfs(int u)
{
    for(int i=f[u];i;i=e[i].next)
        if(e[i].v^p[u])
        {
            p[e[i].v]=u;
            dfs(e[i].v);
        }
}
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void fight(int x)//一开始写int会答案错误? 
{
    a[1]-=(b[x]-c[1])*h[x];
    c[1]+=d[x];
}
void fuck(int x)
{
    fight(x);sc[x]=1;
    for(int i=0;i<vc[x].size();i++)
        fuck(vc[x][i]);
}
signed main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        e[++tot]=edge{v,f[u]},f[u]=tot;
        e[++tot]=edge{u,f[v]},f[v]=tot;
    }
    dfs(1);fa[1]=1;
    a[1]=read();b[1]=read();c[1]=read();
    for(int i=2;i<=n;i++)
    {
        a[i]=read();b[i]=read();c[i]=read();d[i]=read();
        sh[i]=h[i]=(a[i]-1)/(b[1]-c[i]);sd[i]=d[i];fa[i]=i;
        q.push(node{i,1.0*sd[i]/sh[i]});
    }
    sc[1]=1;
    while(!q.empty())
    {
        int u=q.top().u,F=find(p[u]);q.pop();
        if(vis[u]) continue;vis[u]=1;
        if(sc[p[u]]) {fuck(u);continue;}
        sh[F]+=sh[u];sd[F]+=sd[u];
        vc[F].push_back(u);fa[u]=F;
        q.push(node{F,1.0*sd[F]/sh[F]});
    }
	cout<<a[1]<<endl;
}

本文链接http://www.taodudu.cc/news/show-1782070.html