Difference between revisions of "2018 Multi-University, HDU Day 5"

From EOJ Wiki
Jump to navigation Jump to search
Line 42: Line 42:
 
* 若 $k \ne -1$,对于 $j \le c \le a_i$,用 $f(i,j,k)+1$ 更新 $f(nxt(i,c), j, k)$(已经拐了就只能下降了,但是也不能比拐之前的高度还要低)。
 
* 若 $k \ne -1$,对于 $j \le c \le a_i$,用 $f(i,j,k)+1$ 更新 $f(nxt(i,c), j, k)$(已经拐了就只能下降了,但是也不能比拐之前的高度还要低)。
  
这样的话我们成功地算出了形如 01236543 的情形。
+
其中 $nxt(i,c)$ 表示 $i$ 位置之后下一个出现 $c$ 的位置。这样的话我们成功地算出了形如 01236543 的情形。
  
 
接下来还要接一段,只要预处理一下后缀的上升子序列的情形(从后往前更新,倒过来看就是下降的),那么对于所有 $f(i,j,k)+suffix(i,k)$ 都刷一遍答案就好了。
 
接下来还要接一段,只要预处理一下后缀的上升子序列的情形(从后往前更新,倒过来看就是下降的),那么对于所有 $f(i,j,k)+suffix(i,k)$ 都刷一遍答案就好了。

Revision as of 09:55, 6 August 2018

卡常卡得真刺激。

Problem B

Solved by ultmaster. 01:15 (+)

题意:求一个数的所有只需要交换 $k$ 次以内的排列中,最小的和最大的。

题解:暴搜一下就好了。

Problem D

Unsolved. (-10)

Problem E

Solved by ultmaster. 00:49 (+)

题意:求一个圆挖掉若干个小圆,剩下的部分的周长。

题解:计算几何签到。判完圆的位置关系后,求交点,然后判断交出来的弧是优弧还劣弧(通过圆心连线的向量应该加在交点之间来判断)。因为 位置关系搞不清楚,调了好久。

Problem G

Solved by kblack. 00:57 (+)

题意:区间覆盖线段树,修改巨多,离线询问点值。

题解:一个区间按 ST 表拆成两个,按 ST 表更新反方向贡献回去就好了。

Problem H

Solved by ultmaster. 04:27 (+5)

题意:求一个序列中最长的形如 012365436789 的子序列。

题解:一看就是 DP,关键在于如何设计优秀的状态。区间 DP 大概是不大行的。我们考虑前缀。我们可以暂时不考虑后面的 6789,先考虑前面的这一部分的前缀,为了判断下一项最优是多少 / 可不可行,我们需要记住多少信息?比如对于 0123654,我们需要记住的是这个 3 和这个 6;比如对于 012,我们需要记住的是 2 而且没有碰到拐点。这样的话,很容易发现只要记住两维的信息($10 \times 11$,第二维还有一个不存在的状态),我们就可以推出下一个数字可不可行了。

形式化地说,记 $f(i,j,k)$ 为到第 $i$ 项为止,这一项必选,拐之前的那个数是 $j$,拐之后的那个数是 $k$,所能得到的最长答案。那么:

  • 若 $k=-1$,对于 $c \ge a_i$,用 $f(i,j,k)+1$ 更新 $f(nxt(i,c), c, k)$(继续上升)和 $f(nxt(i,c), j, c)$(把 $c$ 当作拐点)。
  • 若 $k \ne -1$,对于 $j \le c \le a_i$,用 $f(i,j,k)+1$ 更新 $f(nxt(i,c), j, k)$(已经拐了就只能下降了,但是也不能比拐之前的高度还要低)。

其中 $nxt(i,c)$ 表示 $i$ 位置之后下一个出现 $c$ 的位置。这样的话我们成功地算出了形如 01236543 的情形。

接下来还要接一段,只要预处理一下后缀的上升子序列的情形(从后往前更新,倒过来看就是下降的),那么对于所有 $f(i,j,k)+suffix(i,k)$ 都刷一遍答案就好了。

复杂度 1E8 刚好是满的。一定要注意初始化!初始化细节留给读者思考。

Problem J

Unsolved. (-5)