嘛，今天 rp 蛮好的，于是 rank 11 了。 rating 怒 += 139。

Solution

250

直觉告诉我合法的方案只有几种特定情况。

枚举后发现是 4 种： 1. 一条边都不选 2. 选一条边 3. 选一个点，然后选这个点的若干条邻边 4. 选一个三角形

然后枚举就可以了。

500

第一眼：不会做。

第二眼：好像可以矩乘。

第三眼：好像矩乘会超。

第四眼：不会做。

第五眼：优化掉一维？貌似可做了。

恩，大概就是这样。

如果你没看懂，还是解释一下吧。

一个 \(O(n^3 \log d)\) 的矩阵乘法是显然的。 \(n\) 一定是一个循环节，预处理 \(n\) 步之后到达各个位置的方案数，然后就可以直接矩乘了。

但是暴力矩乘是会超的。观察后发现，我们并不一定要记录若干步后从 \(i\) 到 \(j\) 的方案数，只需记录 \(i - j\) 为一特定 \(\delta\) 时的方案数即可。即，矩阵中 \(i - j\) 相同的若干个元素一定相同。于是需要维护的量从矩阵降为一个向量，然后暴力乘过去就可以了。如果你足够牛且特别想装 13 ，你还可以写个 FFT/NTT 啥的。

1000

不会做，挖坑中。

现场居然没人做出来？似乎 lyrically 上手就做 1000 结果爆零了。

situation

一看 250 蛮简单的嘛，水掉。

一看 500 似乎也不难，水掉。

然后觉得没啥可做的了， 1000 目测想不出来，而且样例都特别强，cha 人基本上没啥希望，于是到一边玩去了。

然后考手速混到了 rank 11 ？ 根据 RP 守恒定律，目测下次 CF 要跌了……T_T

others

（正当我准备看其他人做的肿么样的时候，TC 连接不上了= =||）

XLk 晚了一步，没能报上名。

ryz rank 53 也不错了。

xiaodao 第一题交的很慢于是分数很低。

大叔由于找笔耽误了几秒，导致 250 没调出来，于是凄婉爆零。momo。

秋锅过了第一题。

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

其实 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 了，目测溢出了。

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

题目不难是的吧。

TLE 1 的是 SB 是的吧。

7E

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

无数口老血喷涌而出。

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

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

答案揭晓。

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

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

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

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

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

还差 178E3 呢。

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组合子演算 的样子。

题意

很简单，给一个 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>> 可以编译通过了！