acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 题解(救援分区)

    先梳理题意 & 核心思路 题目是一棵树上砍一条边,把树拆成两棵子树 A、B。 要求: * A 里面 至少 1 个医疗站、至少 1 个物资站 * B 里面 至少 1 个医疗站、至少 1 个物资站 在合法的切割里,求 (|sumA - sumB|) 的最小值;无解输出 -1。 设: * sumAll:整棵树总人口 * (subSum[x]):以 x 为根的子树人口和 * (subM[x]):子树 x 内医疗站总数 * (subS[x]):子树 x 内物资站总数 * totalM:全树医疗站总数 * totalS:全树物资站总数 切断父节点和子节点 v 这条边后: * 子块:子树 vvv ✅ 合法条件:(subM[v]>=1, subS[v]>=1)(subM[v]>=1,\ subS[v]>=1)(subM[v]>=1, subS[v]>=1) * 剩下大块:原树去掉子树 vvv ✅ 合法条件:(totalM−subM[v]>=1,totalS−subS[v]>=1)(totalM - subM[v] >=1,totalS - subS[v] >=1)(totalM−subM[v]>=1,totalS−subS[v]>=1) 只要同时满足上面四条,这个切割就是合法的,差值 = (∣sumAll−2∗subSum[v]∣)( | sumAll - 2 * subSum[v] | )(∣sumAll−2∗subSum[v]∣),我们取最小即可。 C++代码: 杂度说明 * O(n)O (n)O(n),每个点每条边遍历一次,完全满足 n=2∗105n = 2*10^5n=2∗105 * p[i]p [i]p[i] 可以到 1e91e91e9,全部用 longlonglong longlonglong,这点代码已经处理

    userId_undefined
    黄昏中的落雁
    10月全勤卷王勇敢小狗快乐小狗秩序白银
    3阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页