老早以前老师就说要做个内部 OJ ，上届的学长带了个好头，搞出了个烂首工程= =|| 然后再无下文……鉴于退役后无所事事，于是搞来玩玩消磨时间倒是蛮不错的。

昨天搞完了 safe-run ，可是后来看看

根据 fanhq 在北京集训的时候讲的东西，我决定写一个程序，能够“安全”地运行其他程序。

这个程序的主要思想就是利用 ptrace 这个函数。由于用户态的程序不能做任何事，而用户态到内核态需要调用系统函数（简称 syscall 吧）， ptrace 支持跟踪一个进程，能够截获每个 syscall 。我们在每次 syscall 的时候检查调用的函数是否合法，例如是否运行了外部程序/读写了外部文件，所以能够相对安全地运行一个程序而不用担心可怕的 rm -rf / 。

一开始决定用 python 写，安装个 python-ptrace 库觉得差不多了。结果完全不会用啊亲！连猜带蒙 YY 了好久最后还感觉弱爆了，如果程序连续向文件写入 n 个字符，那么需要调用系统函数 read n 次，每调用一次我要检查 read 的参数是否合法（也就是是否打开了不允许打开的文件），如果用 python 来写，那么 IO 效率将惨不忍睹啊。遂决定还是用 C 写吧。

然后准备加入一个功能：卡时/卡空。fanhq 用的是 setrlimit/getrlimit 来限制资源。一旦要超时了，系统会向程序发送一个 SIGXCPU 的信号，然后被 runner 捕获，就可以实现卡时了。但是一个很囧的问题是：setrlimit 限制的是 CPU 时间。如果程序 sleep() 一下……慢慢等去吧。正在为这个感到蛋疼的时候，想起了一个问题——什么程序需要 sleep 啊？我就直接把 nanosleep 这个 syscall B 掉就可以了嘛……

fanhq 在他的程序中给每个 syscall 造了个表，我后来发现 /usr/include/asm/unistd_32.h 这个文件中有个 syscall 的列表，于是直接蒯了= =||

现在另一个很囧的问题是——似乎每个 syscall 我会捕获两遍。是本来就要调用两遍还是我写挂了啊……

玩脱了，目测要是用大号或者小号的话都会跌吧，幸亏用小小号 lol

Solution

A

水题，记个 max 就可以了。

我会说我看题看了 6min ？

B

对于相同横坐标的可以用很多种排法，这个用阶乘计算。然后除去 2 的满足 A[i] = B[i] 的 i 的数量次方就可以了。

如何除呢？约分就可以了。

C

构造。可以证明，任意一个满足要求的图都可以找到一种方法。考虑一个点，只要这个点周围和它在同一个集合的点的数目不超过和它在不同集合的点的数目，那么这个点就是满足要求的，即邻域中与它在同一个集合的点的个数一定不超过 1 ，因为这个点度数不超过 3 。

所以调整一下，每次选择一个超过的点，换到对面集合里去即可。由于每换一次，矛盾数会减少，所以这个调整总是可以结束的。

我就不吐槽这个题是 原题 或者 原题 了。

D

dp 。显然这个连通块一定是凸的，我们令 f[L, i, j, s] 表示前 L 列，第 L 列的范围为 [i, j] ，且边界状态为 s 的方案数。什么是边界状态呢？考虑上边界，一定是先上再下的，下边界一定是先下再上的，我们就把这个定义为边界状态。

转移的话，如果暴力枚举上一列的范围，复杂度会很高，于是记个前缀和就可以了。

一堆人蒯源代码 T_T……我还是不吐槽这是 原题 或者 原题 了。

E

不坑不科学。

situation

刚被 TC 打击到，现在又要被 CF 打击了。

看了好久 A 的题目才看到有张图。然后随手写个程序就是过不了样例，最后 YY 了好久才过样例 sad

然后看完 B 后想了一个错误算法……因为我想错题了，于是怒 WA #3 。最后是 44min 才过了 B 。

看了 CDE 觉得 C 题似乎考过的样子，但是当时靠着数据水骗了过去，现在不行了。于是就没写 C 了。

D 题看一眼觉得是 dp ，但是很难写的样子。E 没啥想法。我决定还是写 D 吧。

写啊写写啊写一个函数忘记返回值为 64 位贡献一次 WA #11 然后改了后就过了。

后面也没心思写题了，觉得也写不出啥了。但是后来发现如果有想法了，那么 C 还是可写的，代码量真的很少啊亲～

最后就挂了嘛，毫无疑问地挂了嘛。#64 哭了。

others

有人猜得到我第一句话应该是——

强烈谴责 XLk 的虐场行为！

D xiaodao 直接把 Petr 的 java 代码交了上去， XLk 还算良心，还改成了 C++ 代码 = =||

然后 XLk 在 1:58 的时候交了 C 过了。然后就 #12 了。

文学巨匠靠着 D 的手速混到了 #33 也还不错了。

hza 靠着每个题速度都不差混到了 #49 。

我就是太慢加上贡献了两次 WA 导致被虐残了 T_T

scottai 似乎是倒着做题的 = =|| 然后就挂了。

edly 居然 C 没过。

nonsense

XLk 的大号被小号超了！看来如果我再不做大号就要被 XLk 虐飞了（现在已经被虐出翔了） T_T 。

又被虐残了。强烈谴责 XLk 虐场。

#solution ## 250 一看就知道是水题嘛。模拟出一次之后的变化然后根据模 4 讨论一下就可以了。

我就不说我只有 150+ 了。

550

首先要把代价表示出来吧。我们发现， cost = 2 * components - 2 - vertices 。于是我们统计加了 2 之后的好了。

具体怎么搞呢？dp 。 f_{v, ca, cb} 表示 v 这棵子树，和 v 颜色相同的一部分的已有代价为 ca ，其余部分的代价和为 cb 的方案数。转移就是枚举孩子的状态。

复杂度感觉很高的样子，于是用 map 来写= =|| 想优化常数然后过了。但是直接数组就可以了嘛。

900

当然是坑。

situation

看完 250pts 发现这不是水题吗？于是开始码代码。

好的，用 x y 这两个变量来描述一个位置，然后似乎不好写啊？

好吧我就用 complex 。

好吧发现我不会用 complex ？还是老老实实地两个变量吧。

于是时间哗啦啦的流，然后就只有 150+ 分了。

再看 550pts 发现不会做啊。没有草稿本啊于是赶紧上画图。

好像是可做的？复杂度好像高了点？不管了用 map 看看能不能骗过去= =||

然后还真就过了= =|| 。其实数组就可以了啦。

交完没几分钟就结束了。

others

XLk 你不仅虐场，你还虐心啊。#3 啊亲~求抱大腿啊。

xiaodao 第一题有 230+ 于是 #20+ 也不错的说。

好多人第一题都有 200+ 于是我被虐飞了 T_T

最后 #40 ，也不算一个特别坏的结局吧。

nonsense

我说 TC rating 的 delta 能不能大一点啊。我看我的 delta 大部分都不超过 50 啊亲~

看人家 XLk 人生大起多痛快，一次 #1 一次 #3 。有这两次我也就满足了。

晚上居然还有次 CF 。

刷小小号呢。

一次大好的 rank1 的机会就被浪费了，好桑心……

不过 rank5 也还不错的说？

Solution

A

水题，枚举即可。

由于这几天写 Haskell 于是顺手用 Haskell 来写 = = 发现手速更慢了。

B

水题。预处理出每个数至少要加多少次，统计每一行每一列的和即可。

C

构造。有很多种构造的说。

无解显然是 n < 3k 。

我的： 1 1 2 1 2 2 循环很多次，如果 k 是奇数那么就是 k k 1 1 2 1 2 2 k 。

另一种： 1 1 2 2 ... k k 1 2 ... k

D

据说 hash 挂的很惨。

其实 trie 很好的啦……不过我写的不是 trie ……我把所有字符串全部排了序，然后减去 LCP 的长度和即可。

E

这个题就不太简单了。

首先可以证明： (x, y) 可以变化到任意一个 (x + a, y + a) ，不管 a 的正负。做法如下：

(x, y) -> (y, 2y - x) -> (x, 2y - x) -> (ceil(x/2), y - floor(x/2))

可以发现， 这两个数的差仍然是 y - x ，而当 x > 1 时， ceil(x/2) < x ，所以我们最后一定可以得到 (1, y - x + 1)

接着另一个结论：若 x 是奇数，那么 (1, x) 可以得到 (1, ceil(x/2)) 。显然嘛。

然后引出终极结论： (x, y) 最后可以变成 (1, 1 + t) ，其中 t 是 y - x 最大的奇因子。而能产生 (1, a_i) 则要求 t 是所有 a_i - 1 的因子。

于是暴力枚举 t 即可。

situation

在家做笔记本没手感啊。

看完 A 这不水题一个么……速上 Haskell 发现好慢 T_T

看完 B 这不水题一个么……怒上 C++0x ……数组开小了 FST 了啊……哭瞎了啊……

看完 C 同上。随手 YY 一下即可。

看完 D 同上。第一想法居然是后缀数组？发现长度只有 1500 ？暴力建后缀数组吧 = =||

看完 E 发现不会做啊。YY 了若干久没啥好想法，发现没草稿本啊亲……于是只好用画图 YY 了。

结果乱 YY 一个结论居然过了全部样例？好吧就这样吧。

然后开始 cha 人。看了半天没想法，看着 E 题某人只判 t = 2 的情况，于是想 cha 掉，然后挂了 T_T 。截图如下，我多么希望网速能够慢一点啊。

others

XLk 和 xiaodao 开黑……然后两人的 DE 全挂了……

xiaodao 只做了 DE 。是懒得刷 ABC 吧。

liouzhou_101 似乎没搞出 E ？还是 D 用的时间太久了？

zrx 小朋友一开始说要做的，结果不知道做没做，我还不知道他 ID 呢。

然后没谁参加了……

nonsense

现在大号红了小号黄了小小号紫了 div1 的各个颜色都有了。

昨天小朋友要我帮忙给他凑 ID ，原因是他看了 lkf 的 ID ： VFleaKing ，就是把名字 shuffle 后凑出一个还过得去的单词吧。他凑了好久凑出个 penguin ，但是还有 4 个字母 gaxy 死活凑不出了，要我帮忙想想。

嘛，这东西果断给机器做好啊。于是到网上搜英语词典，找到了一个 包 ，用 Python 处理把里面的所有单词全部提取出来，做了一个单词库。另外所有的单个字母都出现过了吧，还得特判掉呢。

我下的这个包比较囧，有些地方有空行，有些地方一行会断成两行。空行的我直接特判了，第二种还真就没办法，只好不处理这个文件了……不过这里面的全是 v 开头的单词全部忽略掉算了吧。

接下来就是暴搜了，没啥技术含量，我就直接拿我自己的名字做测试了。每次枚举下一个单词选啥。由于有些单词过于奇葩，所以又造了个 spam word list ，比如说你听说过 pl 这个单词吗？果断屏蔽掉。

发现了几个比较搞笑的东西：

u no lip guy
你这个没有嘴唇的家伙……233

gun lip you
枪 嘴唇 你……我勒个去这是有多 zkw 啊

i upon ugly
我 在...之上 丑 …… 物极必反么亲？

only pig u u
不想吐槽了。找喷啊你。

不过还是发现一个比较正常的：

guy up lion
狮子上的家伙……狮子王？

好吧就是这样很无聊的一个东西= =|| …… WJMKXMR ……

update:

自从写了这玩意后小朋友们纷纷要玩，于是找出几个比较还不错的：

i judge rein
我审判缰绳

hog in maze
迷宫里养猪。《论让猪不溜走的好方法》

angel conch gin
天使海螺杜松子酒。好酒！

gaze in ohm
专注于欧姆。物理帝。

quad shine
四倍闪耀。啥牌子的洗发露？

glance chignon
瞄一眼发髻

然后再把我以前的 ID 输进去发现：

ours hope
我们的希望

pure shoo
纯十拿九稳

pro house
专业房

hero soup
英雄汤，一口让你变英雄。

其实，到目前为止见过的最好凑的还是 XLk 的名字：

bike

天然中有木有！

被虐得飞起。果然退役了就暴露了一堆问题的说。

和 XLk 开黑。XLk 居然用新小号在 div2 进行了惨无人道的虐场，在此提出强烈批评。

Solution

A

水题。只需对于每一种大小的盒子算出要多大的盒子即可。

注意这组数据：

1
1 1

然后没了。

B

很显然这个题 m 和横坐标都是没用的，答案就是 n - LIS 。

似乎我把 LIS 看成了 LCS 然后怒坑 XLk ？

C

居然不会捉……还是 XLk 教我的。高下立判。

事实上只要注意到一点：整个图是没有环的。那么无论决定了哪些边的方向，都存在一个没有入度的点。我们从这个点开始把所有未决定方向的边的方向全部决定即可。

如何找到这个点？用个队列就可以了嘛。

注意到 n 这个点的特殊性。如果你 WA 22 了，请注意这个点：

4 4
1 2
1 3
2 4
3 4

D

看完题后觉得大水啊，比 C 还水些。

这题不就是去年 WC 的《记忆中的水杉树》吗？由于线段都是平行与 x 轴的，更好处理了。

从左往右依次扫描，用 set 来维护当前扫描线上的线段。

注意到连边的特殊性。我们要求 i 能向 j 连边的话要求中间不能插个 k ，于是你可以各种乱搞处理之类的。我的做法是动态删边，用 unordered_set 来维护当前点的出边。每次加入一条线段，我们就删除一条边。

后面在 DAG 上乱 dp 一通就行了。

但这个题有个小 trick ：

oo 要设为 2e9

哭瞎了，我后来一调，发现我一个地方 b 写成 a 了，另外就是 oo 设小了……

E

坑啊坑

situation

先怒水 A 。发现 WA 了。仔细一检查发现特判的时候加错一个变量了。T_T

然后 XLk 向我求解这个题的特殊情况。

然后发现 B 不也是水题嘛， 1A 好开心。

然后 C 看了半天没看出来。先写个 SAP 试试？怒 TLE 。T_T

感觉再不做题就要跪出翔了，于是怒写 D 。用 set 一下子就写出来了，但是 WA 了。

等 XLk 虐完 C 回来告诉我做法。怒写怒过。

然后就没有然后了。跪的挺惨的。果然实力还是不行呢。

由于小号 rating 低导致还可以涨？ 这不科学 ！似乎 +123 好数字……

others

XLk 果断虐场的节奏啊，怒涨 244 。顺便还带了 gjq 一起练呢。

我就不吐槽 XLk 的小号是 woxihuanni 了。（这是准备对谁说的？）

目测 XLk 的第二个小号都要红了我这个号都红不了呢。

liouzhou_101 和 lydrainbowcat 同时写挂 C 啥情况……于是 liouzhou_101 rating 大跌……momo

zcwwzdjn 目测做了半个小时就睡觉去了？ pty 似乎也一样……怒跪大神

我就不吐槽秋锅奇怪的 sort 了。

最近被虐得好惨啊……谁来拯救我啊……（转身默默学数英去 T_T）

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 ，你可以直接：

1

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 人。