一次多好的进前五的机会啊，居然被浪费了。

最近 FST 特别多，这状态怎么搞腾讯的比赛咯。

最后 #39 不算很坏的结果，但起码 E FST 了很桑心。

Solution

A

先把整个序列用 ab 染好，最后 \(k - 2\) 个从 c 开始赋。

当然，搜索也是可以的。

B

可以发现前 \(k\) 个与后 \(n - k\) 个是无关的。由于 \(k\) 特别小，直接搜索 \(2 - k\) 个值即可。复杂度 \(O(k^k)\) 。

C

不妨考虑 \(p_n\) 应该是多少。令 \(x\) 表示最小的不小于 \(n\) 的能表示成 \(2^k - 1\) 的形式的数，则 \(p_n\) 的最优解显然就是 \(x ^ k\) 。继续考虑下去，可以发现对于 \([x^n, n]\) 内的每个数我们都可以找到唯一的对应关系。剩下的数递归就好。

D

不妨设为有根树。考虑枚举 \(a\) 到 \(b\) 这条路径的 LCA \(t\)。我们要从 \(t\) 的子树中选出两个点，使得它们的 LCA 是 \(t\) 。这样的方案数是有 \({size_t \choose 2} - \sum_{x \textrm{is a child}} {size_x \choose 2}\) 。 \(t\) 的子树外我们任取两个点即可，方案数为 \({n - size_t \choose 2}\) 。考虑到如果两条路径分布在不同的子树，这种情况我们会计算两遍，所以我们还要把这种情况剪掉。然后就没了。

E

一个显然的数位 dp 。我们预处理两个值 \(f_i, g_i\) ，分别表示所有的 \(i\) 位幸运数相邻两个的积的和以及所有 \(i\) 位幸运数相邻两个的和的和。于是我们有如下递推式：

\[f_{i + 1} = 2 f_i + 65 * 100^i * (2^i - 1) + 11 * 10^i * g_i + (\frac{10^i - 1}{9} * 7 + 4 * 10^i) * (\frac{10^i - 1}{9} * 4 + 7 * 10^i)\] \[g_{i + 1} = 2 g_i + 22 * 10^i * (2^i - 1) + 11 * \frac{10^{i + 1} - 1}{9}\]

\(f\) 的递推式可以这么想：任意三个数 \(x, y, A\) ，我们有 \[(x + A)(y + A) = A^2 + (x + y)A + xy\]

那么当从 \(f_i\) 递推到 \(f_{i + 1}\) 时，我们需要加上 \(2^i - 1\) 个 \(A^2\) ， \(g_i\) 乘上 \(A\) ，以及 \(f_i\) 。 \(A\) 有两种取值，一种是 \(4 * 10^i\) ，一种是 \(7 * 10^i\) 。最后再考虑一下多出来的一个积即可。

\(g\) 的类似。

求出 \(f\) 和 \(g\) 后，剩下的就简单了。从前往后扫，每遇到一个 7 就计算对答案的贡献。

situation

今天真心不顺。

先是卡 A 卡了 12 min 。我想写贪心，但是各种怕特判，于是决定写搜。但是搜的一个地方忘记特判导致挂了……

看了 B 后觉得蛮简单的，写完后 A 掉。

看 C 。感觉这个题应该蛮简单的，但是没灵感，遂决定放到一边去。

看了 D 后第一想法是点分治。后面一项分什么治啊，直接 dfs 不就好了吗。我分了好几种情况，交了后发现 WA 了。怒决定写拍。发现拍比正解还难写啊。写完后发现我少考虑了几种情况。经过情况的合并后发现就两种情况嘛。和暴力拍了 20 以内的无误后交了。

然后转过去看 C 。第一想法是一位一位的来，然后就突然想到配对了。 \(2^i\) 显然是和 \(2^i - 1\) 配对嘛。按照这个思路下去就想到了那个构造，于是就好了。

现在大概还剩 50min 。发现 E 有人过我就去看了一下 E 。看完后瞬间就有想法了，于是推了一下公式后发现是可做的，怒写数位 dp 。写着写着发现只有 10+ min 了，我还没开始调试呢。最后在 1：58 的时候交了一个上去，过了 pretest ，对不对只能听天由命了。

结果 AE FST 了。如果任意一个都没 FST 的话应该可以红的。幸亏过了 D 。不然后果不堪设想呢。

最后 #39 被 liouzhou_101 怒踩。按照这 FST 率下去我真就只能专业算法三十年了。要搞 ACM 的话就找一个代码能力强的吧。

others

wjmsbmr 直接 #1 ，好强大……（现在 wjmsbmr 已经超过我大号了）

liouzhou_101 #38 。

只要 E FST 的人都没有好下场。

感觉第一题蛮好 cha 的。只可惜我没时间了。

感觉今天的 ABC 是主流吧。 squarefk、vfleaking、flydutchman、秋锅都是前三题，只不过速度差异有点大。

大叔只过了前两题，顺利跌回 div2 。

nonsense

今天腾讯打电话过来说进了区域赛了，到时候可以去免费深圳玩玩～

本来就只打算拿件 T-shirt 的。600 挂了就挂了吧。

或许按照这个趋势下去，我有淡出 ACM 届的趋势？还是专注算法三十年好了。

Solution

300

裸贪是不对的。

于是写 dp 吧。 \(f_{i, j}\) 表示前 \(i\) 个字母中，保留 \(j\) 个字母所组成的最优的 S 串，以及在 S 串最优的前提下最优的 T 串。转移枚举这个字母取不取就好了。

开黑什么的，还是不要搞的为好。

600

考场上写了个莫名其妙的搜索，当然是 FST 的命运。

考后想高斯消元应该可做啊，于是随手写了个高斯消元。连样例都没调，连我自己都觉得这是错的，结果发现居然过了？我勒个去。

首先特殊情况是 \(n > m\) 其中 \(m\) 表示有多少个已确定的元素。在这种情况下，一定存在一行一列使得这一行一列上没有已确定元素。于是除这一行一列外的其余的元素随便填，到最后还剩下这一行一列的时候，再枚举每行每列的和是多少，那么每个元素的值都会确定，并且一定存在一组可行解（显然），所以答案就是 \(10^{n^2 - 2n + 2 - m}\)

\(n \leq m\) 时的情况比较难处理。不过说到高斯消元大家应该就知道这题该怎么做了。为了解决 10 不是质数，我们利用 CRT 分解下就好。一行一列相等，这个可以表示成一个方程。一个变量的值确定了，我们也可以把它表示成一个方程组。那么共有 \(n^2\) 个未知数，有 \(n^2 + m\) 个方程。去掉其中线性相关的方程后，答案就是模的自由元次方。再判判无解什么的就好。

1000

看完题的第一眼觉得这是水题。仔细想想后发现不会做。经过文学巨匠 wzy 教导后觉得这题怎么还是水题，写完后发现这想法是错的，重新想发现是神题，写了好久总是过不了，调啊调调啊调调了一下午终于发现错误了—— LCM 要用 long long 存……我的天啊

看完题的第一想法是对每个不同的基分开统计。于是我们要求当 \(x\) 从 1 取到 \(A\) ， \(y\) 从 1 取到 \(B\) 时，共有多少个不同的 \(xy\) 。其中 \(A\) 的范围很小，只有 30 。 \(B\) 的范围是 \(10^9\) 。

文学巨匠的方法如下：对于一个 \(x\) ，它最小的质因子为 \(d\) ，则 \(x\) 对答案作出的贡献是 \(xB - \frac{xB}{d}\) 。加起来就好。显然这是错的可是我居然没发现。

考虑容斥。暴力 \(2^A\) 的容斥显然是不行的。于是考虑将若干个类似的状态一起表示出来。假设一个数 \(n\) 可以同时被表示成若干个 \(xy\) ，则 \(n\) 一定是所有 \(x\) 的公倍数。于是我们可以设计一个 dp ： \(f_{i, j, k}\) 表示前 \(i\) 个数中，我们选取了 \(j\) 个数，这 \(j\) 个数的 LCM 为 \(k\) 的方案数。 \(f\) 的转移很简单，枚举这个数字选不选就好了。由于 \(n\) 要能被表示出来的话，一定有 \(\frac{n}{\min \{x\}} \leq B\) ，于是我们可以从大往小 dp ，每选中一个数，那么它一定是已选中的数中最小的，在这个时候计算方案数即可。

一个小小的优化是对于只包含前若干个质数的数用 dp ，其余的数仍然爆搜。

然后就可以过了。

situation

开了 300 后感觉这是个水题啊，于是 YY 了个贪心，大概就是把上下的绑在一起，用一个栈处理一下。但是这样做是过不了样例的。瞬间想起了 dp 。然后就只有 260+ 分了。看起来样例蛮有良心的。

penicillo 你 299.80 分是什么心态。

然后开 600 。看完后第一想法是 \(n\) 大的话很好处理， \(n\) 小就不好搞了。于是我决定写搜。我的方法是找一个空格子，使得这个空格子所在的十字内的已选格子尽量少。然后爆搜出一个小矩形的，这个矩形的大小具体有多大我也不知道 = =|| ，但是肯定很小就是了。对于其余的格子，我猜解的数目等于 10 的自由元次方，但是这是错的 T_T 于是光荣 FST 了。

写了正解后发现正解比爆搜还好写些，什么心态。

1000 看完题目就溜了。

最后过了 300 #90 。由于是小号所以仍然可以涨 LOL 。

others

各种奇葩不忍直视。

tourist 前两题都好慢的说，但是靠 cha 人 cha 到了 #3 真是不忍直视……

有人只交了第一题 FST 后仍然有 300 分，丧心病狂。

wuzhengkai 被我怒压 0.03 分……

大部分人是过了第一题，scottai #205 edly #209 xujie #350

target 君 tomek 居然 #375 ，只交了 140+ 分然后怒 cha 错三个。

lyrically 被 cha * 1 FST * 1 最后靠 cha 人没爆零。

cgy4ever FST * 1 加上 cha 错一个导致爆负，太可怕了。

大叔又一次爆零了……但是令人惊悚是……他……居然……涨了……

没 TeX 心里痒痒的，用的真心不方便。其实用 TeX 的一大理由就是它的公式。显示的很漂亮。偏偏干这一行的公式比较多，特别是在复杂度那一块，没哪些题是不需要涉及到复杂度的。于是痛下决心看能不能支持 TeX 呢？首先可以用 MathJax 。但是 MathJax 太慢了，而且占网速，总之我不喜欢……

于是搜索一堆东西，首先对 Pandoc 有期望，然后发现不会用。后来在本地看到一个叫做 Marutex 的东西。 Maruku 是 jekyll 用的 markdown 渲染器。Marutex 会不会支持 TeX 呢？让我们拭目以待。

事实证明，在 blahtex 的帮助下，Maruku 是可以支持 TeX 公式的。 Blahtex 是一个转换器，调用了系统的 TeX 解析器，利用 dvips 转成 png。初看起来效果确实是不错。由于 png 支持透明，公式就像是普通文字，这点尤其舒服。

但是，很囧的一点，blahtex 生成的图片背景透明，文字是黑色的，而我 blog 背景默认也是暗色调的，因此公式看不太清，这点特别囧。于是我们有两种解决方案： 1. 换一个 blog 主题 2. 改动 png

由于这个主题是我比较满意的，特别是背景我特别喜欢（我个人比较喜欢这个风格的画），所以决定使用第二种方案，改动 png 。

由于最终免不了调用 TeX 的解析器，所以我们可以直接在 TeX 源文件上做文章。我的第一想法是用 color 函数，直接把字体颜色改成白色。看了 help 后发现可以直接用命令行参数来设置。由于我不知道 Maruku 在哪里设置 blahtex 的参数，于是我决定自己写个程序来实现。这就不免涉及到外部程序的调用。

据我所知，一个程序调用了外部程序，则被调用的程序的 stdin、stdout、stderr 均会继承父程序的。可是我写了程序后发现明明 stdin 被继承了，可是仍然输入不进。一个不到 1K 只有 20- 行的程序我看了好久硬是没看到哪里有问题。最后发现， execve 的第二个参数这个数组的第一个元素必须和第一个参数一样……浪费了好多时间囧……

中间有个插曲，某一次我在生成 png 的过程中，只生成了一个 hash 用的 txt ，png 没有生成。结果下次启动 jekyll 的时候总是报错，我一个一个包的排查最后发现把某个临时文件夹清空就好了。

好的，现在可以调用外部程序了。可是字体颜色怎么还是黑色呢？经过不断努力地尝试，我发现了原因： blahtex 会使用一个叫做 preview 的包。这个包会覆盖 color 函数所设置的颜色。于是我干脆就不使用 preview 这个包了。发现 jekyll 不断报错，实在没办法了我就只好去看 Maruku 调用 blahtex 的实现。又参考了一堆的 help ，原因是： blahtex 需要 preview 这个包才能提供生成的 png 文件的尺寸，而 Maruku 需要 blahtex 提供尺寸来进行 png 的缩放。

然后我又蛋疼的去查如何获取一个 png 的尺寸。又准备写程序了 = =||

最后实在无聊，我把直接修改 html ，把 html 代码中和 png 大小相关的东西全部删掉，发现 png 能够正常显示。那就这样吧。于是最后我决定直接把 Maruku 中所有和 png 大小相关的代码直接删掉。似乎终于可以了？看一下效果。

效果

这是传说中的行内公式： \(O(n \log n + n \sqrt{n})\) ……应该没大 bug 吧。再看看所谓的行间公式：

\[1 + 2 + \dots + n = \frac{1}{2} n(n + 1)\]

好吧就这样吧。

eggache

蛋疼是没有上限的。我又遇到了一个问题，github 仓库显然没有 blahtex ，如何在访问 github 的时候能看到这些图片呢？

于是最蛋疼的事是：我不得不新建一个 repo ，用来保存 blog 的源代码，然后原来的 repo 只存放生成的 html 以及图片。也就是说原来是 github 渲染 html ，现在是我上传 html 及其相关文档上去，github 只负责显示了。所以每次更新文章很蛋疼的：

git add *
git commit -m "xx"
git push origin master
jekyll --no-auto ../roosephu.github.com
cd ../roosephu.github.com
git add *
git commit -m "xx"
git push origin master

不过有了 TeX 的支持还是很不错的。

纯粹试试 TeX 的。

不知道 github 支不支持 blahtex 诶。

传说中的行内公式 \(O(\sqrt{n} \log n \frac{n}{m})\) 。再来一个？ \(O(n \sqrt{n})\) 。

传说中的行间公式： \[f(n) = \sum_{i = 1}^n i\]

XHR 问我关于动态 MST 的问题，于是找论文看到一个很神奇的 O(sqrt(m)) per update 的方法。把思路简单说一下吧。（你可以简单地把这篇文章看成是翻译 = =||）

原论文标题是 Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications ，作者是 Greg N. Frederickson 。

保证每个点的度

保证每条边的权为正，这是显然的。

首先要构造一个图，使得和原图的 MST 相同，且保证每个点的度不超过 3 。

原图 G(V, E), \|V\| = n, \|E\| = m ，新图 G'(V', E'), \|V'\| = m, \|E'\| = m ，做法是将原图中的每个点拆成 D 个点（D 表示这个点的度），这 D 个点形成一个环，环上边的权为 0 ，原图的每一条边就可以对应新图一条边，而且任意两条原图的边不会占用同一个新图的点，可以保证每个点的度不超过 3 。

维护的值、可能的操作

z：块的大小

块状树的构造：

def csearch(v) :
    clust = set()
    for u in child[v] :
        clust = cluse \| csearch(u)
    if len(clust) > z :
        # find a new clust
        return set()
    return clust

E[i, j] ：表示所有连接第 i 个块和第 j 个块的边

minE[i, j] ：表示 E[i, j] 中权最小的边

delB(i) ：删除第 i 个块。复杂度 O(z) 。

addB(S) ：建立一个块，块内的元素集合为 S 。复杂度 O(z) 。

delE(x, y)：删除树上连接 x 和 y 的边。如果这条边连接两个块，直接无视。否则先把两个点所在的块删除，然后和相邻的某个块合并，如果合并后的块大小超过某个值，再分裂。所有访问到的块为常数个，复杂度 O(z) 。

addE(x, y) ：添加一条连接 x 和 y 的边，然后试图合并两个块。复杂度 O(z) 。

由于度数限制，每个操作的复杂度均为 O(z) 。

O(m^{2/3}) per update

我们用块状树维护 MST 。

有四种可能的操作：减小树边的权，增加非树边的权，减小非树边的权，增加树边的权。前两种总是可以忽略的。

对于第三种情况，直接查询最大的树边，有可能的话就把它替换掉。替换就是先删除一条边，再添加一条边。

对于第四种情况。我们先把这条树边删去，然后枚举所有的块对，如果可以覆盖这条边，那么用 minE[i, j] 来更新最优的非树边。最后再比较一次，如果可以更新 MST 就执行一次替换。

复杂度的事呢，第三种情况显然是 O(z) 的，第四种情况是 O(z + (m/z)^2) 的，于是 z = m^{2/3} 好了。

O(sqrt(m log m)) per update

上述做法没有用到任何数据结构维护。一个显然的优化是用某种奇怪的数据结构来优化。

Topology Tree

这里用到的数据结构是 Topology Tree 。Topology Tree 是一种动态树，他用一个奇怪的树形结构来维护原来的树，可以在 O(log m) 的时间内往原树加入、删除一条边。

考虑一棵任意点度数不超过 3 的树，我们可以 O(n) 构造它的 Topology Tree 。具体构造方式，自己参考论文吧，因为要用图来解释我就懒得搞了。

容易证明， Topology Tree 的高度是 O(log n) 的。Topology Tree 中任意一个节点的孩子数不超过 4 。

为啥这里需要 Topology Tree 呢？因为后面需要支持若干个操作： 1. 合并两棵树 2. 把一棵树分成两棵 3. 查询一棵树的最小权

块树

构造一个新树叫做“块树”，也就是把原树一个块缩为一个点。可以得到块树的大小是 O(m / z) 的。

很囧的一点，块树的度数并没有保证。于是我们要找到一个合适的划分块的方式，使得满足： 1. 在 MST 中，任意一个块至多与三个块相邻。 2. 任意一个大小小于 z 的块必定与三个块相邻。

这种划分块的方式只要在 csearch 的基础上稍稍修改即可。每次函数再多返回一个值，表示与几个块相邻。一旦块的大小超过 z 或者度数等于 3 ，这就应该要被分成一个块。可以证明，这种方式可以满足要求。（证明懒得看了）

我们把这种划分的方式成为 度限制划分 （自己随口 YY 的名字）。

具体做法

我们在度限制划分时会产生 O(m / z) 个小块，对于每个小块我们构造一棵 Topology Tree 。这棵 Topology Tree 的每个叶子表示一个划分出来的小块，顺便用一个堆按边权大小维护 E[i, j] 以及最小权的边；对于每个内节点，我们维护这棵子树内的最小权的边。很显然，所有的 O(m / z) 棵 Topology Tree 的形状是一模一样的，只是要维护的值不一样。空间复杂度易知为 O(m^2/z^2 + m) 。当 z > sqrt(m) 时，空间复杂度为 O(m) 。

再次考虑删除（添加）一个块需要做的操作。每次需要修改 O(m / z) 棵 Topology Tree 。每次修改需要修改最下层的叶子，然后依次更新内节点。由于 Topology Tree 的高度为 O(log (m / z)) ，所以每次操作的复杂度为 O(m/z log (m/z)) 。

考虑第三种情况。由于替换边的本质是重新维护块，而需要维护的块的个数是常数个，而且要构造常数个块的 Topology Tree ，所以复杂度是 O(m/z log (m/z) + z) 。

考虑第四种情况。这一步就可以通过维护的 Topology Tree 来加快速度。不妨设这条树边连接的是 x 和 y 。如果 x 和 y 在同一个块中，我们需要把这个块分裂成两个，这也可以通过改变常数个块来实现。在前一种算法中，我们要 O(m^2/z2) 地枚举块对，现在我们只要枚举一个块，在这个块对应的 Topology Tree 中把 x-y 这条边删去，这样会产生两个 Topology Tree ，选择不包含这个块的 Topology Tree ，用维护的子树最小权的边即可更新答案。第一步的复杂度是 O(m/z log (m/z) + z) ，第二步的复杂度为 O(m/z log (m/z)) ，总时间复杂度为 O(m/z log (m/z) + z) 。

均衡一下，令 z = sqrt(m log m) 可以得到整个算法 per update 的时间复杂度为 O(sqrt(m log n)) 。真是太令人（理性）愉悦了～

O(sqrt(m)) per update

在上一种做法中，我们建立了 O(m / z) 棵 Topology Tree ，而这若干棵树的形态完全一样。于是我们可以考虑建立一棵“二维 Topology Tree ”来继续优化。

然后啪啦啪啦优化就是 O(sqrt(m)) 了 = =|| （具体过程正在看……）

\(O(\sqrt{n})\)

总感觉很忙没时间，却刷了无数次水。

禁了人人 ，发现逛 NOIP 吧的时间快赶得上人人了。

echo 0.0.0.0 tieba.baidu.com \| sudo tee -a /etc/hosts && sudo systemctl restart network

最近看了看 Lisp ，感觉 Haskell 和 Lisp 是两个极端， Haskell 专业高科技三十年， Lisp 则是让码农自己配置一门语言。Haskell 专注于算法，Lisp 则专注于代码的编写。

好了不说了，说说这次 CF 吧。

结果嘛，自然很不理想。只做了 A、C 两个题，结果 C 还 FST 了囧，最后中号（以后就按照 rating 标记为大中小号好了）居然都跌了，sigh……

Solution

A

这个水题也不水的啊……

可以知道， p^2 只包含长度为 1 和 2 的循环，而且长度为 1 的循环至多只有一个，所以 p 只包含长度为 1 和 4 的循环，且长度为 1 的循环至多只有 1 个。于是无解的充要条件是 n = 2/3 (mod 4) 。

然后我们把若干个长度为 2 的循环合并起来就好了。

B

居然没做出来，囧。

如果提前把序列旋转一次（就是把第一个放在最后去啦），那么有改动的位置是 O(n / i) 的，数组就好了。开个两倍的数组好了。

C

手速慢啊。FST 啊。

主要思想就是尽量晚地退栈。每次遇到一个必须配对的，我们就看看栈顶，如果栈顶为我们等待的元素，那就 OK 了，否则弹出栈顶，递归配对栈顶。

然后某个地方忘记 break 导致死循环了，囧。

D

一开始看错题了囧。

其实这个题蛮好玩的。

我们建立一个平面直角坐标系，x 坐标表示时间，y 坐标表示人物的 y 坐标。那么所谓“墙壁”可以看为一个向右无限延伸的条形，人物的运动轨迹就是直线 y = x - T ，T 表示人物开始运动的时间，答案就是直线在所有条形内的线段在 y 轴上的投影长度和。我们把二维平面直角坐标系变换一下： (x, y) -> (x - y, y) ，则人物的运动轨迹 x = T ，条形变成了一个无限延伸的梯形。我们可以求出所有梯形的并的形状，再水平剖分后成若干个梯形。这若干个梯形对答案的贡献是独立的，每个梯形对答案的贡献可以很方便的求出来。

如何球梯形并？按 t 排序后暴力，用并查集保证复杂度就好了。

E

感觉就是暴力 FFT 的题……

令 f(x) = \sum c_i x^i ，其中 c_i 表示 i 是否出现过。考虑 f^2(x) = \sum d_i x^i 。若 i <= m && c_i == 0 && d_i != 0 则显然无解，因为 i 能被若干个包表示出来，所以 i 必定是一个包；若 i <= m && c_i != 0 && d_i == 0 ，则 i 会出现在答案中，因为此时的 i 不能用其他的数的和表示。

situtaion

听说下午有 CF ，真是喜闻乐见。CF 的正常时间是晚上十一点半的啊。

大叔、秋锅被拉到招生办去了，于是就只有我一个人在做。

看了 A 发现第一眼居然没想法？这不科学！不过乱 YY 一下还是可以 YY 出来。10min 才过居然还是 room 中第一个……

然后看 B 。看完题目的第一想法是调和级数的前缀和是 O(n log n) 的，然后用 splay 暴力维护序列。

……用 splay 维护序列的题可以放在 B ？

……用 splay 维护序列的题有人可以 8min A ？

……用 splay 维护序列的题有 50+ 人 A ？

……只想到用 splay 维护序列的人就滚粗了。

总是感觉各种不科学不可做啊。感觉再在这个题上耗就要挂了，于是决定看 C 吧。

看了 C 后感觉只要 lazy 弹栈就好了。于是怒写。由于写的 dfs ，导致各种判无解退出 = =||

最后在 D 和 B 纠结。稍微看了看 D 的题目，一开始看错了，以为是一道裸数据结构题，写完了才发现囧。

那就只好做 B 了。一直拖拖到考试结束还是没做出来……

E 连题目都没看，要是看了题目的话或许能想到 FFT 的。

最后结果 C 还是少判了个无解退出，结果就死循环了，光荣 FST 。于是就只过了 A 。#190 怒 -64 。

others

怎么看都比我好是不。

看 standing 发现各种 FST 啊，我觉得这么坑爹的题本来数据就要加强点嘛，怎么忍心还让别人 FST 呢，出题人的良心啊。

7k+ 没跳 B 这个坑，于是过了 CE ， D FST 了。 #9

peter50216 FST 了 DE 题。不过前三题过得快也不错的。#10

liouzhou_101 #36 略略跌了点。

lyd 和 shy 开黑我就不吐槽了。总之对于他俩开黑我已经习惯了。 lyd #32 shy#40

过了前三题的人都不错，ryz #48 。

楼教主也来了！FST 了 CDE 真是太残忍了。RAD 也 FST 了 CDE 囧。

发现一堆人 FST C 啊，RAD、a142857a、chnlich、cherudim、wuzhengkai、ACRush 。

WJMZBMR 退出了 IGM ，ACRush 最近的 TC、CF 表现都不佳。难道要让位给—— wjmsbmr 了吗？

nonsense

我该怎样吐槽这两个人？

我会说 fotile96 是镇海神 dyh ？

我会说 roosaphu 是 XLk？ 你这是闹哪样啊……我一开始居然还没反应过来 = =||

最后献上一张图，不忍直视。

结果还没出就开始写了……随便啦，免得成为坑。

Solution

A

A 有 1000 分诶，所以不是简单题了。这是个简单数据结构题，写个树状数组就好了。

B

我勒个去坑翻我了。

很容易可以知道，只要记忆化一下就好。于是我开了个 map 来搞。但是在递归的时候为了预防死递归，我还用了个 set 来保存当前的栈。于是若干次错误就在这个栈这里了……最后 +4 才过。

C

感觉是个水题啊。

首先如果没有变量的限制条件，那就是一个很暴力的 dp 了。无解的一种情况就是出现了环。假设不存在环，考虑消除这种限制条件。对于一组限制 x[c] > x[b] ，我们可以尝试令 y[c] = x[c] - x[b] - 1 ，这样 y[c] 是没有限制条件的，同时，把 a[b] 加上 a[c] 。这样意味着每次取了一次 b 就要取一次 c ，而 y[c] 就是 c 比 b 多取的。

剩下的就是背包了。

D

这个题还蛮有意思的。

先考虑两个数可以相邻的条件。(x, y) 合法，当且仅当存在 t 使得 x = yt + y(y-1)/2 。所以当 y 为奇数时，只要 x = 0 mod y 即可。当 y 为偶数时，则条件为 x = y/2 mod y 。

接下来就是 dp 了。f[i] 表示前 i 个最多保留多少个，其中第 i 个必须保留。f[i] = max(f[j]) + 1 ，j 的条件为 j 到 i 这一段能凑出一个序列。考虑 a[i - 1] ， 如果 a[i] 是奇数，自然一种很自然的想法就是前一个继续用 a[i] ，否则前一个用 a[i] / 2 。这样维护一个数就好了，是这次 CF 中最好写的题。

E

我居然没看这个题……看了后发现应该是可做的，但是我不一定写得出。

首先需要用到 WC 某费用流题《石头剪刀布》的一个结论：

ans = C(n, 3) - sum(C(w[i], 2))

其中 w[i] 表示 i 的入度（或者出度）。证明很巧妙的说。

然后考虑如何统计 w[i] 。原题是在一个 n * n 的格子上进行操作的，每次取反一个子矩形。差分一维，线段树维护即可。

situation

首先做 A 。第一反应是维护一个和就好了，啥数据结构都不用。第二反应是要写个带标记的线段树，恶心啊。最后决定写树状数组吧。坑爹的 cout 输出精度，我一开始只输出了 6 位有效数字不幸 WA1 。换成 10 位就过了。

然后看 B 。我勒个去停电是什么状况啊！向总不是和门卫打了招呼了吗！坑爹啊亲！感觉这个题也蛮水的，写啊写提交发现 MLE 了……这明显是死递归的节奏啊，怒看代码发现了 WA 点。改了再交收获 WA 5 。又发现一个 WA 点再交，还是 WA 5 。还发现一个 WA 点终于过了 5 了——变成 WA 9 了……再找终于过了 pretest 了，泪流满面。只有 592 pts 了。

看 C 。一开始以为这是宇宙大水题，写了发现过不了样例，才发现看错题了 = = 重新看了遍题目发现仍然是水题，怒过。

看 D 觉得这题蛮适合我的口味的，偏数学，代码短。总之推了一下就发现可做了。

然后就没有然后了，连 E 的题目都没看。

最后发现 A 用时 11min C 用时 17min D 用时 13min B 用时 40 min ……最佳的做题顺序是 DCAB 啊亲，又被做题顺序坑了。

幸亏没有 FST 。#14 怒踩 Egor、CLJ 也不错了。下次如果 RP 还这么好就可以红了～

others

ST 之前 7k+ 夫妇怒占前二，然后 CLJ 怒 FST * 2 。

Seter 居然也在做？我很少看见他做啊。 #20 好牛叉。他首先做的 D ，犹豫了好久不敢交……他要是交了绝对虐我。

liouzhou_101 #22 和我一样被 B 坑了 50min

wuzhengkai #31 A 居然 FST 真是 xwlj 。

lyd 的 C 莫名其妙被 Skipped 了……于是 #35

然后我就很奇怪为啥 FredaShi 为啥每题都交的比 lyd 慢。

wyl8899、squarefk 都是前三题。wyl8899 的 D FST 了。

秋锅只过了两题。B 1A 分数比我还高= =

a142857a FST * 2 真是太令人桑感了。

nonsense

最近 我/主席/xiaodao/Seter/7k+ 几个商量再出一场 CF ～

当然 idea 有限，时间也是个问题～

Solution

250 pts

显然是贪心，每次取最大的一个元素，然后去能超过他的最小的两个就好了。

直接用 set 暴力搞。

450 pts

我勒个去这都会想错……

首先一个很简单的结论就是：一定存在一组最优解，使得不会出现新的种类的高度。

有了这个结论就好做了。点的范围只有 50 ，于是直接 f[i][j] 表示第 i 个点的高度为 j ，且 0 号点能到达 i 号点时的最小修改代价。显然可以用最短路来做。构不构图随你，反正范围很小。

我居然很脑残的写了个 bellman-ford ……还是个错的 bellman-ford ……

850 pts

为了填这个坑我容易么我。等 TC 的题解等了这么久，今天晚上终于出来了。

首先很明显，坐标轴需要转一下。然后目标点就被限制在一个矩形范围内了。现在我们要统计所有的初始点到达矩阵中某个点的方案数的和。 注意到每次移动对于 x 和 y 的改变是不相关的 ，也就是说 x 和 y 可以分开解决。知道了这一点一切都好做了。

由于可以分开解决，那么啥问题都没有了，不妨假设要求 x 吧。枚举最后的 x ，再枚举每个点，方案数可以由一个组合数表达出来，所以可以 O(1) 解决。总复杂度就是 O(nm) 。

居然没想到 x、y 分开解决，诶……

situation

早上给小朋友发了题后开始刷水，在八点四十多发现今天的 TC 是早上九点而不是晚上，怒开小号注册。

似乎我在 room 排名蛮低的？桑心～

250 pts 似乎是水题，秒掉。

450 pts 不会做，乱猜了个结论，感觉是对的（的确是对的）。于是开始敲代码。不想构图了，于是 YY 了一个算法，用 dp 来做。结果一测发现连样例都没过 = =|| 然后想着这个算法没错啊，于是又加了一层循环怒过样例。后来一想这是哪门子的算法啊，错的妥妥的……

既然过了样例就没想了，看着第三题只有 850 pts 觉得可做于是就做了一下……发现这不是个数学题吗？蛮合我口味的。感觉是个组合数学题？也还可以。于是 YY 来 YY 去还是没想法……

看完 Analysis 后瞬间发现我脑残了，分开考虑就很简单了。

最后 450 pts 的当然 FST 。排名 #173 如果没有 FST 的话前 20 应该没问题……

由于是小号所以还是可以涨的。但是……这会不会对自已要求太松了点？

others

AC_Rush 时隔多年之后终于回来了！但是 #36 似乎有点不合人意啊……（不要给我）

我们 room 的 NaHS 前两题开的很慢，刚交完的时候是 room 的 #10+ 。但是不知怎么的慢慢慢慢就到了 #2 了，最后 #35 怒压教主。

cherudim9 #49 感觉 450 pts 的有 300+ 应该是不难的。

liouzhou_101 #95 主要是 450 pts 的交慢了吧。

UESTC_elfness 居然 FST 了 250 pts 的，出乎我想象。

ryz #165 ，250 的比我快……

huzecong 蛮好玩的，他的 250 是我们 room 交得最快的，后来他重交了一遍，就只有 75 pts 了。450 速度也还可以，然后又重交了一遍就只有 135 pts 了，最后 250 的 FST 了还 cha 错一个人囧……

另外求 @xiaodao 小号 ID ……

有人 -150 什么心态 = =||

第一次参加 CF 的出题，感觉蛮好的……

虽然我打了一圈酱油啊！啥都没做啊！

Solution

2A --- xiaodao

你还想要有多水？

2B --- roosephu

普通青年：枚举分母。

文艺青年：连分数展开。

二逼青年： Fraction(x,y).limit_denominator(n)

2C/1A --- xiaodao

普通青年：暴力半平面交

二逼青年：暴力推公式

文艺青年：跳掉不做

要我的话还是半平面交吧，虽然这样也要推一些公式 T_T

2D/1B --- roosephu

这个题是我从耀爷那里蒯来的，结果没想到成为最水的题了……

一个结论就是最大值/次大值对只有 O(n) 个，用单调队列处理出来就好了。

感谢大叔提供了几个好数据～

有谁看得出这题是我出的么……其实我还黑了人的，只不过黑得很不明显罢了，连某热衷于黑我的小朋友都没看出来。

2E/1C --- WJMZBMR

答案就是每个点的深度的倒数和。（根的深度为 1）

证明嘛，我还不会一个显然的证明，但是我找规律找出来是对的。

有一种理解是这样的：我们考虑每个点，这个点只有在选择某次其祖先的时候才可能被删，选中自己的可能性是 1/dep(i) ，也就是这个点对答案的贡献期望是 1/dep(i) ，又由于每个点对答案的贡献是独立的（这点怎么看？），所以直接加起来就好了。

1D --- fotile

来自 fanhq 的加强版。

对于一个序列，求 k-MSS ，我们可以用网络流来做：一条链，限制流量为 k ，跑最大费用最大流。

这不是比暴力还慢么！注意到每次增广的特殊性，一定是选择一个区间，取了其中的值，然后区间取反。线段树维护即可。当然由于维护的信息比较多。要支持取反于是要还要记录最小值，还要顺便记录答案，比较麻烦。

于是就 O(n k log n) 了……

这个题居然被水过去了，坑爹啊……算了算了还是那句话：暴力能水过去也是他的能耐嘛。

1E --- fotile

主席的加强版的弱化版。（一种蛋疼的忧桑？）

做过原题的话应该知道用折线来刻画 dp 值这方法。对原题来说令 f[i][j] 表示第 i 个数为 j 时的最小代价和，可以知道 f 是一条折线，且只包含 O(i) 条线段，于是我们维护 f[i] 所表示的折线，递推出 f[i+1] 的折线。事实上这个方法是可以推广的，不过在这个题上是用曲线来刻画。曲线不好表示是吧，于是考虑维护曲线的导数。

维护了导数，找最小值也好找了，直接求与 x 的交点即可，方程也可以维护了。由于 n 只有 6000，暴力维护即可。当然你要有能耐的话可以用平衡树维护，保证复杂度 O(n log n) ，不过略难写。

procedure

一开始是在 G+ 上，主席说要给 CF 出题赚外快，于是我就回了句 bg ，然后就被主席拉过来出题了。

YY 能力完全不够啊。幸亏最难的几个题主席都已搞好了，于是我和 xiaodao 专注水题三十年。小岛出的 2A & 1A ，我出的 2B & 1B

一开始出 2B 的想法是要给一道水题是吧，然后瞬间想到 Python.fractions.limit_denominator 。当然连分数展开是果断不可行的，于是暴力枚举分母即可。

1B 的来源是耀爷讲课时的某题，我就直接蒯了下来～Gerald 好像搞了个很复杂的方法的说，其实就是个水题嘛。

一开始 1B 想出最大值除以次大值，后来想把数据出强一点，于是写了个 cheater 发现全部骗过去了，后来才发现如果是除以的话，答案一定是相邻两个数的商……宇宙大水题啊……

出题是放在 Polygon 上。真心是个专业网站，自带版本控制，用起来非常方便。里面有 invocation 用来测试数据，gen 建议用命令行做初始化，可以用脚本来生成数据，validator 检验特严格，一个字符都不能多，checker 感觉很松的，package 可以下载这个题目的所有相关信息，题目支持部分 TeX 语法真是太好了。幸亏前一段时间用过 git ，对版本控制还是有点理解的，用起来不难。唯一需要吐槽的一点，就是你必须等网页缓冲完毕后再点击超链接，否则会直接回到首页，蛋碎的感觉……每次 commit 都会发一份邮件，所以这几天被轰炸了不少。

主席某天突然之间就住院了，一开始我也不知道是啥情况，但是似乎很严重的样子。于是他的题就被分了，我、xiaodao、Seter 一起搞。我写了 E 的 cpp 以及 java ，慢出翔了，后来还是用的 Seter 的 java 。不过我写的 D 的 java 倒是跑得蛮快的样子。时限要求为 java 的两倍还真是蛋疼。为了照顾 Java 我不得不优化常数，结果最后和 xiaodao 一商量决定把时限开为 5s ，于是就有人水过了 T_T 其实我觉得 n 开小 k 开大蛮好的嘛，CLJ 说限制 k 的和也是可以的，这样更好卡了。

在比赛的前几天，突然得到消息说 C 冲了，于是怒 YY 题目。刚好做了一个 Project Euler 的题，于是 YY 出一个题，但是被 CLJ 抢得先机用了他的题。没关系下次再用嘛。

于是这场比赛的 problem setter 真是多，xiaodao、我、CLJ、fotile、kissbuaa ，另外 Seter、7k+、pashka、Gerald 来验题，规模也算得上庞大了，于是有人怒吐一槽：

话说现在 WJMZBMR 与 Petr 正大战三百回合，有兴趣的同学可以去围观。

然后晚上本来不打算围观了的，因为没人做，但是跑回寝发现大叔在做，于是怒围观。Seter、xiaodao、CLJ 开了语音，我和 7k+ 俩人就只好打字了……好苦逼。

于是讨论组里面的人全部开了上帝视角，成了权限狗。期间由于 XLk 突然之间回话了所以和 XLk 聊了一下天，他好久不回我了 T_T

发现 div2 的题超水，3min 左右 400+ 人过了 2A ，太可怕了。然后继续有人过 2B 。我很想不通那些过了 2C 没过 2B 的人是啥心态……我更想不通居然没人用 limit_denominator 来做，我还想不同有人用 Fraction 构造分数的时候用了小数从而精度有 bug ，我最想不通一堆人说这题精度太紧了太紧了。明明 Gerald 说这题太水要把数据组数减小的……

居然有人 5min 内过了 1A ，真是太令人惊悚了。我还看到若干个纯代数流，太可怕了。由于 1A 题过难，导致 1B 被迅速秒，成为这次 CF div1 AC 人数最多的题。

wuzhengkai 和 watashi 俩人同时在 33min 过了 A ，死磕着 A 不放干啥嘛，A 明显是用来坑人的。（wzk 的人人头像越看越觉得萌 = =||）

比赛的时候一堆人问 excluding OR 是什么意思。我明明记得我原题写的是 XOR 啊，那个英文翻译改成了这个东西真是蛋疼……偏偏样例精心手构答案是 7 和 15 无论 or 还是 xor 都可以解释。不过明明题目是 XOR 样例解释是 XOR 你还有什么问题吗？

哇卡居然有人交了 E ？WA pretest 2 连样例都过不了囧爆了。讨论组里面没人认为有人可以 AK 。

然后在 1h5min 有人过了 E 的 pretest ？为了和谐 pretest 是直接上了极限数据的，人民群众喜闻乐见欢兴鼓舞拍手称好。然后 Seter 拿过去一测发现可以 A 。经仔细研究后发现这个算法是错的……于是 Seter 出数据开始卡发现稍微一卡就可以卡掉了……结果一场腥风血雨在 CLJ 和 Petr 展开……再一看这个人还只交了 E ？果 E 大神！他的 AB 是后来才写的，太强大了……

大叔 YY 了一个 1B 算法，于是交了一次发现是错的，然后再交一次，于是我求数据加入 tests ，然后又写了个 gen 来生成类似的数据，似乎卡掉了一些人的样子。

D 题居然有人写正解！UESTC_Nocturne 太强大了……不过这个题被 liouzhou_101 骗过去了还真就不甘心呢。但是时限放的太宽卡不掉真是蛋疼呢。

之后一堆人在吐槽说 div2 的题太难了太难了太难了，你想要我做什么表情？

这次 CF 成功把 tourist 拖下 3k ……只要拼了前三题的手速就不会太差，后两题基本上没人过的。

nonsense

好吧就是这样，感觉蛮好玩的呢。

骗钱向：以后有谁要出 CF 了我可以过来打酱油啊，专业酱油三十年。

终于没有 hole 这个 tag 了～

Solution

250 pts

做这个 250 不要 250 了……

枚举最大值在这个序列的位置，可以根据位置及 d 算出这个数是多少，然后取遍 max 即可。

500 pts

二分答案，没了。

1000 pts

感觉这个题好囧啊。

令 S 表示随便放一个马，除自己这个格子外，期望能够攻击到多少个格子；令 P 表示同时能被两个马攻击到的期望格子数。经过一定的推理后，我们可以发现如下公式：

ans = 2S + 2 - 2S/(n^2-1) - P

于是我们只要求出 S 和 P 即可。求 S 的话可以考虑统计每个方向上可以放的马的数目， P 的话我们就枚举同时被攻击到的马的位置。

首先考虑 a == b 的情况。 S 倒是很好求， P 的话可以推出一个公式来的。

再考虑 a /= b 的情况， S 照样很好求， P 就不一定了。我 YY 了一个很奇葩的方法。首先找到边界上的若干个分界点： {0, a, b, n - b, n - a, n} 。这若干个点把大矩形分成了 25 个小矩形。矩形内部的 P 是一定的，随便找一个点（例如找中点）即可判断出某矩形内的点的 P 。然后再用组合数乱搞一下即可。

situation

怒刷小号～从此我也是有 TC 小号的人了～

一进 room 一看，cherudim9 是 room 内 rating 最高的，我是最低的，高下立判。

一打开 250 pts，插件自动帮我生成了……Java 模板？我勒个去果断自己手写 C++ 。

随便一想觉得这题蛮水的啊，写完后样例都没测（因为没插件不好测），直接在 Arena 里面测了。觉得没啥问题就交了。这题真心水啊怎么 room 里第二个交的才 230+ 呢？

果断重新配置插件。把默认语言改为 C++ 一切就好了。

然后开 500 pts，这不是一个绝世大水题吗……怒写然后过掉。

现在时间还多的很呢，于是开始 YY 1k pts 。一开始的时候根本就没想到还有 P 这种干扰，后来才想起来……

感觉样例很强的啊，于是感觉是可过的。

cha 人的时候看到 500 pts 有人没用 long long 来保存中间结果，就想着这是不是一个 cha 点。我看到有人程序和我的特别像，于是在 cha 之前用自己代码测了一遍，发现过了？继续 YY 发现就是过了。自己一想发现中间结果至多是 2k 怎么可能会爆 int ……

最后的 FST 是什么情况啊！发现是 a == b 时的特判写挂了 T_T

所以最后是 #60 。如果 1k pts 不 FST 的话前二十没压力的 T_T

others

这次做的人不多，很多人都做前两次去了。

cherudim9 本来还好的，可是被 500 pts 的那个不是 cha 点的 bug 搞错了于是 +0/-2 囧…… #174

秋锅 #72 。令人惊悚的是他现在 rating 还没我小号高 = =||

看到了 DL.uhT 分布式哈希堕落？其实是某盾啦 #93

lydrainbowcat 1k pts 的被 cha 于是 #107 。

至于大叔……哇过了两道诶，虽然速度比较慢但是没爆零了啊～#227 不过 rating 还没他的第一次高……

cjsyj 的 250 pts FST 了？ 这不科学 ！ #425

This_poet 居然 FST 了 500 pts ？#685 momo

nonsense

今晚 CF 欢迎各位参加～