edward_mj

2014北京邀请赛 Prob G Great Escape

做了才知道为什么NowOrNever交那么多次都没过……

首先应该要想到的做法是给每个楼之间的区间分配飞多少层楼的高度。

然后很直接的想法就是每次取涨一层楼代价最小的那个区间来加一的高度，直到这个涨的代价大于1.0/w，或者涨满L这么高。

但是L有10^9，这样做肯定是要TLE的。那么我们可以二分这个+1的代价，然后贪心地去算，然后判断楼层是否超过L就可以了。

不过我的做法更暴力一点，先直接按连续的去做了，差分变成求导，求导以后不难看出这个导数是单调递增的，由于函数是连续的，可以避免很多取整、讨论。于是通过实数的模型可以得到每个区间占用楼层的近似初值。有了这个近似初值，就可以用上面最直接的那个想法通过这道题目。不难证明复杂度是 n lg n的。

代码

SRM 620

难得踩楼爷啊……

250

直接辗转相减法，把所有中途的pair放进set，查一查就出来了。

500

给n个元素，每个元素都包含m个关键字的value，再给一个排序后的结果，问是否存在一种对关键字重要程度的排序，使得按多关键字排序这n个元素以后，得到某个给定的顺序。

按重要到不重要的顺序贪心取这个关键字。正确性的关键在于，如果有两个关键字当前都可以取，那么取了其中一个以后，另一个在之后任意时刻都是可以取的。

800

01域下的高斯消元求方案数。直接算秩，2^(元素个数-秩)就是答案。当然还要小心无解的情况。

[ZOJ 3199 Longest Repeated Substring] 分治、扩展KMP

链接

给定一串S，令S = *xx* (其中*为通配符)
问这个x最长的长度能是多少。

以前用罗穗骞论文的方法按后缀数组枚举长度做的。但是那个需要ST表，空间是O(n lg n)。最近从叉姐那里学会了新姿势，可以用分治的思想做，只要O(n)的空间。

具体想法是每次把字符串分成两半，分别算两边的答案。

对于跨越中间边界的，设中点为 $S_{mid}$ ，那么枚举答案的长度L，然后因为他跨越边界，那么一定包含 $S_{mid}$ 。
因为答案长度为L，那么要么 $S_{mid + L}$ 在答案中，要么 $S_{mid - L}$ 在答案中。

不失一般性假设 $S_{mid + L}$ 在答案中，那么肯定存在一段 $S_{i..i+L-1} = S_{j..j+L-1}$ ，其中 $i \leq mid \leq i + L - 1, j \leq mid + L \leq j + L - 1$ 。

显然 $S_{i..i+L-1}$ 就是我们要求的目标串。

再观察一下，会发现这个条件等价于 $lcp(mid, mid+L) + revlcp(mid, mid + L) - 1 \geq L$
其中revlcp是指往前的lcp

最终发现，对于跨越的情况，我们只要求得lcp(mid, x)和revlcp(mid, x)的函数值即可。而这个显然可以通过拓展KMP处理出来，具体做法就是令 $T = S_{mid .. n} + S_{1..n}$ ，对T求拓展KMP，再对边界取一下min，反的可以转化成正的求解。

至此，这题得到了解决。
时间复杂度O(n lg n)。
空间复杂度O(n)。

代码：https://gist.github.com/edwardmjm/2b88d649ced1d7ce9a99

地址
昨晚翻出酒神的演讲从头到尾听完了。虽然镜头很抖，酒神确实也不怎么精于演讲，但还是发现了很多有共鸣的地方。
“我是一个很注重结果的人”
“我去打比赛就是为了以后有事情可以吹牛”
“对不起，这场比赛我要赢”
“如果你觉得失败就像砍掉你一条腿一样，你肯定是无敌的”
“一个人的成功在于不断地经营自己的优势”
“成功的人总是盲目自信的”
“我也试过很多次组队，也失败过很多次”
“我觉得我就应该打中路solo”
“一开始我想着自己怎么打就行了”
“我开始观察队友在干什么”
……

静态KD树通用模板

今天在opencup上遇到了一个三维区间询问的题。

虽然知道KD树可以做，自己对于二维的也随便写。但是三维的就没怎么写过了。

于是今天下决心写了一个静态KD树的通用模板。于是就有了这个东西。

KD树还是很强大的，还能做一些二维线段树不能做的东西。在想不到比较优美的做法的时候，直接上KD树往往能轻松AC。

模板链接：https://gist.github.com/edwardmjm/11118130