Google Codejam Round 2 && POJ Challange Beta 1
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 图去吧哈哈哈哈。