当前位置: 首页 > news >正文

LGP9755 [CSP-S 2023] 种树 学习笔记

LGP9755 [CSP-S 2023] 种树 学习笔记

Luogu Link

前言

故地重游。

巧合的是,上次写这道题刚好是在去年的九月二十七日,整整一年前。

题意简述

给定一个 \(n\) 个点,\(n-1\) 条边的简单无向连通图。

好吧,这片地本身的形态也是一棵树。

你的目标是:在每个结点上种一棵树,使其长到不低于 \(a_i\) 米。

你每天可以选择一个未种树且与已种树结点邻接的结点,种一棵高度为 \(0\) 米的树。若所有地块均已种树,则你当天不进行任何操作。特别地,第一天你只能在 \(1\) 号空地种树。

对每个地块而言,从该地块被种下树的当天开始,该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同,在整个任务的第 \(x\) 天结束时,\(i\) 号地块上的树会长高 \(\max(b_i+x\times c_i,1)\) 米。注意这里的 \(x\) 是从整个任务的第一天,而非种下这棵树的第一天开始计算。

你想知道:最少需要多少天能够完成你的任务?

\(n\le 10^5\)\(1\le a_i\le 10^{18}\)\(1\le b_i\le |c_i|\le 10^9\)。保证存在方案能在 \(10^9\) 天内完成任务。

做法解析

显然树越早种下去越好。整个问题是可以二分判断的。

二分时怎么判断呢?我们发现对于某个截止时间,每个结点都有一个最晚需要种树的时间点 \(lst_u\),这东西也是可以二分求的。除此之外,\(lst_u\) 也要对 \(lst_v-1\) 取最小值。最后你从 \(1\) 开始贪心地选最急迫的结点就行了。

在二分 \(lst_u\) 的时候你会需要计算 \(\sum_{i=l}^r\max(b_i+x\times c_i,1)\)

\(c_i\ge 0\) 的情况是好求的(题目保证了 \(b_i\ge 1\) 很舒服,我们不用考虑 \(b_i+x\times c_i\) 单增但不恒大于 \(1\) 的可能性)。

对于 \(c_i<0\) 的情况你需要先解一下 \(b_i+x\times c_i\ge 1\) 这个不等式。由于负数取模取整很麻烦,我们选择将其移项为 \(-c_i\times x\le b_i-1\),得 \(x\le\lfloor\frac{b_i-1}{-c_i}\rfloor\)。然后分段计算即可。

这样我们就在 \(O(n\log V\log n)\) 的时间复杂度内解决了此问题。

代码实现

注意会出现 \(V_c\times n^2\) 规模的运算,所以 calc 里面记得该开 __int128 的地方要开。

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
int N,X,Y;lolo A[MaxN],B[MaxN],C[MaxN];
vector<int> Tr[MaxN];
void addudge(int u,int v){Tr[u].push_back(v);Tr[v].push_back(u);
}
molo calc(int u,lolo lb,lolo rb){if(C[u]>=0)return B[u]*(rb-lb+1)+(lb+rb)*(rb-lb+1)/2*molo(1)*C[u];int bkp=(B[u]-1)/-C[u];if(bkp<lb)return rb-lb+1;if(rb<=bkp)return B[u]*(rb-lb+1)+(lb+rb)*(rb-lb+1)/2*molo(1)*C[u];return B[u]*(bkp-lb+1)+(rb-bkp)+(lb+bkp)*(bkp-lb+1)/2*molo(1)*C[u];
}
int lst[MaxN];
int getlst(int u,int lim){int sl=1,sr=N,smid,res=0;while(sl<=sr){smid=(sl+sr)>>1;if(calc(u,smid,lim)>=A[u])res=smid,sl=smid+1;else sr=smid-1;}return res;
}
void dfs(int u,int f){for(int v : Tr[u]){if(v==f)continue;dfs(v,u),minner(lst[u],lst[v]-1);}
}
bool solve(int lim){for(int i=1;i<=N;i++){lst[i]=getlst(i,lim);if(!lst[i])return false;}dfs(1,0);sort(lst+1,lst+N+1);for(int i=1;i<=N;i++)if(lst[i]<i)return false;return true;
}
int main(){readi(N);for(int i=1;i<=N;i++)readis(A[i],B[i],C[i]);for(int i=1;i<N;i++)readis(X,Y),addudge(X,Y);int sl=N,sr=1e9,smid,ans;while(sl<=sr){smid=(sl+sr)>>1;if(solve(smid))ans=smid,sr=smid-1;else sl=smid+1;}writi(ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=18865

相关文章:

  • 7、revision 是 Maven 3.5+ 引入的现代版本管理机制 - 实践
  • P1731 生日蛋糕 做题记录
  • 如何有效提升代码覆盖率:从单元测试到集成测试的实践指南
  • Spring知识点(2)
  • 超越实习期的AI自动化工具:播客工作流与Slack导出器实战
  • 调度器的各项指标以及计算方式
  • 浅谈dsu on tree
  • JavaDay10
  • 昇腾多机推理极速上手:10倍简化的 DeepSeek R1 超大规模模型部署
  • python开始exe应用程序初级教程
  • B站油管抖音一键笔记
  • 介绍自己
  • pycharm更换国内源
  • 基于Python+Vue开发的反诈视频宣传管理系统源码+运行步骤
  • 0voice-2.2.1-服务器百万并发实现
  • 微服务去掉认证的功能
  • INNER JOIN LEFT JOIN, RIGHT JOIN, FULL OUTER JOIN
  • 进程调度的时机,切换与过程
  • 深入解析:六维力传感器材质选择:影响性能与精度的关键因素
  • 按键精灵安卓/ios辅助工具,脚本开发新手教程ui界面介绍 - 教程
  • P3197fwx - FanWenxuan
  • 2025年AI大模型赋能智能座舱研究报告:技术、资本与市场|附20+份报告PDF、数据仪表盘汇总下载
  • 专题:2025年AI Agent智能体行业洞察报告|附110+份报告PDF、数据仪表盘汇总下载
  • 开启我的Java旅程
  • MYSQL: 时间戳演示
  • 自动化测试用例结构分析
  • 谷歌新款具身智能模型 Gemini Robotics 1.5 和 Gemini Robotics-ER 1.5
  • 完整教程:测试自动化教程:Parasoft如何流重定向与单元测试自动化
  • 用 Zig 实现英文数字验证码识别
  • 用 Crystal 实现英文数字验证码识别工具