2025 ICPC 南京 / UCUP 4. Stage 5: GP of Nanjing
VP on 2025-11-15,只做了三题。
| ID | Diff | Description | Solution | Penalty | Review |
|---|---|---|---|---|---|
| B | Medium | 只袋鼠,第 只袋鼠的初始坐标 ()。任意操作:选择四种指令之一,作用于所有袋鼠:,,,:最大化 的袋鼠数量。 | (1) 即给 个不等式 ,找一组整数 使得最多的不等式成立。 (2) 直接做是半平面交,但我们没必要这样做(我也不会这个板子)。重要的观察是 ,这意味着所有平面都不包含原点。可以不妨设找出的整数 是无穷远点,进一步,最优点一定取平面的边界。(像是拿着手电筒原地转圈,问哪个方向照到的最多。) (3) 对所有平面边界的射线极角排序,对边界的极角做差分,算出每个地方的答案。 | * | 不要乱用 eps; 的可以安全 atan2。 |
| C | Easy | 求 满足 。 | 小清新签到。奇数无解,偶数取 。 | 4 | |
| F | Hard | 点且初始无边的无向图, 次操作:添加边权为 的边;最大化两点间路径按位与。 | (1) 查询:从高到低逐位贪心。对于每一位,尝试将其加入当前已确定的结果中。维护 :只考虑 的边构成的子图连通性。检查利用这些边,能否使目标连通。单次 。 (2) 维护 的方法: 个并查集,有用的合并只有 次。每次合并之后, 删去一位,递归到下一层。总时间 。 | AC | 好题。先考虑要做什么查询,再决定用什么数据结构维护及考虑如何修改。 |
| G | Hard | 个水桶,容量 ,每秒漏水 。初始时任意合并水桶,容量取最大值,漏水取最小值。 次询问第 秒最大剩余容量。 | (1) 考虑所有可能子集 ,欲求时间 - 剩余总容量 图像的上凸壳,这个凸壳时间越大,斜率越缓。预处理凸壳分界点,多次询问在凸壳上二分。。 (2) 不需要考虑所有子集,基于贪心,剩下容量最大的 个与漏水最慢的 个。将容量和漏水速率排序后,计算每一段的 和 就能确定合并时间,即一次函数的交点,为 。 (3) 合并方案:设容量最大的 个是红色,漏水最慢的 个是蓝色。一个桶可能同时有两种颜色。那么同时标红、标蓝的桶,各自建立一组;仅标红的桶与仅标蓝的桶,两两配对;没有颜色的桶,随意并入已有组。 | 271+1 | |
| I | Hard | 天,初始资金 。第 天会产生打车费 ,可以选择两种行动之一:(1) 花费 吃饭,收益 ,自己不打车,因此 的概率 A 朋友花费打车费 , 的概率 B 花费;(2) 花费 吃饭,收益 ,和朋友打车,如果自第一天起或自你上次承担打车费用以来,两位朋友都曾承担过打车费用,则这次必须承担,否则规则同 (1)。在保证所有可能情况的总花费均不超过 的前提下,最大化收益期望。 | :从第 天到最后一天,已经花费 元钱,上次以来 AB 都没付 / 仅 A 付 / 仅 B 付 / AB 都付,最大收益期望。。 | AC | 不能用一个有限的负数表示不可能。参与期望计算时,会把不可行方案逐渐稀释变成可行方案。 |
| K | Medium | 象棋棋盘,马先手,车能否吃掉马。 | 唯一的 Yes:无论马第一步怎么走,车都能在第一步吃掉马。 | 71+2 | 不要写超长 if。 |
I 的一些分析【期望 DP】
这题的状态分为两部分: 确知的费用 和 随机的状态机。前者的实现是 01 背包 DP,后者是期望 DP。
先说随机的状态机。
首先回忆一下期望 DP 的一般做法:
依据题意,状态机是关于过去的(谁付过钱导致现在的状态)。虽然状态是由过去决定的,但我们在第 天计算时,不需要知道过去具体发生了什么,我们只需要知道现在做决策 A 时,我的未来期望就是这么多即可。也就是说,在 DP 第 天时,需要先知道第 天的答案,因此期望 DP 的状态设的是从第 天到最后一天。
如果第 天出去吃,第 天的状态 3 只能转移到第 天的状态 0,状态 0/1/2 有一定概率转移到 1/2/3。所以,我们列出的转移方程类似于(先不考虑费用)
那么如何加入确知的费用呢?
再加一个维度,实现我知道要花这么多钱的前提下,做某个决策未来会得到多少期望。这同时也满足了题目要求的最坏情况,因为我们已经为每一次决策预留足够的空间——先决定钱,再决定概率。
1 | // 遍历每一个可能的确知预算状态 i |
本部落格所有文章除特別聲明外,均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源 小明の雜貨屋!
評論