似乎 Matrix67 大大已经翻译过了。

Problem

一个长度为 \(n\) 的 0/1 串，A/B 俩人博弈。每次操作如下：

1. 如果当前串首是 1 ，则放一个 0/1 到串尾，由 A 决定
2. 如果当前串首是 0 ，则放一个 0/1 到串尾，由 B 决定
3. 删除串首，重复以上过程

如果有限步内这个串全是 0 ，则 A 获胜，否则 B 获胜。

问什么情况下 A 必胜。

呼啦啦准备翻译完 TOAD 。这些题真心虐心啊……

今天说的这个题有一个众所周知的方法。但是还有一个非常漂亮的解法，我相信还是没多少人见过的。

Problem

有 \(n\) 个人坐在一张圆形桌子前，每个人面前有一盏灯。现在 A 和 B 博弈。流程如下：

1. A 选择若干个位置，并把选择的结果告诉 B
2. B 把桌子转一下
3. 把 A 选择的位置的灯的状态同时取反
4. 重复以上过程

游戏终止的条件是存在某一时刻，使得所有的灯都是亮的。游戏终止则 A 获胜，否则 B 获胜。

A 随时可以调整策略，即 A 每次决策的时候可以看到现在灯的状态，并做出反应。

问：什么情况下 A 可以获胜。

新生活。

看到一个很好玩的题，来源于 TOAD 。

Problem

给定一个正整数三元组 \((a, b, c)\) ，每次可以选择任意两个数，不妨假设选择 \(a, b\) ，且满足 \(a \leq b\) ，则可以把这个三元组变换到 \((2a, b - a, c)\) 。

求证：任意一个三元组经过若干次变换后，总可以使一个数为 0 。

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

最近 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 有限，时间也是个问题～