0%

又跪了。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 这个位置的数大的概率。每次交换 st ,就先令 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_101zcwwzdjn (我真心怀疑这个 ID 是随手打的) 两人 C 都 FST 了,目测溢出了。

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

题目不难是的吧。

TLE 1 的是 SB 是的吧。

7E

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

无数口老血喷涌而出。

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

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

答案揭晓。

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

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

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

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

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

还差 178E3 呢。

lambda

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

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 组合字 嘛,感觉很厉害的样子。

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

closure

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

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

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 产生了影响。我们可以假设有这么个函数:

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

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

unlambda

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

unlambda 中没有变量,只有两个函数。 k 作为一个普通的函数, s 貌似实现了 CurryingCurrying 后的 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\| <= 5\|V\| ,每次修改一个点,查询一个点所有邻居的权和。

\|V\| <= 20w, Q <= 100w

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

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

update

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

里面有这么句话:

The minimum number of forests needed to cover the edges of a graph G is
    max{ceil(\|A\| / rank(A)) : A in E}

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

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

summary

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

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

似乎有题 cin 被卡了?节操何在?!

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

200A

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

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] ,如果 ABi 到达另一点的路径上,那么 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 折线:

Sorry, the picture can't be loaded

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

吐槽

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

另外最囧的是明明是 SRM-565 的题我标题写个啥 SRM-564