前言

别看这标题非常像一个神秘的叙事文，但是实际上这是篇考试总结 + 类日记。

Day 1 \(\Leftrightarrow\) 5.28

Day 1

补了昨天考试的题。

T1 智障了。不难发现如果找到全局最优点对，剩下就只有这两个点到根这两个路径上的点不是这个答案，然后扫两边就行了。

T2 神仙 DP。考虑到我们可以把一个 \((n-k,m-k)\) 的方案掰到 \((n,m)\) 上，具体就是第一个向量的横坐标 \(+k\)，最后一个向量的纵坐标 \(+k\)。因为任意一个不重向量组加起来等于 \((n,m)\)，最后总能重排成有序的状态使得合法，所以加入可以没有顺序，使用 01 背包可以做到复杂度 \(O(n^4)\)。因为是不重向量组，所以我们要踢掉 \(\gcd(n,m)\not=1\) 的向量。

因为我们已经可以掰方案了，所以我们这里可以贪心，选小的越好，所以对于一个向量 \((x,y)\)，我们一定是选完 \((\leq x,\leq y)\) 的向量再选这个，否则我们可以替换使得至少某一维更小。打出来表有 600 个向量满足所有条件。

然后有一个结论就是凸包上整点个数是 \(O(n^\frac{2}{3})\)，不知道为什么。但是算出答案确实只有最多 \(290\) 个点。这个时候的背包理论上就是 \(O(n^\frac{8}{3})\)。

交换答案和某一维的状态，设 \(f_{i,j}\) 是选 \(j\) 个向量，使得 \(\sum_p{x_p}=i\) 的最小的 \(\sum_q{y_q}\)。转移是简单的。此时复杂度为 \(O(n^\frac{7}{3})\)。最后记得做一个二维前缀 \(\max\) 就行了。

T3 nxbj，等我做 DS 的时候再说。