新年第一帖，先祝大家新年快乐吧。

其实 THU 集训后就一直想写些啥的，但是坑挖了很久一直没填，心里也一直憋得慌。还是写点啥吧。

现在主要是感觉压力大呢。主席他们还有一次机会呢，我就只有这一次了。

fail

感觉越来越害怕失败了。

为啥害怕呢？

我怕退役后，同学给我的不是一句安慰，而是“为啥你没 xx 呢？”，或者是“人家 xx xx 了，你以前不是很厉害吗？”。是的，刚开始接触 OI 的时候充满了兴趣，第一次 NOIP 也靠着 RP 拿到了省一，但是后面的路感觉越来越难走。难度逐渐加大，但是水平提高慢。

记得高二上学期刚开始的时候，老师要我们填竞赛目标。当时刚考完 NOI ，靠着题目水混到了银牌，于是天真地填下了 xx 。如果有人还记得这件事，再问起来……sigh

我怕退役后，再看到老爸。老爸对我希望很大。近些天来没主动和老爸聊天过，老爸找过来甚至都装作不在。聊啥呢？老爸说，我们已经有年龄的代沟了。每次聊天，不外乎几件同样的事：诸如天冷了记得加衣服啊，上次总结的要赶紧改啊，以及一些思想道德教育之类的。我不想让他失望，我也知道这是对我好。我也想想，除了这些东西，还真没啥可以说的。但是每次面对这些话，我只想躲掉。

老爸一直相信我的资质。但正因如此，我感受到的压力很大。我甚至想，如果 WC 滚粗回家，他会不会是一声叹息呢。

还有谢老师。这是我高中以来一起度过时间最长的老师了。她真的为我们付出了很多。她一直说“尽吾志而不能至者，可以无悔矣”。可是这句话我越听越不安心。我没有“尽吾志”，愧对这句话。偷一下懒，会有一种深深的罪恶感。最怕的是，偷懒不会产生罪恶感了。对比起当年刚来长郡的时候，感觉真是变化很大。有人说我很努力，可我真的不觉得，我是在吃智力饭的吧。山外有山天外有天，智力饭又能吃到啥时候呢。

当谢老师从学校借来移动硬盘和笔记本的时候，我很感动。可是无条件给我那么多，我真的很受宠若惊。我相信谢老师的付出，但是如果我失败了，我怕谢老师在学校不好过。我不愿因为我，而是照顾关心我的人不好受。

last

写出来总感觉好受些。压抑久了，总会爆发的。

说穿了，以上写的全是心理的阴暗面。被生活压抑着，终却爆发了。

我算是一个不知好歹的人。给我那么好的条件，却受宠若惊。就是一个面子问题呢。

以前一直意味自己的心理承受能力很强，现在看也不过如此。

前一段时间写给本本的一段话，可以再拿来给自己吧。

我不知道这次 NOIP 你还悲剧，你会怎样。
你会后悔当年 OI 这条路吗？
你会后悔当年停课吗？
你会后悔高三还停课吗？
没有果实，你会后悔栽下那棵树吗？
没有结果，你会后悔当初的热爱吗？
没有收获，你会后悔青春的执着吗？

我不知道如果高考挂了你会怎样。
你，会变得坚强吗？

即使退役了，太阳正常升起。

以上，瑾献给我的 2012 。

今天刷小号的 = = ，然后其余人为了保证充足的睡眠以及有规律的生物钟没参加了。反正我的生物钟已经被完完整整地破坏了，那就大胆的被虐吧～

Solution

A

水题，暴力枚举每一位即可。

hack 人的时候发现只要枚举第一位就可以了，其余的全部填 0 。不过反正差不多快啦，5 min。

B

水题，枚举即可。

我居然看到有人判日期直接判 31 。随手一个数据过去就挂了。

还看到有人没判中间的 - ，本来想 hack 的，但是没时间了。

C

求出结束状态中的最小值，全部减去这么多，那么结束位置前第一个 0 就是初始位置，暴力模拟一遍就可以。

话说我一开始写的纯模拟，要交的时候觉得不太对劲，然后再看几遍发现有严重 bug ，果断改。

hack 错一个人，好伤心。

D

其实很水的啦。建立两个集合，每次随便取两个点，在这两个点之间连一条费用为其 sum 中较小的值的边，然后将 sum 值较小的那个点删掉，再更新两个点的 sum 。我们必须保证两个集合中一个为空时，另一个大小要为 1 。于是在 sum 相同的时候，删掉较大集合的点即可。

考试时我还脑残地用了 set 呢。

E

看了 YY 了一个思路然后觉得写不出= =于是没写了。虽然说还有一个小时，但觉得 rank 已经可以了（本来的目标就是 div1 嘛），于是就没写了，hack 人去。

填坑中。

和考场上一样的思路。首先离散化，易知至多只有 9!/(3!)^3=1680 种不同的 x y 坐标对，因为任意一个 x 都要把 n 个点分成两半，其中必有一半是恰好 3 个区域的点数。然后枚举，用主席树判断这 9 个区域的面积即可。时间复杂度 O(1680^2 log n) 的。

还蛮好写的。没啥细节的。

看懂了 tourist 代码之后觉得我就是个奇葩。你不是要维护前缀和么，尽管有那么多次询问，可是枚举垂直于 x 轴的两条直线，再枚举垂直于 y 轴的两条直线，每次你只会查 3 个区域的前缀和。那么每枚举一次 x 轴的坐标对时重新求一遍前缀和就可以了啊，还写什么主席树呢。

我写的 C++0x 居然比 watashi 的 Haskell 还要慢，不活了。

situation

一看 A 不是水题么。5 min 怒 A 。

一看 B 不也是水题么。写了好久= =。 18 min A 掉。

再看 room 里面有人 11min 过了 C ，觉得 C 也不难吧。但我觉得 D 可能可以搞出来，于是搞 D 去。

看了 D 的题目觉得没有思路，返回去看 C ，水题一个我去。差点交了暴力。36 min 。

再去看 D 。随手 YY 了个用 set 维护的算法，觉得也还靠谱，写完一交居然就 A 了 = =。 49 min 。

然后看 E 。在 1h10min 的时候 YY 了一个复杂度无法估计但目测很快的算法，但不准备写了， rank 还是蛮高的，hack 别人靠谱些。

于是一个一个 lock 掉。看 A 感觉太没 hack 点了吧，于是看 BC 。B 成功 hack 一个人，C 的一个 hack unsuccessful 了。

在结束的时候又看到有人 B 写挂了，但没来得及 YY 一个数据 hack ，sigh……

不过终于涨上 div1 ，rating 踩掉大叔了～

others

xiaodao 莫名其妙只过了 A、C ，B FST 了，D 没过 pretest 。

XLk B 被 hack ，D FST 了。不过他的手速给我好大的压力= =||。

hyc rank73 也不错了。

liouzhou_101 D 也 FST 。 D 的 trick 有这么多么。

然后手速蛮快的，还 hack successful 了一个人。如果没有 hack 另一个人，那么应该是 div2 中的 rank1 吧？

rating 曲线啥的，就两次那就算了吧= =

一时兴起玩了一下 awesome 某 tiling wm。似乎蛮好玩的样子。

优点

自定义。（噗，哪个 wm 不给自定义？ Mac OS X 太糕富帅了。）

啊不对，是高度配置性。awesome 内置了 Lua 语言。Lua 从本质上来说就一图灵机是波。而且还内置了若干高级内容呢，例如 lambda 和 closure 。语法倒也简洁明了，入门都不难的。

另外就是 tiling 了。大概就是无论何时都会把整个屏幕占满。左边开着 Firefox 右边 Emacs ，或者上下？蛮有情调的 = =。

还有， awesome 让我开始用上了虚拟桌面= =。没办法，一个 screen 肯定是满足不了需求的。每个 screen 有自己的 layout 方式，这点还是比较好的。

资源占用量小。目测比 KDE 少了 300MB 的内存（雾）。

缺点

特效啦啦啦～ wobby windows 这个效果还是蛮讨人喜欢的。不过现在都没移动过窗口了，就当有了没用到吧。

部分中文支持。发现了 awesome 的一个 bug ：中文标题栏，在窗口 active 的时候可以正常显示，在 inactive 的时候就会出现乱码。求如何汇报 bug 。

另外 Emacs 在 tiling 时发现有缝隙。

yakuake 在 floating 的时候动画有些 bug 啊，非 floating 的时候把屏幕分割地真的很丑。我在官方 blog 上看到了关于 yakuake 的说明，不过还没改= =。

其余的还好啦。

配置

先把 /etc/xdg/awesome/rc.lua copy 到 ~/.config/awesome/rc.lua 作为一个初始配置。

先改快捷键吧。我让 Mod4 + h/l 左右移动 screen ，感觉舒服些。语法直接模仿他原来的就可以了。

官方 wiki 蛮好的呢，要配置的话可以参考里面的代码。

然后加个一段自动运行程序的代码，fcitx、mpd 啥的都自动开吧。

如果要增加插件的话，先搞个 MenuBar 吧

git clone https://github.com/alexander-yakushev/menubar

然后按照 wiki 讲的配置就可以了。

另外如果要加 widget 的话，建议把 vicious 搞下来：

git clone http://git.sysphere.org/vicious

然后在屏幕最下方增加了一条，用来显示杂七杂八的信息。例如，mpd 蛮好玩的，就在屏幕下方放了个显示 mpd 当前播放的。然后加了个显示内存、cpu 的控件。那个 cpu 的东西特别不靠谱，显示的曲线都是不连续的= =。

summary

截图（求不吐槽我的审美观）：

有兴趣的可以试试啊。用起来蛮顺手的。

又跪了。rank 37 去了。

Solution

A

找到第一个 0 删掉即可。

如果全部都是 1 肿么办呢？随便删个都可以啊。

B

首先肯定是要数位 dp 预处理的。这个还好做吧，一遍 dfs ，枚举这一位上是啥就可以了。

接下来可以直接搜，也可以跑一遍背包。限制很强的嘛，搜不会 T 的。

叫你写搜不写 dp，写挂了吧？写挂了吧？

我居然脑残地没有算组合数。都说了要 先组合再排列 的啊，你肿么就忘了啊？

C

先排序。然后枚举 LCM 是多少，枚举 LCM 的因数，可以利用 lower_bound 快速知道有多种选择的元素有多少个。再去去重就好了。

D

不会做。T_T

后来 orz 了 jzp 的神代码，差不多看懂了。

令 p(w,x,y) 表示 w 次操作后， x 这个位置的数比 y 这个位置的数大的概率。每次交换 s 和 t ，就先令 p(w+1,s,t) = p(w+1,t,s) = 0.5 ，然后枚举其余每个位置 i ，令 p(w+1,i,s) = p(w+1,i,t) = 0.5(p(w,i,s) + p(w,i,t)) ，令 p(w+1,s,i) = p(w+1,t,i) = 0.5(p(w,s,i) + p(w,t,i)) 。然后 p 大部分是相同的，直接滚动更新就可以了。

E

这个脑残的每个点的链表直接转化为到根的路径嘛。

考虑 dfs 整棵树。和当前节点有共同数的点必定是若干棵子树上的，用 dfs 序维护。那么要维护 2 个操作：

1. 添加/删除一条线段
2. 求所有线段的总覆盖长度

这是一个很经典的线段树练手题。标记都不要下放的。

situation

看完 A 觉得水翻了，秒之。

B 一看要写数位 dp ，但感觉不难写，于是写去了。写了半天发现过不了 = = ，这样例真是精心手构啊。

感觉不能在一棵树上吊死啊，于是写 C 去。发现 C 好好写的，过掉。

然后看 E 有这么多人过，还是可写的啊，于是把 E 写掉。

这时还差 8min ，想把 B 过掉，但就是过不了，找不出哪里错了 T_T 。和主席二分发现超过 50 就要跪。

于是到最后调试发现 44 就会挂，原因是我没有考虑人与人之间的组合，每次要先选择若干个人，再令这若干人的幸运数码个数为多少，再算排列的，结果没有乘选择这若干个人的方案数了。

感觉 dp 就不会犯这种 SB 错误了嘛。

由于初始 rating 低，所以 rating 还是微涨到 2343(+19) 。

others

qmd 小号 sandytea AK 虐场。

xhm 和 xlk 半开黑，lydshy 大开黑。看 lydshy B 的 code 你就知道了。两人每道题提交时间相差不超过 5min。

主席脑残 E 没想出来。

cwx 的 rating 居然没变化！

liouzhou_101 和 zcwwzdjn （我真心怀疑这个 ID 是随手打的） 两人 C 都 FST 了，目测溢出了。

化悲痛为食欲！慢慢啃板栗中。

lambda

lambda 表达式听说过吗？先给一段 C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12

auto sqr = [](int x){return x * x; };
cout << sqr(4) << endl;

auto sqr2 = [](int x) -> int {
 	return x * x;
};
cout << sqr2(5) << endl;

function<int (int)> fac = [&] (int a) -> int{
 	return a ? a * fac(a - 1) : 1;
};
cout << fac(5) << endl;

这段代码会输出 16、25 和 120 。可以看出， lambda 表达式就是一个匿名函数一样的东东吧。你完全可以把 lambda 函数当成普通函数一样用。

当然，普通的 lambda 不可以递归，但是如果你不用 auto （很残忍吧），还是可以实现递归的，就像上面的 fac 。至于鼎鼎大名的 Y 组合字 嘛，感觉很厉害的样子。

可以看到 sqr2 和 sqr 是同一种函数，只是两个的写法不同罢了。我个人感觉 sqr2 好看些 = =，而且这种函数申明方式还可以直接申明全局函数呢。

closure

所谓 closure ，就是闭包。闭包就是建立 anonymous function 上的一个东西，就是记录的周围环境的 lambda 表达式。

比如说这么一段 C++ 代码：

1
2
3
4
5
6
7

auto gen = [](int a) -> function<int (int)> {
 	return [a](int b) -> int {
 		return a + b;
 	};
};
auto f = gen(3);
cerr << f(4) << endl;

仔细看 f 的定义，会发现 f 就是一个函数，这个函数接受一个参数 b ，返回构造时传入的参数 a + b 。那么在 f 中，已经不见了 a 的踪影，但是它又对 f 产生了影响。我们可以假设有这么个函数：

1
2
3

auto g = [](int a, int b) -> int {
 	return a + b;
}

但是我们想一部分一部分确定参数，也就是先确定 a 再确定 b 。为此 gen 函数就是接收一个参数 a ，返回一个函数 f ，而这个 f 中包含了 a 的信息。那么就可以说， f 就构成了一个 closure ，它包含了不在本地的信息。

unlambda

说起 lambda 表达式，就不得不让我想起这个奇葩的语言。

unlambda 中没有变量，只有两个函数。 k 作为一个普通的函数， s 貌似实现了 Currying 。Currying 后的 lambda 函数不就是 closure 嘛。好像有个专业名词叫做 SKI组合子演算 的样子。

题目不难是的吧。

TLE 1 的是 SB 是的吧。

7E

找 xhr 要 jzp 的数据，终于过了哈哈哈。

无数口老血喷涌而出。

你知道 95 分是肿么出来的吗？

你知道第一个点 T 的感想吗？

答案揭晓。

他数据中有 n = 0 的点，我是 getline(cin, expr) 读入的。

于是我读了一个空字符串。

可是，明明我在本机跑了这种数据的啊。毫无压力啊。

原因是，他数据是 win 下做的。

我在 linux 一测，发现读入了一个 \r。一口老血喷涌而出。

还差 178E3 呢。

题意

很简单，给一个 0/1 描述的二维图片，求里面有多少个正方形和圆。正方形的边不一定与坐标轴平行。每个点有 20% 的几率变成相反的点。保证人眼可以轻松识别出来。任意两个图形之间的距离不小于 10 像素，任意一个图形的直径不小于 15 像素。

想吐槽么。目测出数据的人要疯了。

Solution

其实我也不会，乱搞吧。

由于每个点 20% 的几率变成颜色相反的点这个条件太可怕了，我们考虑将整个图形模糊一下。一种方法是加权平均数，也就是每个点取相邻点的加权平均数，然后再取个整。权的话，我们可以模仿 高斯模糊 。我取了周围 9 个点，然后将整个图模糊 10 次。

经过模糊处理后，我们得到的图中，不仅有圆/正方形，还有若干个形状未知的小块。小块的处理很简单，题目保证圆/正方形的直径不小于 15 个像素，我们判断如果块的大小小于某个值（我取 200 ），就把这个小块的颜色全部取反。

没有了干扰点了。对于每个块，只需暴力 BFS 出块的大小 n 以及到中心点的最大距离 r ，对于圆我们有 n ~ pi r^2 ，对于正方形我们有 n ~ 2 r^2 ，所以我们取个中，判断 n 与 2.5 r^2 的大小关系即可。

现在是可以过 Codeforces 的数据了= =||，但是 tsinsen 上的数据实在太强，完全过不了 T_T。

常数优化

cin 读入要 2.4s 。坑死爹= =

判断圆和正方形

判面积是一种方法。这种方法比较怕的就是被模糊后的圆角矩形，因为到最远点的距离会减小。这样可以有 90 分。

还可以找中心点到边界最远点的距离与最近点的距离差？调整参数，分界线为 1.33 的话 92 分，1.35 有 94 分，1.37 有 96 分，1.38 和 1.39 有 98 分。

求凸包后再判？感觉也不靠谱啊，很容易损失正方形中间的点。

最后 98 分被卡的那个点应该是判不出正方形与圆吧，高斯模糊还是不错的。

恩，大概是这么个问题：

给定一个图，每次对于一个联通块，随机删除一棵生成树，期望多少次删完所有的边？

于是想了一下没有结果，打个程序试试，发现随机图上差不多就是 \(m/n\) 了。

关于这个数，xhr 说一定不超过原图两点间最大流的最大值，因为每次起码会破坏一条增广路。

然后呢？不知道了。

于是乎 xhr 又 YY 了一个题（据 Vani 说是 Asia Regional 2012 Chengdu 的原题）：

给定一个图 \(G = (V, E)\) ，保证 \(\|E\| \leq 5\|V\|\) ，每次修改一个点，查询一个点所有邻居的权和。

\(\|V\| \leq 2 \times 10^4, Q \leq 10^6\)

有了这个 图树剖分 还是蛮简单的吧。

我肿么感觉我就是打了一圈酱油呢？

update

从网上找到篇论文： Disjoint Spanning Trees 1 Forest Partitioning

里面有这么句话：

The minimum number of forests needed to cover the edges of a graph \(G\) is \[\max \{\lceil\|A\| / \text{rank}(A) \rceil: A \in E\}.\]

其中 \(\mathnormal{rank}(A)\) 的定义是 \(A\) 的顶点数减去连通块个数。

也就是说，如果没有重边，那么剖分数至多是 \(O(\sqrt{m})\) 的。随机图就更不用说了。好像用来骗分很爽的。

summary

还差 5 篇 solution 以及 tsinsen 上还有 7E、178E3 两个题没过。

果断要吐槽 tsinsen 上 cerr 要挂啊。还有可以直接上传源文件是吧， C++0x/C++ 你是如何分辨出的呢？于是 C++0x 就识别不出来了囧。

似乎有题 cin 被卡了？节操何在？！

然后还是有很多题蛮好玩的。

200A

吐槽 CF-200A 。lyx 实在是太不厚道了，竟然卡常数 = =|| 。最后优化了两次并查集才过的。 最后代码如下：

1
2
3
4
5
6
7
8
9

int find(int t)
{
 	if (f[t] == -1) return t;
 	if (f[f[t]] == -1) return f[t];
 	int r;
 	for (r = t; f[r] != -1; r = f[r]);
 	for (int x; t != r; x = f[t], f[t] = r, t = x);
 	return r;
}

C++0x

感觉最好玩的几个东西是：

auto
range-based for
lambda
unordered_map/unordered_set

想吐槽 C++ 里面不能函数套函数？今天突然想到可以用 lambda 啊。

还有 vector<vector<int>> 可以编译通过了！

又被虐了。rank 26 ，T_T 。本来是一次大好的涨 rating 的机会啊。

Solution

A 给每个数建立一个 vector 。再枚举两个数，求出共有多少段，更新答案即可。复杂度是 O(n^2) 的。 注意要把只选一个数的情况特判掉

B 二分答案。求奇葩图形与矩形的交，容斥一下就好了，也可以暴力 for x 坐标。

C 只要注意到 SG(x) 至多和 SG(sqrt(x)) 相关就可以了。暴力求出 3e6 以内的，记录前缀和。 还不知道 xhr 他们的表是怎样打出来的呢

D 暴力四维 dp 打表即可。

E 可以直接线段树暴跑，也可以用 set 来维护区间。mod 777777777 比较恶心，我的方法是用线段树来维护积，反正复杂度不变 = = 。

situation

A 没特判，结果 FST 了。

C 看错题了。我以为是减去那么多个。

D 以为表打不出。

E 写完就过样例然后 A 。

others

xhr 以 tourst2 强势虐场，13 min A 掉 E。

CLJ 重回 rank4 。

XLk、ACMonster 强力虐。