2025-2026:teams:the_server_is_busy_please_try_again_later:20250717
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2025-2026:teams:the_server_is_busy_please_try_again_later:20250717 [2025/07/27 17:53] istina [总结] |
2025-2026:teams:the_server_is_busy_please_try_again_later:20250717 [2025/07/27 18:36] (当前版本) istina |
||
|---|---|---|---|
| 行 31: | 行 31: | ||
| 警钟长鸣。 | 警钟长鸣。 | ||
| + | |||
| + | ==== H -3 ==== | ||
| + | _istina_: 最意难平的一题。赛时思路和实现完全正确。包括建正反两张图求约束选某边时的最短路、把路径和边权增量打包视作直线插入坐标系，以及用单调栈线性维护。但是赛时写完了没能通过（也不知道问题出在哪里），赛后重构直接过了。 | ||
| 行 39: | 行 42: | ||
| Ender_hz: 一个技巧性比较强的魔改 $01$ 背包题。注意到物品价值会随物品占用总空间改变，而这道题的数据范围 $V\le 500$，因此直接枚举物品占用总空间 $V'$ 来固定物品价值，然后按照单个物品占用空间分组后用 ''nth_element'' 取每个空间 $curV$ 价值最大的前 $\dfrac{V'}{curV}$ 个，总共就是 $\sum\limits_{curV\le V'} \dfrac{V'}{curV}=\mathcal O(V'\log V')$ 个物品，对于每个 $V'$，背包的时间复杂度从 $\mathcal O(nV')$ 降至 $\mathcal O(n+V'^2\log V')$，总时间复杂度由 $\mathcal O(nV^2)$ 降至 $\mathcal O(nV+V^3\log V)$。 | Ender_hz: 一个技巧性比较强的魔改 $01$ 背包题。注意到物品价值会随物品占用总空间改变，而这道题的数据范围 $V\le 500$，因此直接枚举物品占用总空间 $V'$ 来固定物品价值，然后按照单个物品占用空间分组后用 ''nth_element'' 取每个空间 $curV$ 价值最大的前 $\dfrac{V'}{curV}$ 个，总共就是 $\sum\limits_{curV\le V'} \dfrac{V'}{curV}=\mathcal O(V'\log V')$ 个物品，对于每个 $V'$，背包的时间复杂度从 $\mathcal O(nV')$ 降至 $\mathcal O(n+V'^2\log V')$，总时间复杂度由 $\mathcal O(nV^2)$ 降至 $\mathcal O(nV+V^3\log V)$。 | ||
| + | |||
| ===== 总结 ===== | ===== 总结 ===== | ||
2025-2026/teams/the_server_is_busy_please_try_again_later/20250717.txt · 最后更改: 2025/07/27 18:36 由 istina
