WC2022习题选做及总结

1.Kitesurfing

有一点神，结合了代码才理解到了它的精妙之处！

考虑研究我们的解的形态，并尝试将其规范化。

显然，我们的解当中必然存在一连串的大跳，然后接一段游泳小跳啥的，然后继续大跳啥的。

假如中间只接了游泳，那么考虑将这段游泳和后面的大跳交换位置，发现最终落点不变，但中间落点不一定合法。

如果中间落点不合法，则我们完全可以把部分游泳移动使之大跳落点恰好在岛屿的右边界。

如果合法则递归考虑。

假如中间直接了小跳，则小跳一定可以变大，让落点不变只需要让后面的跳跃同时缩短即可，发现这样做不仅会使答案不劣而且很有可能使它更优。

由于小跳是小跳，因此这个小跳一定可以恰好落在岛屿的左端点。

如果小跳和游泳同时连续存在，则小跳可以变大直到无游泳或大跳，则必然更优且划归为上述情况。

整理以上讨论可以得到：

存在最优解由以下结构构成：

1.不断大跳，然后游一段泳，然后大跳到一个岛屿右端点。

2.不断大跳，然后小跳到一个岛屿左端点，然后下一跳尽量跳远一点。

于是我们可以通过上述规则转移。

考虑对以每一个岛屿边缘为起点跳到以另一个岛屿的边缘为一次转移，由于最多只会有两种到达情况，因此总转移数是 \(O(n)\) 的，因此总复杂度是 \(O(n^2)\) 的。

为了实现轻松，我们可以让每一个转移，即大跳过下一个岛屿也作为状态，把状态数升为 \(n^2\) ，会好写很多。

官方题解说复杂度是 \(O(n^3)\) 的，但我觉得是 \(O(n^2log n)\) 的，但机房有人不信，有兴趣的同学可以精细实现。

2.Date Pickup

为什么这样的人也能有npy

并不易于直接计算，答案显然具有单调性，不妨考虑二分答案 \(ans\) 。

问题被转化成为了判断一个答案是否可行。

考虑如果他在 \(a\) 时刻收到了电召该怎么办？考虑我们在一开始先计划前往点 \(x\) ，则满足 \(dis[s][x] + dis[x][t] \le a + ans\)。

于是我们想到去找到所有计划第一个到达的点。考虑到达了这样一个计划目标点之后怎么办？

由于他刚走上一条边的时候也可能收到电召，因此一条边 \((u,v,w)\) 可以走当且仅当 \(w + dis[v][t] \le ans\) 。可以理解为刚下道就直奔 npy 家。

考虑找到这些边，由于我们会先到目标点，所以我们可以用目标点吧这些可走的边扩展出来，于是就得到了可走的子图。

检查这个子图是否有环以及最多能在里面逛多久。如果有环一直走环等电召，否则尽量走久一点，如果能挨到 \(b\) 以后则可行。

注意到他可以在家摆烂摆到再不去就赶不上来自 npy 在 \(a\) 时刻的电召为止最优。

我相信 Richard 的行为不值得提倡。