DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

吃苹果

返回题目

题解

将吃苹果的顺序表示为100个格子的一个排列。如果在吃格子 vvv 的苹果之前,已经吃掉了距离它不超过2的其他苹果中的 kvk_vkv​ 个,则该苹果得分为 100⋅0.9kv100\cdot0.9^{k_v}100⋅0.9kv​。因此目标函数为 ∑v100⋅0.9kv\sum_v100\cdot0.9^{k_v}∑v​100⋅0.9kv​。

可以从随机排列开始模拟退火。使用交换两个位置,或者将一个苹果插入另一位置并移动中间区间等操作。若分数上升则接受;若下降 ddd,则在温度 TTT 下以概率 exp⁡(−d/T)\exp(-d/T)exp(−d/T) 接受。逐渐降温,多次重新开始,并单独保存历史最高分方案。

每个格子距离2以内的其他格子至多12个。预存邻接列表和当前排列中的位置,只更新先后关系发生变化的格子的 kvk_vkv​,即可快速计算分数变化。移动后的位置信息更新至多需要 O(100)O(100)O(100),直接重算全部得分也只需 O(100⋅12)O(100\cdot12)O(100⋅12)。

模拟退火不能保证达到 AC 门槛。由于网格固定,也可以事先充分搜索,将选定的顺序存入提交程序并直接输出。提供的参考解输出用交换和插入搜索得到的顺序,准确得分为 6391.44590319386391.44590319386391.4459031938,高于 6391.46391.46391.4 分的门槛,因此获得 AC,超出的分数也会保留。但不声称它是全局最优。参考程序运行时间与输出量成正比,不在提交时进行搜索。

朴素解按行顺序吃苹果。虽然输出是合法排列,但得分较低。

判定可以使用整数准确计算总分。因为 0≤kv≤120\le k_v\le120≤kv​≤12,将得分乘以 101210^{12}1012 后,每项变为整数 100⋅9k。不对总和设置上限,将实际得分与 的比值作为检查器的得分倍率。子任务满分也是 分,因此即使倍率超过 ,最终得分仍然是苹果得分总和。最终得分达到 分时判定为 AC。每项至多 ,总和至多 ,均在有符号64位整数范围内。

Solution written by GPT6

v⋅1012−kv100\cdot9^{k_v}\cdot10^{12-k_v}
100⋅9kv​⋅1012−kv​
6391.46391.46391.4
6391.46391.46391.4
111
6391.46391.46391.4
101410^{14}1014
101610^{16}1016