2014-2015 ACM-ICPC, Asia Tokyo Regional Contest
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$ 之后经过至少一次。求最小路程。
题解:一定是第一种情形。扫描线一下就好了。
图是从多校偷的。
Problem D
Solved by ultmaster. 01:57 (+)
题意:有若干柱子,要求打一个会反弹的炮,打到恰好 $d$ 米远的地方。至多反弹次数有限制。求最小速度。
题解:枚举至多反弹的次数。发射角度一定是 45 度以上占优,二分最小的可行角度。
Problem E
Solved by zerol. 03:09 (+)
题意:有一些互相垂直的街道,告诉你起始点和若干次经过一段路的方向,求可能的当前位置。如果刚好在转弯,那么方向可能是转弯前的也可能是转弯后的。
题解:分裂所有点,用 (x,y,d) 表示在 (x,y) 接下来要走 d,然后建图,要保证不能倒车。对于经过 dis 方向为 dir 有两种情况,分别是经过 dis-1 后方向为 dir 后再走一步或者经过 dis 方向为 dir。由于每次的 dis 很小,用 set 暴力一步一步走并去重然后检查合法性。
Problem F
Solved by zerol. 01:15 (+)
题意:求一个无向图上一定在最小生成树的边。
题解:先求出任意一个最小生成树。对所有非树边,把端点对应的路径上边权一样的边标记为不行,最后找生成树上行的边。
Problem G
Solved by kblack. 01:21 (+1)
题意:给一个合法的括号序列,每次翻转一个括号,要求再翻转一个括号使得序列仍旧合法,同时位置最左。
题解:( 翻 ) 很好做,寻找最左侧一个 ) 翻转即可,下面考虑 ) 翻 (。( 记为 +1,) 记为 -1,用线段树维护实时前缀和,我们只要找到最左侧的区间使得后侧全部 $\geq 2$ 的 ( 翻转即可。标记下放写错,演了自己。
Problem H
Upsolved by kblack.
题意:给定起点终点,不能走进 $N$ 个圆内,求最短路径长度。
题解:$N$ 只有 8,暗示了想怎么玩怎么玩。通过脑补我们可以发现,去除没有阻挡的显然情况,所有走的路径段只有三种可能:一段弧,两个圆的公切线,起/终点与圆的切线。我们把后两类线全部求出来,去除掉不合法的线段后,再在每个圆上用弧线连接相邻的合法点,要考虑其他圆使得弧不可用,这样就得到了一个点数 $O(N^2)$ 的图,随便跑啥最短路。
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 中二分查找。
没想到两个意识模糊的人还是在赛后把这道题过掉了。
另解:
$f(i,d)$ 表示在剩下 $i$ 个物品的时候超过对方 $d$ 点能量时所能获得的最大收益,记 $s_i$ 是最后 $i$ 个物品的价值和。
得到转移 $f(i,d) = \max \{s_i - f(i-1,-d -r_i),f(i-1,d-1-r_i)[d > 0]\}$
由于 $d$ 的取值很多而 $f$ 的取值很少,而且在 $i$ 一样的情况下,$f$ 关于 $d$ 具有单调性,反转函数 $f$ 的参数 $d$ 和值。设 $g(i, v)$ 为剩下 $i$ 个物品时获得 $v$ 收益时所需要的最小能量差。
那么有转移 $g(i,v)=\min\{\max\{1+r_i+ g(i-1,v),1\}, -(g(i-1,s_i-v+1)-1)-r_i\}$ ,其中后面一项中的 $+1,-1$ 是因为那部分要取 $\max$。