首页 > 其他分享 >POI2011/洛谷P3523 DYN-Dynamite

POI2011/洛谷P3523 DYN-Dynamite

时间:2024-10-31 11:43:23浏览次数:1  
标签:TNT ch P3523 POI2011 mid char DYN 引爆 getchar

前言

Link

本来一个很直观的题面,非要搞形式化题意反而使题意变得非常迷惑。

题意

有一栋树形建筑,其中有一些点摆放了 TNT ,树边上都摆放了引信,引信的燃烧时间为 \(1\) 秒 \(/\) 边,现在你要选择 \(m\) 个点同时点燃引信(起爆),则显然 TNT 被引爆的时间为到离它最近的起爆处的距离,请你求出所有 TNT 爆炸所需的最短时间。

思路

首先最大值最小肯定是二分,check(mid) 就是求至少需要同时在多少点起爆才能做到 \(mid\) 秒内所有 TNT 引爆,如果这个值大于 \(m\) 则说明时间不够,小于 \(m\) 说明时间还可以更短。当然 check 不只有这一种,但个人认为这是相对容易的方式。

那么可以考虑树形 dp(严格来讲是贪心),记 \(f[x][0]\) 为 \(x\) 子树中离 \(x\) 最的还不能被引爆的** TNT 距离,\(f[x][1]\) 为 \(x\) 子树中离 \(x\) 最起爆点**距离。

  • 从儿子转移到父亲是容易的,直接 \(f[u][0]=\max\{f[v][0\}+1\),\(f[u][1]=\min\{f[v][1]\}+1\)。

  • 如果 \(u\) 自己就是 TNT ,那么更新 \(f[u][0]\)。

  • 如果 \(f[u][0]+f[u][1]\leq mid\),说明 \(u\) 子树中的某个起爆点可以在 \(mid\) 秒内,通过经过 \(u\) 的引信引爆 \(u\) 子树中最远的 TNT ,那既然最远的都能引爆,说明 \(u\) 子树中所有的 TNT 都能被引爆,于是 \(f[u][0]=-\infin\)。

  • 如果离 \(u\) 最远的 TNT 距离等于 \(mid\) 了,那么就必须在 \(u\) 设置起爆点,更新 \(f[u][0]\),\(f[u][1]\)。

这样贪心一定是优的,因为我们每个 TNT 都是拖到实在不能再拖的时候才起爆的。

代码

#include<bits/stdc++.h>
#define getmax(x,y) x=max(x,y)
#define getmin(x,y) x=min(x,y)
#define getmid int mid=(l+r)/2
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
    static char ch[1<<20],*l,*r;
    return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
    static char wtbuff[20];
    static int wtptr;
    if(x==0){
        putchar('0');
    }
    else{
        if(x<0){x=-x;putchar('-');}
        wtptr=0;
        while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
        while(wtptr--) putchar(wtbuff[wtptr]);
    }
    if(endch!='\0') putchar(endch);
}
const int MAXN=300005,INF=0x3f3f3f3f;
int n,m,f[MAXN][2],cnt,head[MAXN],ecnt=0;
bitset<MAXN>charge;
struct EDGE{
    int v,nxt;
}e[MAXN<<1];
inline void add(const int& u,const int& v){
    e[++ecnt].v=v;
    e[ecnt].nxt=head[u];
    head[u]=ecnt;
}
void dfs(int x,int fa,int val){
    f[x][0]=-INF,f[x][1]=INF;
    for(int i=head[x];i;i=e[i].nxt){
        int it=e[i].v;
        if(it==fa) continue;
        dfs(it,x,val);
        getmax(f[x][0],f[it][0]+1);
        getmin(f[x][1],f[it][1]+1);
    }
    if(charge[x]) getmax(f[x][0],0);
    if(f[x][0]+f[x][1]<=val) f[x][0]=-INF;
    if(f[x][0]==val){
        cnt++;
        f[x][0]=-INF;f[x][1]=0;
    }
}
inline bool check(int x){
    cnt=0;
    dfs(1,0,x);
    cnt+=(f[1][0]>=0);
    return cnt<=m;
}
int main(){
    rd(n);rd(m);
    for(int i=1,x;i<=n;i++){
        rd(x);
        charge[i]=x;
    }
    for(int i=1,u,v;i<n;i++){
        rd(u);rd(v);
        add(u,v);add(v,u);
    }
    int l=0,r=n,res=n-1;
    while(l<=r){
        getmid;
        if(check(mid)){
            res=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<res<<endl;
    return 0;
}

标签:TNT,ch,P3523,POI2011,mid,char,DYN,引爆,getchar
From: https://www.cnblogs.com/SkyNet-PKN/p/18517405

相关文章

  • POI2011/洛谷P3514 LIZ-Lollipop
    前言典中典思维蓝题难度薄纱模板水紫捏。\(1\)\(2\)序列这种也不是第一次见了,感觉多多少少都沾点Ad-hoc。话说这种考法真的好吗,一上来就是一个门槛很高的性质,推出来就满分,推不出来就\(0\)分,正推和反推的难度完全不是一个思维量级。题意Link给一个只有\(1\)和\(2\)......
  • YOLO11改进 | 卷积模块 | 在主干网络中添加蛇形卷积Dynamic Snake Convolution
    秋招面试专栏推荐 :深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转......
  • DYN / 消防局的设立 / Spread of Information / 将军令 题解
    前言四倍经验:[POI2011]DYN-Dynamite;[HNOI2003]消防局的设立;[ARC116E]SpreadofInformation;将军令。题意简述给你一棵\(n\)个结点的树和点集\(S\),你要选出\(k\)个关键点\(T\),求\(\min\max\limits_{u\inS}\min\limits_{v\inT}\operatorname{dis}(u,v)\)......
  • Dynamic DMA mapping Guide(重要的)
    一、前言这是一篇指导驱动工程师如何使用DMAAPI的文档,为了方便理解,文档中给出了伪代码的例程。另外一篇文档dma-api.txt给出了相关API的简明描述,有兴趣也可以看看那一篇,这两份文档在DMAAPI的描述方面是一致的。二、从CPU角度看到的地址和从DMA控制器看到的地址有什么不同?在DM......
  • Python's exec Functions: Execute Dynamically Generated Code
      #encoding:utf-8#版權所有2024©塗聚文有限公司#許可資訊查看:言語成了邀功的功臣,還需要行爲每日來值班嗎?#描述:主、子表單窗體傳值Parent-childformoperations#Author:geovindu,GeovinDu塗聚文.#IDE:PyCharm2023.1python3.11#OS......
  • TRLO: An Efficient LiDAR Odometry with 3D Dynamic Object Tracking and Removal
    arxiv|中科院联合国科大开源TRLO:一种结合3D动态物体跟踪与移除的高效LiDAR里程计【TRLO:AnEfficientLiDAROdometrywith3DDynamicObjectTrackingandRemoval】文章链接:[2410.13240]TRLO:AnEfficientLiDAROdometrywit...项目主页:GitHub-Yaepiii/TRLOTRLO:A......
  • E71 树形DP+二分 P3523 [POI2011] DYN-Dynamite
    视频链接:   P3523[POI2011]DYN-Dynamite-洛谷|计算机科学教育新生态//树形DP+二分O(nlogn)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;intread(){intx=0,f=1;charc=getchar();while(c>'9'||c......
  • Spacetime Gaussian Feature Splatting for Real-Time Dynamic View Synthesis
    SpacetimeGaussianFeatureSplattingforReal-TimeDynamicViewSynthesis摘要动态场景的新视角合成一直是一个引人入胜但充满挑战的问题。尽管最近取得了很多进展,但如何同时实现高分辨率的真实感渲染、实时渲染和紧凑的存储,依然是一个巨大的挑战。为了应对这些挑战,......
  • cpp:指针转化(百度AI:static_cast/dynamic_cast/const_cast/reinterpret_cast)
    cpp:指针转化(百度AI:static_cast/dynamic_cast/const_cast/reinterpret_cast)    一、c++指针转化概述: 在C++中,指针转换主要包括静态转换、动态转换、常量转换和重新解释转换四种类型。‌ ‌1、 静态转换(static_cast)‌: -- 用于基本数据类型之间的转换,如将int转换......
  • P8969 幻梦 | Dream with Dynamic
    Sol好题!注意到popcount操作会使数以\(\log\)的速度变小,所以没有加操作的话我们就可以直接暴力维护。但是注意到有加操作,考虑懒标记,先popcount后加。当一个区间popcount之后,值域范围极小,所以考虑暴力对每一种数预处理popcount。这里其实可以用线段树但是我懒了,用了分......