4.17 题

A Winding polygonal line

神仙构造。

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

复杂度 O(n2)O(n^2)

B Distinctification

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

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

所以考虑 BiB'_iBB 中第 ii 大的东西,于是要算的就是

AiB1+(Ai+1)B2+(Ai+2)B3+AiBiA_i B'_1 + (A_i+1) B'_2+(A_i+2)B'_3 + \cdots - \sum A_iB_i

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

C AUOJ 837 博弈

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

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

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

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

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

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

\