比赛地址

Go Home

因为从 $1\sim n$ 中选若干个数可以拼出 $[1,\frac{n(n+1)}{2}]$ 中的所有数,所以我们只要找到最大的满足 $\frac{n(n+1)}{2}\geq X$ 的 $n$ 即可。因为数据范围小所以可以直接枚举。

代码

No Need

把所有数从小到大排序,则可有可无的数一定是一段前缀。

设 $s=\sum_{j=1}^i a_j$,那么 $[1,i]$ 是可有可无的当且仅当不能从 $[i+1,n]$ 中选出若干个数,使得它们的和在 $[k-s,k-1]$ 间。

直接 DP 即可。复杂度是 $\mathcal{O}(nk)$ 的。

代码

NarrowRectangles

首先考虑一个暴力 DP。设 $dp_{i,j}$ 表示前 $i$ 个矩形,第 $i$ 个矩形的左端点在 $j$ 的最小代价。转移为

$$ dp_{i,j}=|j-l_i|+\min_{j-(r_{i-1}-l_{i-1})\leq k\leq j+(r_i-l_i)}\left\{dp_{i,k}\right\} $$

把 $dp_{i,x}$ 看成一个关于 $x$ 的函数,可以发现它是一个分段函数,从左往右斜率为 $-i,-{i-1},\cdots,-1,0,1,\cdots,i-1,i$。

于是只要用堆维护一下所有拐点,于是转移时根据 $l_i$ 的位置讨论一下即可。具体可以参考一下代码。

代码

HonestOrUnkind

先考虑无解的情况。当 $A\leq B$ 时,不友好的人可以都装成诚实的人,于是就判断不出来了。

于是有一个想法是找到一个诚实的人,再问他其它人就能得到答案了。

因为 $A>B$,所以可以考虑一个类似于摩尔投票法的过程。我们维护一个栈,每次询问栈顶当前这个人是啥,如果是不友好的就弹栈,否则把当前这个人入栈。最后栈顶即为诚实的人。

考虑正确性。我们分几种情况讨论一下:

  • 栈顶不友好,当前的人不友好:如果回答不友好则两人都没了,否则正常入栈。
  • 栈顶不友好,当前的人诚实:如果回答不友好则成功一换一,否则正常入栈。
  • 栈顶诚实,当前的人不友好:成功一换一。
  • 栈顶诚实,当前的人诚实:正常入栈。

可以发现最后不友好的和诚实的会有一些换掉了,剩下的诚实的一定会在上面,所以是正确的。

代码

最后修改:2020 年 09 月 16 日 09 : 47 PM