纯粹试试 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 了我可以过来打酱油啊，专业酱油三十年。

刚刚对主题做了点小改动。原因蛮简单的，在 XFCE 下开启透明效果后，我发现原来的背景与桌面这张阿狸的图片混在一起蛮好看的，于是心血来潮加了个背景。各位觉得怎么样啊～不好看的话我还是改回来吧。

具体实现其实蛮简单的。首先找到你的壁纸，用 GIMP 打开，然后新建一个全黑的图层，然后 菜单 -> 颜色 -> 曲线， 通道设为 alpha ，然后把那根线段的端点往下拉，就是 x 不变 y 变小，开启预览的话就按照自己喜好调。然后 Ctrl-Shift-E 导出即可。似乎这种图上 jpg 比 png 小一些？

如果图片大了的话缩放一下即可，我直接用 XnView MP 来重采样了。

然后要改 Jekyll-Bootstrap 了。我用的主题是 hooligan ，于是在 /assets/themes/hooligan/css/style.css 这个文件内有一行

background: url(../images/bgs/body.png) repeat;

我要的效果是背景不随网页滚动而滚动，于是改成：

background: url(../images/bgs/bg.jpg) fixed;

刷新几次，收工。

当然还有不满意的一点，就是壁纸大小不能根据屏幕大小自动换。这个要实现的话应该是可行的，因为这几天鼓捣 bootstrap 发现可以提供响应式设计，多 YY 一下应该是可以 YY 出来的吧～

终于没有 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 欢迎各位参加～

似乎坑越来越多了……得填填啊。

XLk 去北京学英语了。（而且问他又会黑我的 T_T）

Solution

250 pts

唔，似乎是水题的样子。

大概就是利用 K 找出每一条链，链上找出出现次数最多的字母，其余的字母全部变为这个字母即可。

500 pts

又是渣手速。

暴搜是会 T 的～hahahaha 感觉只要答案大点就好了。（random 搜怎么破？）

我的方法是这样的：前面 4 位枚举原数，得到所有前四位的匹配情况。后 5 位就可以直接暴搜了。这相当于一个双向搜索，先从某一半开始搜，把所有可能的解全部塞到一个 set 里，从另一半检验的时候就直接在 set 里找了。

用 set 的话可能常数比较大，用个 trie 效果会更好些。不过这无关紧要了，不会 T 的。

话说感觉 TC 的 500 pts 很喜欢出这种暴力题啊。

1000 pts

坑。

situation

这次 TC 居然是晚上八点。话说 TC 没小号真是让人感到可怕……（xiaodao：rating 是用来跌的！）

于是机房里都在做 TC 。

上次 TC 给我发了个啥邮件，说啥 warning of unused code ... 于是这次交之前把模板神马的全删了……

250 这不是水题吗……手速硬伤。只有 237 分了。 T_T

500 想着感觉暴搜很容易过的？但是复杂度不靠谱啊……没敢写，继续 YY ……

突然之间 YY 出来了？写啊写……代码能力越来越差了，写了好久才调出来。只有 270 分了。

看了一下 1000 pts 的题，感觉很厉害的样子，没怎么动心思去想……

然后啥都没做了， Challenge 对我来说一直是打酱油的。

other

大叔又一次没爆零！普大喜奔～

tourist 怒 cha 掉 Petr 的 1000 pts 成功 #1！

我会说 Petr 只靠前两题还有 #4 ？

WJMZBMR #10 。第二题 350+ 太快了啊……

我居然看到了 Gerald ？ #16

某 id 为 ainu7 的神犇只过了第一题，第二题 FST 了。然后他居然连 cha 了 6 个人 #17 ！跪。

然后我就是中规中矩的 #22 ……

还有 Mike Mirzayanov 。CF 的都来了？

edly 说跪了，然后 #35 = =|| 然后怒黑之。

一堆人 FST 了 500 pts 。zhouerjin/xiaodao/NaHS/ChnLich/cherudim9/ryz/wuzhengkai ……momo

有位小朋友在做 div2 ……只交了两道于是 FST * 2 momo

另外 orz huzecong div2 虐场。

nonsense

CF-172 求围观啊～求各位大神虐啊～

前几天某人（特指）进入国家队了，然后 renren 上转了条状态（miffy 的），然后被一群人围观，然后四处被黑 T_T

有必要么！

嘛，wyl8899 问我是不是刷小号……

我才不刷小号呢，我刷的是小小号。

Solution

A

惯例水题。直接用并查集搞搞就可以了。

注意没有一个人会一门语言的情况。我因为这里 WA 了一次。

B

构造。

rng_58 的构造方法：对于 m=3 的情况手算，可以证明若 n>4 则无解。于是这里手算很简单的。

然后考虑两条抛物线： y = x^2 + U 与 -y = x^2 + U ，其中 U 是一个很大的数。如果我们在抛物线上选点，由于抛物线的特殊性质（凹还是凸分不清啊 T_T），可以得到如果两个抛物线上都有点被选，那么这样构出的凸包的大小最多是 4 ，所以如果要选择尽量多的点的话，应该是选择某一条抛物线上的所有点。我们令一条抛物线上点的个数为 m 即可。

C

感觉还蛮简单的。

容易知道每行每列都是独立的，我们可以把这看成是若干个不相关的组合游戏。对于每一行/列，我们只关心没有被覆盖的线段的条数。这个可以用排序+点事件维护，也可以直接用 set 暴力维护。

然后把所有的数 xor 起来就是 SG 了。注意一种特殊情况就是初始时没有出现过的行/列。很显然，我们只关心奇偶。

如何输出方案？一行一列枚举下去，如果通过改变这一行/列可以把 SG 变为 0 则找到一组解。

代码量比较大吧。

D

没看懂题目的说……

E

稍稍一想就发现这是水题。

每个点的出点向所有可能的父亲的入点连边，容量 1 费用为距离。源向每个点的出点连边，容量 1 费用 0 。每个点的入点向汇连边，容量 2 费用 0 。跑一遍费用流，如果最大流是 n - 1 那么有解否则无解。如果有解则最小边权和就是最小费用。

大家都蒯模板啊我还老老实实自己打啊。

situation

本来以为秋锅不做的，结果居然做了。

看完 A 觉得这不是水题吗？于是怒敲代码，写着写着觉得有 bug 于是怒换一种写法。submit 后怒 WA#4 。瞬间想到某特例，加上特判后过 pretest 。

然后 B 。按照惯例，B 应该是水题吧。于是我被惊悚到了，完全不会做啊。YY 了好久想到了用抛物线但就是没想到用两条抛物线。一开始看错题了，以为是要构造一个大小为 n 的点集使得凸包大小恰好是 m 。交了后发现过不了样例才发现看错题了 T_T

瞟了一眼 Dashboard 发现有几个 E 已经出来了，看了一眼 E 觉得不会做。然后看 C 的题目去。看完 C 的题目后发现我会做 E 了 = =|| 于是回去写 E 。1A 。

然后发现 C 不也是水题么。只是处理起来比较麻烦罢了。于是再次怒看错题。然后就没有然后了，1:50 的时候交了个 FST 程序过去。后来调的时候才发现又看错题了 T_T

一看 D 的题目这么长我就直接撤了。目测等我理解完题目 CF 都结束了。

最后 #41 由于是小小号然后还是可以涨的。快追上小号的说～

others

XLk 你真的 AFK 了吗……考完后没人和我聊天了 T_T

scottai1 怒过 ACE 。E 手速还很快的说，于是有 #8 。于是 rating 又超过我了 T_T

wuzhengkai #25 、xiaodao #32 都是 ABE 。我觉得 B 的这个构造很巧妙的说。

watashi 和我一样的，默默 C FST 了。

秋锅 AE #90 。看起来又黄了。

另外我就不吐槽 FredaShi、CatCat、liouzhou_101 三个人的分数都差不多，都是 AB ，提交的时间也差不多，代码也差不多，连 E FST 了都是 T 12 。

ztxz16、sths、edly01、vfleaking 都只过了 A ，而且和我一样，默默 wa 了一次 ……

最后还要吐槽这次 CF 的分数变来变去的，一刷新就发现题目的分数变了。

nonsense

感觉这次 CF 难度很大的说……

然后发现还有人 AK 。

于是感觉 CF#172 也会有好多人 AK 的说。