4.17 题

A Winding polygonal line

神仙构造。

考虑拿凸包上一个点 $A$ ,然后每次找一个点 $B$ ,如果是 L ,则使得剩下的所有点都在 $AB$ 的左侧,然后连过去即可,否则就使得所有点都在 $AB$ 右侧。不难发现这样每一轮都一定能找到剩余点继续,且由于所有点都在一侧,显然不可能出现线段相交。

复杂度 $O(n^2)$ 。

B Distinctification

考虑给定一段序列怎么算出答案。不难发现对于一个 $A_i$ ,我们一定会找到一个最大的 $k$ 满足 $[A_i,A_i+k-1]$ 的数的个数正好是 $k$ ,然后把这些数进行操作使得这些数互不相同。

我们定义一个方案的权值为 $\sum_i A_iB_i$ ,那么最终需要花费的代价是 $W_e - W_s$ ,而我们希望这个代价尽量小,也就是最小化最终状态的代价。而且不难发现,在题目的条件下,一定可以将 $A_i,B_i$ 变成 $k,B_i$ 其中 $k \in [A_i,A_i+k-1]$ 。具体为啥想一想就会发现这个方案非常容易构造,可以先任意得到一个每个数不同的方案,然后一个一个归位即可。

所以考虑 $B’_i$ 为 $B$ 中第 $i$ 大的东西,于是要算的就是

于是我们就可以 $O(n)$ 回答一次询问了。然后就是考虑插入一个 $(A_i,B_i)$ ,我们可以拿 set 维护连续段,即之前说的 $A_i,A_i+k-1$ 这种段每个段拿一个权值线段树维护 $B_i$ ,同时维护 $\sum iB_i$ 这个东西,于是插入一个数后就会把一些连续段合并,合并直接上线段树合并即可。复杂度 $O(n\log^2 n)$ 。

C AUOJ 837 博弈

我们倒着考虑这个过程,来手玩一下样例 5 20 3 输出 3 4 3 4 3

考虑什么样的状态是终止状态,显然 0 0 0 0 0 会导致结束。然后,

  • 当 $m$ 仅剩 $2$ 时(此时 $2$ 作为提出者),无论怎么提出方案,必然有人会获得 $0$ ,这种人会否决这个方案,于是会进入状态 0 0 0 0 0
  • 当 $m$ 为 $5$ 时(此时是 $1$ 作为提出者),可以提出方案 1 1 1 1 1 ,这样必然优于继续下去的 0 0 0 0 0 ,于是这就是一个终止状态。
  • 当 $m$ 为 $8$ 时(此时是 $5$ 作为提出者),无论怎么提出方案,都会有人只得到 $1$ ,他会否决方案,因此终止态一定仍然是 1 1 1 1 1
  • 当 $m$ 为 $11$ 时(此时 $4$ 作为提出者),他首先肯定会给每个人相较于之前的方案多分配一个,这样可以保证大家都同意这个方案,然后剩下的肯定会私吞,于是就是 2 2 2 3 2
  • 当 $m$ 为 $14$ 时,此时必然会有人只能得到 $2$ ,会否决方案。
  • 当 $m$ 为 $17$ 时(此时 $2$ 为提出者),他首先肯定会相较之前多分配一个,然后剩下的私吞,于是就是 3 4 3 4 3 了。
  • 当 $m$ 为 $20$ ,此时会被否决。

所以最终答案就是 3 4 3 4 3

然后按照这样的思路去模拟,就有了一个 $O(\frac m n)$ 的优秀做法,可以获得 $80$ 分。

考虑优化这个,因为第一步之后每一步都会往前推 $\lfloor \frac n k \rfloor$ 个人,因此循环节是 $O(n)$ 的,所以直接推循环节即可,复杂度 $O(n)$ 。

文章作者: yijan
文章链接: https://yijan.co/2021/04/19/417-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog