Farewell

OI 生涯已完结。谢谢各位的关心与支持。

没什么好说的。能认识这么多人我也很开心了。

遗憾是肯定的。可是没办法，考试的残酷在这里表现的淋漓尽致。

一帆风顺的生活到此结束。不一定要活在别人的视线中的呢。

考挂自己弱，LYP 最弱。（XLk：版权！版权！）

Life

流水帐啥的就不写了，吐槽几点吧。

首先要吐槽宾馆= =||。还真就是个公寓式宾馆啊，居然提供厨房 -_- 。灯奇暗无比，网速呈脉冲型分布，故美其名曰：一大波流量正在接近。被子真心感觉薄。

UESTC 发了个啥 U 盘，样子到蛮好玩的，不过……一体机被卡了差不进去啊亲！

伙食嘛……第一天在旁边的一个川菜馆吃的，味道的确正宗，够麻。但是……分量倒是不多，某道鱼里面只有 5 片鱼肉（yxj 怒抢两片）。后来一直吃食堂。 贴吧上一堆人吐槽：少放点辣椒会死啊。 为啥我完全没吃出辣味啊。

还有这饭的质量确实让人捉鸡。连长郡食堂都比不上。不过早餐还是蛮不错的，油条泡豆浆真心舒服。

和 XLk、gjq 一起吃饭实在是太虐心了。gjq 衡水中学的有木有啊！！吃饭速度实在是太快了有木有！！

由于每天都在空调房里，导致脚出汗特别多……于是又化脓了哭。

XLk 真心高（一米九啊亲）富（连键盘都自带）帅（目测一堆妹子追？）啊。坐在他旁边亚历山大啊。

LRJ 在讲课的时候准备叫 jzp 回答问题，结果发现 jzp 睡着了，不忍心打扰他。钱桥：遇到这么好的老师你就嫁了吧！

机场的网速比宾馆快有木有！！ 机场遇到来旅游的学姐了有木有！！ 机场遇到了 hwd 和 ayq 有木有！！ 机场有机器可以免费上网/看视频有木有！！

吐槽：“双流机场” -> “二流机场”

闭幕式表演节目，hym 和谁（抱歉我不认识= =||）两人对唱《因为爱情》太高能了有木有！！只可惜当时相机不在我这里没法录像。学军 + 丽洁的《法海你不懂爱》无法直听有木有！！

营员交流，dyh 太可怕了……要不是我提前开挂看了 pdf ，不然根本就听不懂啊。话说这掌声真是人民群众喜闻乐见，讲到二项式反演时集体鼓掌，hwd 报时还剩 10 min 的时候集体鼓掌，还剩 1 min 的时候集体鼓掌，还剩 10s 的时候掌声雷动！不过最郁闷的是最后下来的时候还不忘黑我= =||

为啥营员交流 day1 的是 4 个 ppt ，day2 的是 3 个 beamer ？

最后讲课那天 hjf 将的东西蛮好玩的，可以去试试嘛。

文学巨匠 wzy ：我看过《约翰·克里斯托夫》。

• 大家好，我是来自石家庄二中的 LYD 。——by liouzhou_101
• 大家好，我是来自广西柳州高级中学的 WQS 。——by lydrainbowcat
• 大家好，我是 MIT 的 GYZ。 ——by WJMZBMR
• 大家好，我是来自青岛二中的王强松。——by lydrainbowcat
• 大家好，我是来自唐山一中的 SHY 。——by kAc
• 我是唐山一中的 SHY ，你快来黑我呀。——kAc to lydrainbowcat

小朋友看见我说 XLk 就说溴分快什么心态 = =||

Examination

第一题一看就一裸题啊，平面图转对偶图，然后点定位再写个倍增啥的就好了。可是可是可是，写得出来吗？

第二题一看想到了《小 Z 的袜子》，然后再一看想到了 COT2 ，然后就把它当成了 COT2 来写。

第三题看一眼没啥好思路，于是就放一边吧= =||

后来证明没做第三题是绝对错误的。那么多个点那么好玩，我完全没做啊。每个点全 0 骗了几分，用 checker 做第 9 个点骗了 10 分， 5 分钟怒写高斯消元过第三个点，第四个点骗了 4 分，然后没了，只有可怜的 31 分。这个题完全是最可做的啊。怒黑 XLk 第三题全场第一。

第二题其实还好的，写 70 分的莫队算法差不多了。想起了各种 sqrt 爆搞，但是觉得不太靠谱怕被卡常数，于是辛辛苦苦写了 Manhatton-MST 。（我去退役了在乎啥常数啊。）比较囧的是最后才拍出一个错误，就是某种情况下有些询问没有和最小生成树连通= =||，于是怒 for 一遍，没有连上去就直接连到 1 号点，然后普通情况下不错？算了就这样吧……

第一题实在是难写啊……先写平面图转对偶图了。想写 100 的算法发现写不完，于是怒写 70 的；再发现写不完，怒写 50 的；仍然写不完，转写 30 ；再发现怒写挂。

结果很凄凉。第一题玩脱了，完挂。第二题 70 + 第三题 31 = 101 。翻盘无望。退役了。

cherudim 以 0.02 分被 hym 强踩。momo。

liouzhou_101 打错第一题文件名了。

xpd、yzc、ldf 的优势被 WC 完卡。

Epilogue

两年半的 OI 生涯结束了。

pty sillycross 文学巨匠wzy 继续努力吧。默默祝福。

fotile 明年还有一次机会呢。祝你好运。

cherudim momo……不必太悲伤了呢，想开点吧。

XLk liouzhou_101 kAc xpd lydrainbowcat qdc dyh lyx 一起加油吧。

能认识你们真是我的荣幸。

谢老师、向总：很抱歉我没能完成任务。感谢您长期以来对我的关心、帮助。

遗憾也好，后悔也罢，就让这段 OI 历史成为我高中生活中最美好的回忆吧。

远处的地平线 闪耀着光辉
那是因为 有你在身后
点滴岁月令人如此怀念
是因为 有你相伴

世界不停转动 有你藏在其中
发亮的双眸 闪烁的灯火
世界不停转动 伴随着你
伴随着我们 直到重逢之日

Future

又回到最初的起点。

得考虑生存问题了。大学还是得继续的呢。

具体规划啥的还没出，不过大概说一下吧。

想进 IIIS 还真就不容易呢。

物理高数线代具数都看看吧。

然后怒学英语。

还要为学校做几件事的呢。

那个 MIT Challenge 貌似很好玩的样子。不过全部学完是不可能的，就当做是学英语了 T_T

ACM 啥的还是准备搞搞，CF/TC 啥的都玩玩吧。（怒求队友。请做好被坑的准备。）

小朋友也要辅导一下的说。

某人（特指）你加油呢。尽力就好，再惨不会比我惨是啵。

Winter Camp 的讲稿。

update: RTM 已出。

想要的人去下吧。src 神马的在 github 上自己去找吧。

链接在此

如果你会用 git ，你可以直接：

git clone https://github.com/roosephu/slides.git

内附 org/tex 。

谢谢大家的支持。随便乱讲一些东西，不要当真。感谢 XLk 指出错误。

快退役了吧。

最后再疯狂几次吧。

——谨以此纪念我的 WC 前最后一次 TC 。

summary

250pts 的速度一般般，但 500pts 的手速比较快，所以能混到 50+ 名。

总体来说 rating 还是涨了， +44 也还不错了。

Solution

250 points

我觉得最好写的方法就是容斥了。

把那个啥 sqrt 拆开，可以得到只要 AB 为完全平方数，那么 (sqrt(A) + sqrt(B))^2 就是整数。所以我们要统计的就是有多少个 AB 为完全平方数。而 AB 为完全平方数的充要条件是 A/x 和 B/x 均为完全平方数，其中 x 为 gcd(A, B) 。

令 f[i] 表示当 x = i 时的 (A, B) 数目。全集为 floor(sqrt(n / i)) * floor(sqrt(m / i)) ，我们要减去的是那些 gcd 不是 i 但是仍然

500 points

1000 points

others

XLk 看错题了。但是总 rating 还是比我高，瘦死的骆驼比马大。

cherudim 和我聊天去 = =|| ，于是没咋 cha 人。

哭瞎了。

OI 生涯最后一次 CF 做小号然后怒跌。

幸亏没用大号做……否则要会黄啊……

Solution

A

双端队列就可以了。读到一个 l 就在右边插入 i ，否则就在左边插入 i 。

B

直接 dp 就可以了。转移的时候优化一下，记录 g[i] 表示 i 的倍数的最大的 f 值，每次 O(sqrt(n)) 利用 g 来求 f， 再用 f 来更新 g

C

观察数据范围发现 O(nq) 可过，但是 O(nq log n) 也许会超，考虑每次询问重新处理。令 f[i] 表示选取第 i 个球的最大收益，通过枚举最后一个球的颜色来转移。由于只有两种可能性：与上次颜色相同，与上次颜色不同。对于每种颜色维护最大值，线段树查询。

这样会 T 。其实只要维护最大的两个元素就可以了，不用线段树，复杂度降至 O(nq) 。

D

考虑枚举 S 中的每个位置，实时维护 T 中的所有可行位置。

维护两个量， L, R 表示 S 在当前位置时， T 最近、最远在哪里。那么所有可行的位置一定在 [L, R] 内。但并不是所有的位置都是可行的，考虑在当前位置前一位时 [L, R] 内的所有相邻元素，如果相邻两个是 [S[i], S[i - 1]] ，那么 i 这个位置是不能到达的，减去即可。可以证明，其余的位置都可以到达。

E

rng_58 的程序居然这么暴力。哭瞎。

令 f[i] 表示从 i 开始的 LIS 的长度。暴力维护 f 。

插入：由于高度小，只有高度比他小的元素， f 才会受到影响，暴力更新。

删除：由于序号小，只有序号比他小的元素， f 才会受到影响，暴力更新。

situation

首先做了 A ，还是很快的。

然后看了 B 后觉得记录约数是可行的，于是写了。（然后不小心写挂了 T_T）

然后脑残想去 cha 人？于是 Lock 了 B ，然后一个人都没 cha 到。

感觉不行啊，要跪的节奏啊，于是看 CDE 去。

C 瞬间 YY 出 O(nq log n) 的怕 T 不敢写。

一看 E 那不是原题么肿么没人做啊。于是写啊写写啊写好开心～过样例了好开心～交上去 WA 2 了好开心～再仔细一看看错题了好开心～T_T

完了彻底玩脱了。于是赶紧补 C ，YY 出一个 O(nq) 的。结果维护最大的两个值的时候维护错了，交了 4 次才过。

E 题无望，D 题或许还有点可能性。于是继续 YY ，YY 出一个算法了好开心～手跑过不了样例好开心～

继续 YY ，经过各种常数微调似乎可以过样例好开心～3 个样例交上去就 WA 4 好开心～

于是乎小号都会跌……T_T

这大概是除了那次 Bayan 外跌得最惨的一次了……

others

liouzhou_101 稳定发挥 rank 16 怒虐场。

wwwwodddd rank 53 也不错。

cherudim 终于可以不用熬夜了。

大叔只过了 B 。不过遇上了一件奇葩的事：有人用大叔的 ID 交程序 = =|| 。这是肿么做到的……

nonsense

今晚 8 点有 TC 。没小号给我撑着大号要怒跌了。

刷小号。差一点就可以虐场了 T_T。

Solution

A

签到题。q 只需求个 min 就可以了，然后把 a 排序一路扫过去，能用就用。

B

dp 。先要转换一下思路，把答案分成若干份： ans = 前 1 个人能塞进去的概率 + 前 2 个人能塞进去的概率 + 前 3 个人能塞进去的概率 ……

然后就可以 dp 了。令 f[i, j, k] 表示前 i 个数中选了 j 个数，这 j 个数的和为 k 的方案数。然后枚举当前数选不选即可。

提供另一种思路：统计每个数字出现的次数，令这个数组为一个状态，每次枚举选哪个数。记忆化一下即可。

C

先把这个表打出来，统计每行的和，发现 m + 1 行的数的和为 2^g(m + 2) ，其中 g(x) 表示 x 的二进制表示中 1 的个数。然后就是一个简单的数位统计题了。

D

被卡常数了求破。

如果 t > maxb \|\| t > n ，那么显然可以直接输出 b 中不同数的个数。

这样就可以保证序列的长度不超过 nt 也就是 2 * 10^7 。然后暴力跑最长上升子序列即可。

注意时间复杂度的估计，不是 O(nt log nt) 的，而是 O(nt log ans) 的，而 ans < min(n, maxb) ，所以有一个 0.5 的常数。

我当时就是这么写的，但是这样是会 T 的。一个比较简单的剪枝是如果答案到达上限，那么就直接 break 掉。但是仍然会 T 。再加一个常数优化：对于位置 i ，这次二分的位置不会小于上次二分的位置，于是从上次二分的位置开始二分即可。加上这个常数优化就可以过了。

E

不会。挖坑

situation

首先看了 A 题，水之。

然后看完 B 第一反应不会做，第二反应是作业中的一道题，然后就有了这个 idea ，然后 dp 超好写的说。

接着看了 CDE 三个题，感觉都不太会。刷新一遍看到 C 有人出了，于是开 C 。

推了一下没推出啥结论，然后打表发现都是 2 的幂，瞬间想到二进制表示中 1 的个数，然后就有结论了。

写了好久过不了最大的样例，到最后才发现有个地方需要 + 1 我忘记了，浪费了好多时间 T_T 。

借助刚才想的思路，立马写 D 。然后写了个随机的 generator ，发现无压力，于是直接 submit 了。

YY 了一下 E ，暴力 dfs 发现所有合法的数并不多，但是没想到肿么处理。于是 cha 人去。结果一个人都没 cha 到。

然后发现 D FST 了。哭瞎。

后来优化了一下常数就过了。

现在 rank 是 20 ，如果 D 没挂，那么可以直接 rank 3 。第一次 CF 是 rank 1 ，第二次是 rank 2 ，第三次是 rank 3 该多好啊。T_T

others

liouzhou_101 D 题同样 FST ，TLE 11 比我还惨。

ryz 怒 cha 两人。

ryz 、XLk、shangjingbo、pty、hyy、ChnLich 一堆人中规中矩，过了 ABC 。

jzp、cwx、gsh、大叔只过了 AB 。

秋锅只过了 A 。

xiaodao 怒挂 B 。

nonsense

闲着无聊把 RSS 架了起来。有兴趣的同学不妨订阅一下嘛。（目测没谁有兴趣……）

嘛，今天 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 了，目测溢出了。

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