题目不难是的吧。

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>> 可以编译通过了！

又被虐了。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 强力虐。

Solution

250pts

比较水啊。稍微转换一下思路就可以想出来的。 f(i,j) 表示前 i 个怪物用 j 块钱最多可以得到多少的伤害值，然后枚举当前怪物是买还是打就可以了。不过我还不知道 cha 点呢。

500pts

也不难吧。

首先是要把 SG 求出来。这个我是马上打了一个表然后就找出来了， x 的 SG 值就是 x 的质因数的指数和。这相当于普通 nim 游戏中，石子有不同种类（2,3,5,7 之类的），每一堆直接由这一堆石子的积表示出来。

由于区间长度较小，直接 O(L log L) 求 SG 就可以了。从小到达枚举质数，上界为 sqrt(R) 。超过上界仍然分解不完全，那计数器再加一。

至于统计答案嘛，告诉你用前缀 SG xor 和你还不会？

很多人被 cha 目测是 sqrt 分解质因数去了。

1000

只看了题目，不会做。 update: 2012-12-23 已经会做了。某次失眠时 YY 了一个做法 ms 是对的。

如果我们知道了 ABC 彼此之间的距离，剩下的就简单了。那么 AB、BC、CA 三条路径会覆盖若干个点，一个点被这三条路径覆盖的条件是以下条件至少满足 2 个：

1. d[A,i] + d[B,i] = d[AB]
2. d[B,i] + d[C,i] = d[BC]
3. d[C,i] + d[A,i] = d[CA]

这种点的位置是唯一的。对于其它的点 x ，我们一定可以找到一些点 y ，使得 d[A, x] - d[A, y] = d[B, x] - d[B, y] = d[C,x] - d[C,y] > 0 。对于这些点，我们任意找一个连上去即可。

现在还存在一个问题：如何找出所有可能的 AB、BC、CA 的距离？如果 AB 中存在非 C 的点，那么 AB 的距离等于最小的 d[A, i] + d[B, i] ，如果 A 或 B 在 i 到达另一点的路径上，那么 AB 距离等于最大的 \|d[A, i] - d[B, i]\| ，如果以上都不是，那么 AB 还可以等于 d[A, i] + d[B, i] - 2 d[C, i] ，这种情况就是一条 A-C-B 的链，然后某点通过 C 连出去。

既然 AB、BC、CA 都只有 3 种可能，爆枚即可。

others

rejudge 强力 target 。

tourist 悲剧 500pts 的没出。

XLk 凭手速又虐我。

zcwwzdjn 虐我 1 分多一点。

大叔又一次没爆零，真是太开心啦。不过他 250pts 的只交了 98pts ，结果被某人以不交程序怒 cha 得 100pts 强踩。

话说 XLk 跟我讲了他上次 rank1 后的事。有人对他产生怀疑，于是 t-mac 的管理员就和他扯淡去了，然后他的方法和 rng_58 的还不一样。

nonsense

好开心啊，终于涨红了。这是 rating 折线：

最近几次 TC 都没啥做好的。一开始 2034 ，想一次涨红还是有可能的；一次之后是 2142 ，一次涨红还是可以的；又一次之后是 2158 ，一次涨红还是可以的；又过了一次是 2174 ……我彻底无语了。不过这次红了还是蛮好的。

吐槽

我肿么又和 ahxun2006 一个 room ？这是连续几次了？