GCJ 应该是可以骗到一件衣服的 - -

POJ 的奖品居然没骗到 >__< 做到一半机房断网了于是 #11 真是不能更爽

Google Codejam Round 2

A

一开始看错题了……

显然最后每个人的路线是不相交的，允许包含。于是上车点与下车点构成了括号序列。

然后用栈处理一下就好。

B

假设第一步是二分吧（感觉有不用二分的方法），那么我们的问题就是判定一个人最好/最坏排名是多少。

共有 $T$ 个人，令 $f(x, T)$ 表示能力排名为 $0 \leq x < T$ 的人最差排名是多少。考虑 $x = 0$ 的情况，易得 $f(x, T) = T - 1$ 。否则，最差情况下， $x$ 会被打败，而且下一轮中 $x$ 的能力值排名是所有可能的值中最大的。 $x$ 之前有 $x$ 个人比他强，进入败者组的人至多有 $\lfloor\frac{x - 1}{2}\rfloor$ 个人，所以有 $f(x, T) = \frac{T}{2} + f(\lfloor\frac{x - 1}{2}\rfloor, \frac{T}{2})$ 。

最好情况类似，令 $g(x, T)$ 表示 $x$ 最好可以打败多少人，可以得到当 $x = T - 1$ 时有 $g(x, T) = 0$ ，否则有 $g(x, T) = \frac{T}{2} + g(\lfloor\frac{x + 1}{2}\rfloor, \frac{T}{2})$ 。

python 真是极好的。

C

根据 LIS 和 LDS 序列可以构出一个拓扑图，一条有向边 $s \to t$ 表示 $x_s < x_t$ 。我们要求这个拓扑图的一个拓扑序列，满足 1 出现的位置尽量靠前，在此基础上， 2 出现的位置尽量靠前 etc 。

直接上伪代码吧 = =||

def dfs(x) : # 要使得 x 尽量先出来
	if x 已经在拓扑序中 :
		return
	ys <- 所有要使得 x 出来必须出来但是还未出来的点
	sort ys increasingly
	for y in ys :
		dfs(y)
	Q += [x]

Q = []
for i from 1 to n :
	dfs(i)
# 然后 Q 就是要求的拓扑序

这样做显然是 $O(n^2)$ 的。

其实有个更好写的 $O(n \log n)$ 的方法。反向建图，每次选择标号最大的点出来，相当于求出逆拓扑序。

D

计算几何，哈哈哈哈。

POJ Challenge Beta 1

有中文题面，这真是极好的。

A

由 $a(a + b) = c^2$ 可得 $a = \frac{\sqrt{b^2 + 4c^2} - b}{2}$ ，可以发现只要 $\sqrt{b^2 + 4c^2}$ 为整数即可，奇偶性可以保证。

令 $b^2 + 4c^2 = d^2$ 得 $b^2 = (d - 2c)(d + 2c)$ 。易知 $d - 2c \leq 4$ ，所以枚举 $d - 2c$ ，看看是否存在整数 $c$ ，如果存在 $c$ 就可以直接求 $d$ 然后求 $a$ 了。

为啥 $d - 2c \leq 4$ ？当 $b$ 为奇数时显然 $d - 2c = 1$ ，当 $b$ 为偶数时 $d - 2c = 2, d + 2c = \frac{b^2}{2}$ 和 $d - 2c = 4, d + 2c = \frac{b^2}{4}$ 中至少有一组可行解。（其实继续分析下去可以直接找到规律，只不过这样已经很好写了于是就直接写了。）

B

一个 $O(n^3)$ 的 dp 是显然的， $f_{i, j}$ 表示区间 $[i, j]$ 的最优解，枚举根进行转移。

然后我就不会了 = =

不过我是怎么在 20min 过的呢……因为我看到有人（wkn ？）在 15min 过了，于是觉得这个题应该是可做的，于是猜了个结论： $f_{i, j}$ 的根只可能是 $i$ 或 $j$ 。随机生成了几组极限数据试试发现是对的……然后就没有然后了……

感觉如果按照 dp 的一般优化思路去想的话应该也是可做的。

C

如果一个数同时出现在两组限制中，那么这两组限制必定是连续的，也就是最后的限制就是若干条链，每条链分别搞搞就好了。

感觉好多细节啊不想写啊。你要牛逼就写 PQ 树去吧哈哈哈哈。

D

std 的想法大概是 dp 吧， $f_{i, j}$ 表示最后一条线段是 $i \to j$ ，转移的话利用极角序优化一下就好了。

我写的另外一种方法，但是 WA 了。

考虑枚举最低点。两边点到这个点的斜率递增，求出斜率后直接 LIS 。为啥我会错……难道老了连 LIS 都不会了么 T_T

E

果的数据结构题。

依次 dfs 每个点。对于 $(a, b)$ ，我们要求所有的 $(c, d)$ 数目使得 $(c, d)$ 能够覆盖 $(a, b)$ ，我们在 dfs c 的时候在 d 点放个标记，那么在 dfs a 的时候就相当于查询 b 到根的路径上有多少个标记。显然 dfs 序 + 树状数组。

F

显然是原题。

半平面交是 $O(n^2 \log n)$ 的吧。似乎我估错复杂度以为是 $O(n^3 \log n)$ 的就没写了 →_→

模拟退火 balabala 不知道怎么样。你要牛逼就写 Voronoi 图去吧哈哈哈哈。