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$。

zerol：困惑于最大值最小值的问题，其实就是计算出某一层的值后，某一个价值对应的能量差范围也就获得了（最大值是价值+1 的能量差-1）。