2014-2015 ACM-ICPC, Asia Tokyo Regional Contest

From EOJ Wiki
Revision as of 15:07, 17 November 2018 by Kblack (talk | contribs) (→‎Problem G)
Jump to navigation Jump to search

Problem A

Solved by zerol. 00:23 (+)

Problem B

Solved by zerol. 00:12 (+)

Problem C

Solved by ultmaster. 00:31 (+)

题意:从一条直线的一端走到另一端,有若干对关系 $(c_i, d_i)$ 表示 $c_i$ 必须在 $d_i$ 之后经过至少一次。求最小路程。

题解:一定是第一种情形。扫描线一下就好了。

Screen Shot 2018-07-29 at 12.15.57 PM.png

图是从多校偷的。

Problem D

Solved by ultmaster. 01:57 (+)

题意:有若干柱子,要求打一个会反弹的炮,打到恰好 $d$ 米远的地方。至多反弹次数有限制。求最小速度。

题解:枚举至多反弹的次数。发射角度一定是 45 度以上占优,二分最小的可行角度。

Problem E

Solved by zerol. 03:09 (+)

Problem F

Solved by zerol. 01:15 (+)

Problem G

Solved by kblack. 01:21 (+1)

题意:给一个合法的括号序列,每次翻转一个括号,要求再翻转一个括号使得序列仍旧合法,同时位置最左。

题解:( 翻 ) 很好做,寻找最左侧一个 ) 翻转即可,下面考虑 ) 翻 (。( 记为 +1,) 记为 -1,用线段树维护实时前缀和,我们只要找到最左侧的区间使得后侧全部 $\geq 2$ 的 ( 翻转即可。标记下放写错,演了自己。

Problem H

Problem I

Upsolved by ultmaster & zerol.

题意:有若干巧克力按顺序出现,吃第 $i$ 块巧克力可以获得 $r_i$ 的能量和 $s_i$ 的收益。两个人轮流操作。每个人有两种选择:1. 吃掉;2. 花费 1 点的能量轮空,让对方操作。现在你和对方分别有 $a$ 和 $b$ 的能量,求最优情形下双方收益。

题解:显然,巧克力要么直接吃掉,要么在能量比对方多的时候花费 1 点的能量给对方吃掉。我们可以注意到,只有双方能量的差值才有意义,因为互相让来让去会消耗掉所有相等的部分;最后当一方的能量降为 0 时,还是花费了 1 点能量。

考虑这样一种记忆化搜索 $f(i,d)$ 表示在我已经累计了 $d$ 点能量差值(比对方多 $d$)时,面对还剩 $i$ 个的游戏局面,我能获得的最大收益。那么 $f(i,d) = \max \{$ 剩下的 $i$ 个物品的总价值 $- f(i-1, -t - r_i), f(i-1, t-1-r_i) \}$。边界条件是 $f(0,x)=0$。答案是 $f(n,a-b)$。

第二维可能的取值太多了,难以记忆化。但我们不难发现 $f(i,d)$ 在取值上的单调性,$d$ 越多,拿到的收益肯定越大,而这个变化的点不会太多。考虑自底向上,每一层,先求出我们关心的关键点,然后算出所有关键点的值,删除掉不必要的点。求值的时候就在下一层的 set 中二分查找。

没想到两个意识模糊的人还是在赛后把这道题过掉了。