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

洛谷比赛做题记录

SCP-J 2025

T3 P14259 兄妹(siblings)

每一列的书交给一个人来放是最优的。预处理出每一列的总步数 \(v_i\)
同时处理横坐标和纵坐标的步数非常不便。我们发现两个人 \(X,Y\) 里面一定有一个横坐标最大会去到最后一列,令他为 \(Y\),那我们枚举 \(X\) 最大取到第 \(i\) 列。那么第 \(i+1\sim maxr\) 列的书都由 \(Y\) 负责,第 \(i\) 列一定由 \(X\) 负责,直接加上。
问题转化成前 \(i-1\) 列有 \(i-1\) 个东西,怎么分配给两个人使得两个人得到的东西价值更大者最小。显然二分。于是问题又转化成 \(i-1\) 个东西,限定每个人最多可以拿 \(mid\) 体积的东西,看能否拿完所有东西。这也是显然的背包。我们让每个物品的价值和体积都为 \(v_i\),背包算一个人最多能拿多少体积的东西,这时当前 \(v\) 的总量减去它就是另一个人要拿的东西总体积,看它拿不拿的下(会不会超过 \(mid\))即可。
这里对于背包,由于枚举每一个 \(i\) 都要看当前的前 \(i-1\) 个物品的情况,所以我们每一次循环就加入一个物品来做一次背包即可。不要每一次循环都整体背包一次,更不要在二分里背包。
枚举的 \(r_{max} \le 5*10^2\),背包用到的 \(sumv \le r_{max}*c_{max}*2=5*10^5\),二分 \(log\),乘起来不超时。(?

http://www.hskmm.com/?act=detail&tid=34565

相关文章:

  • 什么是命运(摘抄)
  • 编程指北的 C++
  • Linux grep命令
  • 物品复活软件开发记录 - CelestialZ
  • 螺纹钢的中线节奏
  • 2022 ICPC Hangzhou
  • KL散度
  • Win11常用的bat脚本
  • 随便记
  • Map与Map.Entry的区别
  • 真诚
  • 历史和线段树
  • 大数据分析之MySQL学习2
  • [KaibaMath]1012 关于收敛数列保号性的推论的证明
  • 申公豹说
  • 赛前训练 12 树的直径、中心和重心
  • 关于无人巡航小车的学习笔记
  • 详细介绍:springboot+vue智慧旅游管理小程序(源码+文档+调试+基础修改+答疑)
  • 存算一体架构的先行者:RustFS在异构计算环境下的探索与实践
  • 2-SAT
  • CSP-S模拟10
  • CSP-S模拟赛加赛 比赛总结
  • 我要好好写博客了 - Milo
  • 洛谷P4735--最大异或和
  • DAPO代码实现浅析
  • [KaibaMath]1011 关于收敛数列保号性的证明
  • Appium 3.0:跨平台移动自动化测试框架全面解析
  • 赛前训练 12 extra 树上差分倍增
  • 塔吊施工人员操作合规性监测!思通数科 AI 卫士实时守护作业安全
  • Dos命令1