Codeforces-166-div2

刷小小号呢。

一次大好的 rank1 的机会就被浪费了，好桑心……

不过 rank5 也还不错的说？

Solution

A

水题，枚举即可。

由于这几天写 Haskell 于是顺手用 Haskell 来写 = = 发现手速更慢了。

B

水题。预处理出每个数至少要加多少次，统计每一行每一列的和即可。

C

构造。有很多种构造的说。

无解显然是 n < 3k 。

我的： 1 1 2 1 2 2 循环很多次，如果 k 是奇数那么就是 k k 1 1 2 1 2 2 k 。

另一种： 1 1 2 2 ... k k 1 2 ... k

D

据说 hash 挂的很惨。

其实 trie 很好的啦……不过我写的不是 trie ……我把所有字符串全部排了序，然后减去 LCP 的长度和即可。

E

这个题就不太简单了。

首先可以证明： (x, y) 可以变化到任意一个 (x + a, y + a) ，不管 a 的正负。做法如下：

(x, y) -> (y, 2y - x) -> (x, 2y - x) -> (ceil(x/2), y - floor(x/2))

可以发现， 这两个数的差仍然是 y - x ，而当 x > 1 时， ceil(x/2) < x ，所以我们最后一定可以得到 (1, y - x + 1)

接着另一个结论：若 x 是奇数，那么 (1, x) 可以得到 (1, ceil(x/2)) 。显然嘛。

然后引出终极结论： (x, y) 最后可以变成 (1, 1 + t) ，其中 t 是 y - x 最大的奇因子。而能产生 (1, a_i) 则要求 t 是所有 a_i - 1 的因子。

于是暴力枚举 t 即可。

situation

在家做笔记本没手感啊。

看完 A 这不水题一个么……速上 Haskell 发现好慢 T_T

看完 B 这不水题一个么……怒上 C++0x ……数组开小了 FST 了啊……哭瞎了啊……

看完 C 同上。随手 YY 一下即可。

看完 D 同上。第一想法居然是后缀数组？发现长度只有 1500 ？暴力建后缀数组吧 = =||

看完 E 发现不会做啊。YY 了若干久没啥好想法，发现没草稿本啊亲……于是只好用画图 YY 了。

结果乱 YY 一个结论居然过了全部样例？好吧就这样吧。

然后开始 cha 人。看了半天没想法，看着 E 题某人只判 t = 2 的情况，于是想 cha 掉，然后挂了 T_T 。截图如下，我多么希望网速能够慢一点啊。

others

XLk 和 xiaodao 开黑……然后两人的 DE 全挂了……

xiaodao 只做了 DE 。是懒得刷 ABC 吧。

liouzhou_101 似乎没搞出 E ？还是 D 用的时间太久了？

zrx 小朋友一开始说要做的，结果不知道做没做，我还不知道他 ID 呢。

然后没谁参加了……

nonsense

现在大号红了小号黄了小小号紫了 div1 的各个颜色都有了。