AFAIK

Valar Morghulis

第一次参加 CF 的出题,感觉蛮好的……

虽然我打了一圈酱油啊!啥都没做啊!

Solution

2A --- xiaodao

你还想要有多水?

2B --- roosephu

普通青年:枚举分母。

文艺青年:连分数展开。

二逼青年: Fraction(x,y).limit_denominator(n)

2C/1A --- xiaodao

普通青年:暴力半平面交

二逼青年:暴力推公式

文艺青年:跳掉不做

要我的话还是半平面交吧,虽然这样也要推一些公式 T_T

2D/1B --- roosephu

这个题是我从耀爷那里蒯来的,结果没想到成为最水的题了……

一个结论就是最大值/次大值对只有 O(n) 个,用单调队列处理出来就好了。

感谢大叔提供了几个好数据~

有谁看得出这题是我出的么……其实我还黑了人的,只不过黑得很不明显罢了,连某热衷于黑我的小朋友都没看出来。

2E/1C --- WJMZBMR

答案就是每个点的深度的倒数和。(根的深度为 1)

证明嘛,我还不会一个显然的证明,但是我找规律找出来是对的。

有一种理解是这样的:我们考虑每个点,这个点只有在选择某次其祖先的时候才可能被删,选中自己的可能性是 1/dep(i) ,也就是这个点对答案的贡献期望是 1/dep(i) ,又由于每个点对答案的贡献是独立的(这点怎么看?),所以直接加起来就好了。

1D --- fotile

来自 fanhq 的加强版。

对于一个序列,求 k-MSS ,我们可以用网络流来做:一条链,限制流量为 k ,跑最大费用最大流。

这不是比暴力还慢么!注意到每次增广的特殊性,一定是选择一个区间,取了其中的值,然后区间取反。线段树维护即可。当然由于维护的信息比较多。要支持取反于是要还要记录最小值,还要顺便记录答案,比较麻烦。

于是就 O(n k log n) 了……

这个题居然被水过去了,坑爹啊……算了算了还是那句话:暴力能水过去也是他的能耐嘛。

1E --- fotile

主席的加强版的弱化版。(一种蛋疼的忧桑?)

做过原题的话应该知道用折线来刻画 dp 值这方法。对原题来说令 f[i][j] 表示第 i 个数为 j 时的最小代价和,可以知道 f 是一条折线,且只包含 O(i) 条线段,于是我们维护 f[i] 所表示的折线,递推出 f[i+1] 的折线。事实上这个方法是可以推广的,不过在这个题上是用曲线来刻画。曲线不好表示是吧,于是考虑维护曲线的导数。

维护了导数,找最小值也好找了,直接求与 x 的交点即可,方程也可以维护了。由于 n 只有 6000,暴力维护即可。当然你要有能耐的话可以用平衡树维护,保证复杂度 O(n log n) ,不过略难写。

procedure

一开始是在 G+ 上,主席说要给 CF 出题赚外快,于是我就回了句 bg ,然后就被主席拉过来出题了。

YY 能力完全不够啊。幸亏最难的几个题主席都已搞好了,于是我和 xiaodao 专注水题三十年。小岛出的 2A & 1A ,我出的 2B & 1B

一开始出 2B 的想法是要给一道水题是吧,然后瞬间想到 Python.fractions.limit_denominator 。当然连分数展开是果断不可行的,于是暴力枚举分母即可。

1B 的来源是耀爷讲课时的某题,我就直接蒯了下来~Gerald 好像搞了个很复杂的方法的说,其实就是个水题嘛。

一开始 1B 想出最大值除以次大值,后来想把数据出强一点,于是写了个 cheater 发现全部骗过去了,后来才发现如果是除以的话,答案一定是相邻两个数的商……宇宙大水题啊……

出题是放在 Polygon 上。真心是个专业网站,自带版本控制,用起来非常方便。里面有 invocation 用来测试数据,gen 建议用命令行做初始化,可以用脚本来生成数据,validator 检验特严格,一个字符都不能多,checker 感觉很松的,package 可以下载这个题目的所有相关信息,题目支持部分 TeX 语法真是太好了。幸亏前一段时间用过 git ,对版本控制还是有点理解的,用起来不难。唯一需要吐槽的一点,就是你必须等网页缓冲完毕后再点击超链接,否则会直接回到首页,蛋碎的感觉……每次 commit 都会发一份邮件,所以这几天被轰炸了不少。

主席某天突然之间就住院了,一开始我也不知道是啥情况,但是似乎很严重的样子。于是他的题就被分了,我、xiaodao、Seter 一起搞。我写了 E 的 cpp 以及 java ,慢出翔了,后来还是用的 Seter 的 java 。不过我写的 D 的 java 倒是跑得蛮快的样子。时限要求为 java 的两倍还真是蛋疼。为了照顾 Java 我不得不优化常数,结果最后和 xiaodao 一商量决定把时限开为 5s ,于是就有人水过了 T_T 其实我觉得 n 开小 k 开大蛮好的嘛,CLJ 说限制 k 的和也是可以的,这样更好卡了。

在比赛的前几天,突然得到消息说 C 冲了,于是怒 YY 题目。刚好做了一个 Project Euler 的题,于是 YY 出一个题,但是被 CLJ 抢得先机用了他的题。没关系下次再用嘛。

于是这场比赛的 problem setter 真是多,xiaodao、我、CLJ、fotile、kissbuaa ,另外 Seter、7k+、pashka、Gerald 来验题,规模也算得上庞大了,于是有人怒吐一槽:

话说现在 WJMZBMR 与 Petr 正大战三百回合,有兴趣的同学可以去围观。

然后晚上本来不打算围观了的,因为没人做,但是跑回寝发现大叔在做,于是怒围观。Seter、xiaodao、CLJ 开了语音,我和 7k+ 俩人就只好打字了……好苦逼。

于是讨论组里面的人全部开了上帝视角,成了权限狗。期间由于 XLk 突然之间回话了所以和 XLk 聊了一下天,他好久不回我了 T_T

发现 div2 的题超水,3min 左右 400+ 人过了 2A ,太可怕了。然后继续有人过 2B 。我很想不通那些过了 2C 没过 2B 的人是啥心态……我更想不通居然没人用 limit_denominator 来做,我还想不同有人用 Fraction 构造分数的时候用了小数从而精度有 bug ,我最想不通一堆人说这题精度太紧了太紧了。明明 Gerald 说这题太水要把数据组数减小的……

居然有人 5min 内过了 1A ,真是太令人惊悚了。我还看到若干个纯代数流,太可怕了。由于 1A 题过难,导致 1B 被迅速秒,成为这次 CF div1 AC 人数最多的题。

wuzhengkai 和 watashi 俩人同时在 33min 过了 A ,死磕着 A 不放干啥嘛,A 明显是用来坑人的。(wzk 的人人头像越看越觉得萌 = =||)

比赛的时候一堆人问 excluding OR 是什么意思。我明明记得我原题写的是 XOR 啊,那个英文翻译改成了这个东西真是蛋疼……偏偏样例精心手构答案是 7 和 15 无论 or 还是 xor 都可以解释。不过明明题目是 XOR 样例解释是 XOR 你还有什么问题吗?

哇卡居然有人交了 E ?WA pretest 2 连样例都过不了囧爆了。讨论组里面没人认为有人可以 AK 。

然后在 1h5min 有人过了 E 的 pretest ?为了和谐 pretest 是直接上了极限数据的,人民群众喜闻乐见欢兴鼓舞拍手称好。然后 Seter 拿过去一测发现可以 A 。经仔细研究后发现这个算法是错的……于是 Seter 出数据开始卡发现稍微一卡就可以卡掉了……结果一场腥风血雨在 CLJ 和 Petr 展开……再一看这个人还只交了 E ?果 E 大神!他的 AB 是后来才写的,太强大了……

大叔 YY 了一个 1B 算法,于是交了一次发现是错的,然后再交一次,于是我求数据加入 tests ,然后又写了个 gen 来生成类似的数据,似乎卡掉了一些人的样子。

D 题居然有人写正解!UESTC_Nocturne 太强大了……不过这个题被 liouzhou_101 骗过去了还真就不甘心呢。但是时限放的太宽卡不掉真是蛋疼呢。

之后一堆人在吐槽说 div2 的题太难了太难了太难了,你想要我做什么表情?

这次 CF 成功把 tourist 拖下 3k ……只要拼了前三题的手速就不会太差,后两题基本上没人过的。

nonsense

好吧就是这样,感觉蛮好玩的呢。

骗钱向:以后有谁要出 CF 了我可以过来打酱油啊,专业酱油三十年。

终于没有 hole 这个 tag 了~

Solution

250 pts

做这个 250 不要 250 了……

枚举最大值在这个序列的位置,可以根据位置及 d 算出这个数是多少,然后取遍 max 即可。

500 pts

二分答案,没了。

1000 pts

感觉这个题好囧啊。

S 表示随便放一个马,除自己这个格子外,期望能够攻击到多少个格子;令 P 表示同时能被两个马攻击到的期望格子数。经过一定的推理后,我们可以发现如下公式:

ans = 2S + 2 - 2S/(n^2-1) - P

于是我们只要求出 SP 即可。求 S 的话可以考虑统计每个方向上可以放的马的数目, P 的话我们就枚举同时被攻击到的马的位置。

首先考虑 a == b 的情况。 S 倒是很好求, P 的话可以推出一个公式来的。

再考虑 a /= b 的情况, S 照样很好求, P 就不一定了。我 YY 了一个很奇葩的方法。首先找到边界上的若干个分界点: {0, a, b, n - b, n - a, n} 。这若干个点把大矩形分成了 25 个小矩形。矩形内部的 P 是一定的,随便找一个点(例如找中点)即可判断出某矩形内的点的 P 。然后再用组合数乱搞一下即可。

situation

怒刷小号~从此我也是有 TC 小号的人了~

一进 room 一看,cherudim9 是 room 内 rating 最高的,我是最低的,高下立判。

一打开 250 pts,插件自动帮我生成了……Java 模板?我勒个去果断自己手写 C++ 。

随便一想觉得这题蛮水的啊,写完后样例都没测(因为没插件不好测),直接在 Arena 里面测了。觉得没啥问题就交了。这题真心水啊怎么 room 里第二个交的才 230+ 呢?

果断重新配置插件。把默认语言改为 C++ 一切就好了。

然后开 500 pts,这不是一个绝世大水题吗……怒写然后过掉。

现在时间还多的很呢,于是开始 YY 1k pts 。一开始的时候根本就没想到还有 P 这种干扰,后来才想起来……

感觉样例很强的啊,于是感觉是可过的。

cha 人的时候看到 500 pts 有人没用 long long 来保存中间结果,就想着这是不是一个 cha 点。我看到有人程序和我的特别像,于是在 cha 之前用自己代码测了一遍,发现过了?继续 YY 发现就是过了。自己一想发现中间结果至多是 2k 怎么可能会爆 int ……

最后的 FST 是什么情况啊!发现是 a == b 时的特判写挂了 T_T

所以最后是 #60 。如果 1k pts 不 FST 的话前二十没压力的 T_T

others

这次做的人不多,很多人都做前两次去了。

cherudim9 本来还好的,可是被 500 pts 的那个不是 cha 点的 bug 搞错了于是 +0/-2 囧…… #174

秋锅 #72 。令人惊悚的是他现在 rating 还没我小号高 = =||

看到了 DL.uhT 分布式哈希堕落?其实是某盾啦 #93

lydrainbowcat 1k pts 的被 cha 于是 #107 。

至于大叔……哇过了两道诶,虽然速度比较慢但是没爆零了啊~#227 不过 rating 还没他的第一次高……

cjsyj 的 250 pts FST 了? 这不科学 ! #425

This_poet 居然 FST 了 500 pts ?#685 momo

nonsense

今晚 CF 欢迎各位参加~

刚刚对主题做了点小改动。原因蛮简单的,在 XFCE 下开启透明效果后,我发现原来的背景与桌面这张阿狸的图片混在一起蛮好看的,于是心血来潮加了个背景。各位觉得怎么样啊~不好看的话我还是改回来吧。

具体实现其实蛮简单的。首先找到你的壁纸,用 GIMP 打开,然后新建一个全黑的图层,然后 菜单 -> 颜色 -> 曲线, 通道设为 alpha ,然后把那根线段的端点往下拉,就是 x 不变 y 变小,开启预览的话就按照自己喜好调。然后 Ctrl-Shift-E 导出即可。似乎这种图上 jpgpng 小一些?

如果图片大了的话缩放一下即可,我直接用 XnView MP 来重采样了。

然后要改 Jekyll-Bootstrap 了。我用的主题是 hooligan ,于是在 /assets/themes/hooligan/css/style.css 这个文件内有一行

1
background: url(../images/bgs/body.png) repeat;

我要的效果是背景不随网页滚动而滚动,于是改成:

1
background: url(../images/bgs/bg.jpg) fixed;

刷新几次,收工。

当然还有不满意的一点,就是壁纸大小不能根据屏幕大小自动换。这个要实现的话应该是可行的,因为这几天鼓捣 bootstrap 发现可以提供响应式设计,多 YY 一下应该是可以 YY 出来的吧~

似乎坑越来越多了……得填填啊。

XLk 去北京学英语了。(而且问他又会黑我的 T_T)

Solution

250 pts

唔,似乎是水题的样子。

大概就是利用 K 找出每一条链,链上找出出现次数最多的字母,其余的字母全部变为这个字母即可。

500 pts

又是渣手速。

暴搜是会 T 的~hahahaha 感觉只要答案大点就好了。(random 搜怎么破?)

我的方法是这样的:前面 4 位枚举原数,得到所有前四位的匹配情况。后 5 位就可以直接暴搜了。这相当于一个双向搜索,先从某一半开始搜,把所有可能的解全部塞到一个 set 里,从另一半检验的时候就直接在 set 里找了。

用 set 的话可能常数比较大,用个 trie 效果会更好些。不过这无关紧要了,不会 T 的。

话说感觉 TC 的 500 pts 很喜欢出这种暴力题啊。

1000 pts

坑。

situation

这次 TC 居然是晚上八点。话说 TC 没小号真是让人感到可怕……(xiaodao:rating 是用来跌的!)

于是机房里都在做 TC 。

上次 TC 给我发了个啥邮件,说啥 warning of unused code ... 于是这次交之前把模板神马的全删了……

250 这不是水题吗……手速硬伤。只有 237 分了。 T_T

500 想着感觉暴搜很容易过的?但是复杂度不靠谱啊……没敢写,继续 YY ……

突然之间 YY 出来了?写啊写……代码能力越来越差了,写了好久才调出来。只有 270 分了。

看了一下 1000 pts 的题,感觉很厉害的样子,没怎么动心思去想……

然后啥都没做了, Challenge 对我来说一直是打酱油的。

other

大叔又一次没爆零!普大喜奔~

tourist 怒 cha 掉 Petr 的 1000 pts 成功 #1!

我会说 Petr 只靠前两题还有 #4 ?

WJMZBMR #10 。第二题 350+ 太快了啊……

我居然看到了 Gerald ? #16

某 id 为 ainu7 的神犇只过了第一题,第二题 FST 了。然后他居然连 cha 了 6 个人 #17 !跪。

然后我就是中规中矩的 #22 ……

还有 Mike Mirzayanov 。CF 的都来了?

edly 说跪了,然后 #35 = =|| 然后怒黑之。

一堆人 FST 了 500 pts 。zhouerjin/xiaodao/NaHS/ChnLich/cherudim9/ryz/wuzhengkai ……momo

有位小朋友在做 div2 ……只交了两道于是 FST * 2 momo

另外 orz huzecong div2 虐场。

nonsense

CF-172 求围观啊~求各位大神虐啊~

前几天某人(特指)进入国家队了,然后 renren 上转了条状态(miffy 的),然后被一群人围观,然后四处被黑 T_T

有必要么!

嘛,wyl8899 问我是不是刷小号……

我才不刷小号呢,我刷的是小小号。

Solution

A

惯例水题。直接用并查集搞搞就可以了。

注意没有一个人会一门语言的情况。我因为这里 WA 了一次。

B

构造。

rng_58 的构造方法:对于 m=3 的情况手算,可以证明若 n>4 则无解。于是这里手算很简单的。

然后考虑两条抛物线: y = x^2 + U-y = x^2 + U ,其中 U 是一个很大的数。如果我们在抛物线上选点,由于抛物线的特殊性质(凹还是凸分不清啊 T_T),可以得到如果两个抛物线上都有点被选,那么这样构出的凸包的大小最多是 4 ,所以如果要选择尽量多的点的话,应该是选择某一条抛物线上的所有点。我们令一条抛物线上点的个数为 m 即可。

C

感觉还蛮简单的。

容易知道每行每列都是独立的,我们可以把这看成是若干个不相关的组合游戏。对于每一行/列,我们只关心没有被覆盖的线段的条数。这个可以用排序+点事件维护,也可以直接用 set 暴力维护。

然后把所有的数 xor 起来就是 SG 了。注意一种特殊情况就是初始时没有出现过的行/列。很显然,我们只关心奇偶。

如何输出方案?一行一列枚举下去,如果通过改变这一行/列可以把 SG 变为 0 则找到一组解。

代码量比较大吧。

D

没看懂题目的说……

E

稍稍一想就发现这是水题。

每个点的出点向所有可能的父亲的入点连边,容量 1 费用为距离。源向每个点的出点连边,容量 1 费用 0 。每个点的入点向汇连边,容量 2 费用 0 。跑一遍费用流,如果最大流是 n - 1 那么有解否则无解。如果有解则最小边权和就是最小费用。

大家都蒯模板啊我还老老实实自己打啊。

situation

本来以为秋锅不做的,结果居然做了。

看完 A 觉得这不是水题吗?于是怒敲代码,写着写着觉得有 bug 于是怒换一种写法。submit 后怒 WA#4 。瞬间想到某特例,加上特判后过 pretest 。

然后 B 。按照惯例,B 应该是水题吧。于是我被惊悚到了,完全不会做啊。YY 了好久想到了用抛物线但就是没想到用两条抛物线。一开始看错题了,以为是要构造一个大小为 n 的点集使得凸包大小恰好是 m 。交了后发现过不了样例才发现看错题了 T_T

瞟了一眼 Dashboard 发现有几个 E 已经出来了,看了一眼 E 觉得不会做。然后看 C 的题目去。看完 C 的题目后发现我会做 E 了 = =|| 于是回去写 E 。1A 。

然后发现 C 不也是水题么。只是处理起来比较麻烦罢了。于是再次怒看错题。然后就没有然后了,1:50 的时候交了个 FST 程序过去。后来调的时候才发现又看错题了 T_T

一看 D 的题目这么长我就直接撤了。目测等我理解完题目 CF 都结束了。

最后 #41 由于是小小号然后还是可以涨的。快追上小号的说~

others

XLk 你真的 AFK 了吗……考完后没人和我聊天了 T_T

scottai1 怒过 ACE 。E 手速还很快的说,于是有 #8 。于是 rating 又超过我了 T_T

wuzhengkai #25 、xiaodao #32 都是 ABE 。我觉得 B 的这个构造很巧妙的说。

watashi 和我一样的,默默 C FST 了。

秋锅 AE #90 。看起来又黄了。

另外我就不吐槽 FredaShi、CatCat、liouzhou_101 三个人的分数都差不多,都是 AB ,提交的时间也差不多,代码也差不多,连 E FST 了都是 T 12 。

ztxz16、sths、edly01、vfleaking 都只过了 A ,而且和我一样,默默 wa 了一次 ……

最后还要吐槽这次 CF 的分数变来变去的,一刷新就发现题目的分数变了。

nonsense

感觉这次 CF 难度很大的说……

然后发现还有人 AK 。

于是感觉 CF#172 也会有好多人 AK 的说。

退役了神马的,写篇回忆录来纪念我的 OI 生涯吧。文采比较差文章比较长章法比较乱废话比较多神马的就不要介意啦。当然,拒绝黑人。

小学

没听说过 OI 。

初一

没听说过 OI 。

初二

没听说过 OI 。

初三

没听说过 OI 。

>>>>>>>>>>>> 我是完美的分割线啦啦啦 <<<<<<<<<<<<

轻轻松松写完 9 年 lol = =||

好吧重点是后面的几年。既然 5 个学期就分 5 部分吧。

高一上

我初中在一个偏远的小县城里,教育条件显然比不上长沙。一中在当地也算有点名气,每年可以考一两个清北吧。毕竟人家的生源没有长沙那边好。但我老爸想把我送到长沙这边来读书。 长沙四大名校 在我们看来是可望而不可及的。但是老爸要我去试试,结果没想到考上了。

当时老爸联系的是向总,是长郡的信息学总教练。于是考完后就理所当然被拉过去玩玩,大概是在 7 月初的时候吧。初中的时候没接触过 OI ,但是玩电脑倒是玩的蛮多的,加上老爸严厉打击游戏,所以习惯起来不是问题。记得当时我们总共有好几批,我因为来得早被分到了第一批去。这一批除我以外全是初中就开始学的,所以一开始的时候被虐的惨不忍睹。不过当时想的是反正玩玩,又没人认识我是啵 = =|| 。突然记起来当时坐在我旁边的是mt。他天天玩三国杀,我要凑过去围观一下他就会说“搞学习去”= =||

后来又去试了试长沙市一中,似乎也上了。当时我兴趣更大的是数学,这方面一中应该是强一些(现在看还真说不定呢),但是最后还是选择了在长郡搞 OI 。(然后踏上了这条不归路?)具体原因神马的都是历史的尘埃了。

一开始在暑假集训的时候写的都是容易的不能再容易的题……一开始的时候都是要写啥背包问题的吧,别人写个 dp 我居然不知道为啥是对的。我记得当时某一道搜索的练习题,我怎么搜都 TLE ,然后 YY 出了一个想法,写出来后发现可过?然后好开心好开心地告诉谢老师(我指导老师),然后谢老师告诉我:你写的这个东西叫做动态规划,你以后要学的。她还鼓励我继续研究 = =||

暑假的时候,学校搞了几次 NOIP 模拟,我跟着当时的高二学长一起做,当时坐在我旁边的是 xqz ,当时好崇拜的。还请了个老师讲组合数学,于是听了几堂课再也撑不下去了,默默去另一个机房编程去。(结果后来某盾说当时我虐爆全场,因为高二还没学微积分,前面几堂课只有我听懂了 = =||)

军训之前,谢老师说:趁着军训你看看网络流的标号法吧。于是军训的时候无聊看看书,居然看懂了= =|| 军训过后就正式开学了。

开学过后的第一件大事就是准备 NOIP 。谢老师对第一批的说:你们这一批都有拿省一的实力,所以要努力 balabala 之类的。当时我也没太在意,因为知道大部分人都是在高二拿的。由于刚进高中的时候学科还不错,老李(班主任)也就批了我的停课。

当时实在不喜欢 Pascal 的 begin/end ,于是自己动手丰衣足食改 C 。后来才知道,我是学校第一个在高一就转了 C 的人 = =||

准备 NOIP 2010 的日子是我高中最怀念的日子。天天被虐,然后慢慢啃题解,争取每天都把题目做完。时不时地出现了啥集训队题目也不一定的说。实在写不完就算了。每天的生活忙碌而充实。记得当时有个题:求 n! 的末位非 0 数字,全场只有我一个人做出来了,然后还上去讲了讲,所以给小朋友出题时我总喜欢用这个题。另外 xqz 出题的时候出了道最短路的,和某人的集训队答辩题是同一个模型,我当时 YY 了很久,YY 出一个很奇葩的算法居然得了 70 分。后面再来看这程序,似乎我连最短路都不会写的说,用的还是类似于 bellman-ford 的东西…… mt 出了一道题,大概就是单调队列优化,后来 astar 就考了一道一模一样的题。每天看着还剩哪些题没做,争取多做一道。

然后就是 NOIP 2010 了。我也没啥心理压力,做不出就做不出嘛,反正高二有机会呢。第一题水题模拟无压力。第二题初看居然不会做,第三题由于有学长天天念叨二分答案所以 YY 出来了。不过后来前三题都过了。至于第四题(引水入城),我没啥好思路,于是准备拿个部分分走人,然后写着写着 YY 了一个结论,顺手就写了。正解的结论是上面能覆盖下面连续的一段,我的结论是能覆盖下面的一定是上面的连续一段,于是用差分约束系统 YY 了一下。由于对差分约束系统理解不彻底,于是边的方向、边权、初始值搞了好久,大概就是找出所有可能的匹配,然后随便找个没死循环、可以出正确结果的那个构图方法。

出来后向总问我可以打多少分,我说大概 300 吧,向总说 300 省一可能有点困难。我也没往心里去,大不了明年嘛。

回到学校休息了一下,谢老师给我打电话过来告诉我 390 ……我自己都不敢相信……因为我一直不敢相信我那个结论,觉得是数据水得了 90 分。后来告诉高二的学长某盾,他 YY 了好久也没 YY 出反例。然后就不了了之了。倒是高二的一堆人压力大得很,很多人都集中在分数线附近,包括后来进了集训队的 syj 学长。

大概这次 NOIP 之后我就开始放心地搞 OI 了。反正省一已经到手,实在不行回去高考也有几把刷子。NOIP 结束的第二天恰逢月考,于是很悲剧地被拉过去当垫被= =||

鉴于初期发展的很不错,准备 wc2011 顺利翘掉期末考试。我发现我每次外出考试总是考得奇差。wc2011 只有 30 分= =||这也是个打击吧。不过我在想……NOIP 之后我到底干了些啥?我的记忆中只记得两个完全不懂的词:网络单纯形/原始对偶。现在想起来真的是浪费时间啊。这时间要是拿来刷题该多好啊。

高一下

高一下期记忆就更少了。一开始的时候是在班上上课,突然之间谢老师找到我说省选快来了你不要准备一下吗我说我最近在准备啊谢老师说我觉得你现在准备的不够充分高二的早就停课了 balabala 的于是我又停课了 = =||

当时高二学长在做模拟题,于是我又跟着过去凑个热闹结果天天被虐,当然有时候小小爆发一下也不一定嘛……正好当时也要准备 APIO 于是就一起训练了。APIO 一去发现被虐残了,只拿了块银牌。据说这次 APIO 比 CTSC 还难。考试的时候坐我旁边的是衡八的 lyx ,我就是这个时候认识他的。当时第二题写的是 60 分算法结果只拿了 10 分。回校后怒调发现一个变量打错了……第一题在最后十分钟又猜了个结论想拿来骗骗分结果没写完,后面发现这就是正解啊……雅礼的似乎也挂了,倒是衡八的两个都是金牌确实可怕。不过当时还不太认识外校的人。

灰溜溜回来继续搞省选。心态依旧,今年进不了我还有明年嘛。

后来去长沙理工大学的时候联系了我爸一学生,于是每次去的时候都蹭了一点零食 lol 。

考完 day1 觉得还好。第一题随手 YY 了个矩阵乘法,写完之后觉得应该大概也许可能约莫十有八九是对的……吧……但是不放心觉得还是写个拍吧。结果拍出错来了= =||。然后其余的题全部暴力。于是 day1 150 分长郡内部排第二。我就不吐槽 t4 是江苏省选原题了。

考完 day2 后表示彻底享受了暴力的愉悦。4 个暴力依次展开。最让我无语的是 day2t1 ,数据你是纯手构让骗分 A 的吧,若干人输个最^10007 没技术含量的下界居然过了。只写了暴力的表示伤不起啊。不过算了,明年还有机会的说。谢老师说可能会改数据,因为这数据水的不科学。还有我 day2t4 的暴力莫名其妙挂了。经检验我的暴力应该是没错的。最后是俩题的数据都改了,于是前面一堆人掉下来,我加了分上去。似乎 220 的有好几个,最后是拼 NOIP 。NOIP 的人品还是少有的爆发了一次,没几个人拼得过我 lol 于是作为省队最后一名进去了。当时的雅礼好可怕,前 6 名被雅礼和南雅包了,xpd 因为学校名额限制被卡了。谢老师是在中午通知我的,我正在睡午觉,赶紧到厕所去接电话。真的很开心~

省选后又回去上课了。然后谢老师说全国赛快来了这是一个很难得的机会你要好好好好珍惜要充分地准备来应对 balabala 于是我又停课了。然后发现省选翘期中 NOI 翘期末真完美 lol 。

接下来是清华夏令营。省队的都去了玩了一下,我也继续跟着高二学长凑热闹。第二题是一个经典的网络流模型,但由于当时水平问题真就不知道做,写了个高斯消元还写挂了。第三题是恶心计算几何题,只想写最简单的情况,出来后才发现最简单的 10 分都没搞到。倒是第一题莫名其妙多了 10 分,调了后发现……我 for 多加了个 break 于是可以多 10 分 lol 。雅礼一堆大神都在这里签了,clj 也签了,我就纯酱油了一次,搞了个啥前 60 的。

然后还有个蛋疼的省队集训。于是谢老师要我出长郡的题= =|| 于是蒯了三道自己觉得还不错的水题结果有几人 AK 好没面子。我居然在湖南省队集训看到了 applepi ?计算几何帝啊。某个题只有俩人有分: dyf AC 以及 lrl 靠着 8K 的特判拿了 70 分,其余全部爆零。结果那天下午准备 dyf 讲做法结果发现他居然没来……另外雅礼汪老师搞了一套极其恶心的学科题:第一题和阶乘有关,第二题要求 B i x/e^x = A i cos(ix) - A sin(ix) 的实数解,不知道 e^{ix} = sin(x) + i cos(x) 的话还真就不好办,当时我还教了 zpl 如何证明这个式子 = =||。第三题是一个物理题,以前在物理组闲逛的时候拿起一半书随手一翻看到了基尔霍夫两大定理然后就可做了。

蛋疼的省队集训后就是全国赛了。不得不吐槽住宿条件。day1 的时候感觉还不错。第二题 YY 了一个奇葩的调整居然过了。可惜了第三题没写暴力, 60 分啊亲。day2 居然碰上了 NOIP 级大水题,T2 不会做,T3 我就不吐槽是原题了,然后……更让我惊讶的是搜索居然有 60 分……我又没写。于是银牌垫底,自然没进集训队,大概随便写个暴力就可以了吧。THU 的那个啥前 60 的自然报废了。 PKU 嘛,不太感兴趣于是就直接开溜了。这次 NOI 长郡还是很颓。耀爷 xqz 去了上交,某盾 THU ,syj 去了 PKU 。

NOI 告一段落,也标记着高一的正式结束,当然也标记着————假期的开始~有 5 天的假期哦亲~于是高一的寒暑假加起来恰好 10 天……

高二上

高二上期算得上是比较轻松的一个学期吧。

刚开学的时候有个湖南 ACM 比赛,于是谢老师让我在学校里挑人组一个队,看能打到什么水平。于是我就挑了个翻译官加一个水平相对较强的。由于一开始的时候误操作,导致开场的 30min 没有提交,罚时很惨烈的。翻译官拿着字典努力地查单词,然后发现翻译出了一个神题 = =|| 我后来又看了下题目发现这是个水题囧。这次 ACM 最坑的是一个最短路的题。看完题目后觉得这不是个水题么,最短路乱搞一下就可以过了啊。于是速写 SPFA ,怒 TLE 无压力。发现这个图是个网格图的说,怒写 DijkHeap ,怒 TLE 无压力。于是感觉这个题不对啊一定是打开方式有问题,于是搁一边把其余的水题做了。最后还有感觉某 dp 题和这个题比较可做,决定先把这个题搞掉再想那个。于是开始二分错误,甚至到了只读入的程度,怒 TLE 无压力。于是请求管理员验证数据,得到消息没问题……然后最后就卡在这个题上了。同校的另一支队伍也是二分错误在哪里,最后提交了 38 次,排在同题数的最后一名。最后的错误是啥呢?明明数据范围中写的是 100 ,同校的把范围改成 200 就过了。这不坑爹么~然后顺祝身份证和钱包一起消失在湖南农业大学的尘埃之中。

然后又迎来群众喜闻乐见的 NOIP 。话说有个同学去年和我一起拿了省一,然后……出于未知原因转到化学组去虐场了。这次 NOIP 正式给同学出了套题,然后被吐槽坑爹无限 = =|| 平均分也有 150+ 好不好?我们出题要讲究平均分是啵。如何提高平均分?要么把题目出水一点,要么就……我们有平均分帮手!把 std 复制若干遍就会形成若干个平均分帮手的亲~对应的也就有平均分杀手,把一个空文件夹复制若干遍即可。于是每天都上演着帮手与杀手的斗争。而且空文件夹的名字还要有技巧,你可以 YY 若干个看起来很正常的名字叫出题人没法区分 lol 。当然我的题是第一个考的,该机制尚未成熟所以躲过了其伤害 lol

考 NOIP 的时候我还是没压力,原因你懂的。Day1t3 mayan 准备写个 hash 判重目测可以快很多的,但是 hash 的时候写挂了,忘记把某个量 hash 进去了,结果剪枝错误导致只有 60 分。Day2t3 觉得是贪心啊,于是 YY 了好久的贪心感觉也是对的,于是……不好拍啊亲~于是这个题就只有 10 分了 T_T 这次 NOIP 学校的高分不多,400 分的分数线,最高分就是高三的 cy 490 ,然后就是我 470 了。于是还被批了一顿的说。

陆续的很多同学走了。有人拿了省一就撤了,有人没拿省一也准备撤。经过一定的选拔,最后还剩下 12 个人。陆陆续续又走了两个。NOIP 时热闹非凡的机房冷清下来。然后被拉着考了次期中考试。这大慨是我高中以来唯一一次期中/期末吧。

然后又是一次 WC 。然后和某盾、基哥分在一个房间很和谐的。(某盾你改我签名我还记着呢)我想起为了让某盾起床,我决定把我的手机(也就是闹钟)放在他那边。第二天早上,我被吵醒了,某盾表示毫无压力。另一件事就是,王教授在讲 CEOI 某 KMP 的题的时候,某盾上去讲,说这个题他是用平衡树维护 hash 来做的,然后突然之间扯到我,说我们学校的小朋友会一种线性的方法 balabala 的,然后我就光荣上场了 = =|| 。当然,王教授讲课一如既往的催眠。吴翼带了一些 IIIS 的糖,于是怒回答问题拿糖去。

WC 考试的时候,感觉题目完全不会做,所学的知识完全派不上用场。第一题 mst 拿了最暴力 30 分,第二题 memory 写的是 50 分算法,但很奇怪的写挂了,似乎某个地方想偷点懒,结果偷鸡不成反蚀把米暴力写挂了。最后一题又是个恶心的游戏题,实在是坑爹啊!有人写了个 GUI ,整个考试都在玩这个游戏,于是他神奇地拿了 80+pts 太可怕了。我随便输了个可行解拿了 6 分,最后总分就 66 分混了个二等奖。

高二下

高二下期就是真正的竞赛时期了。

这个学期除了为了应付水考而回去上了半个月的课外,其余时间全呆在机房。那也算得上是一次难忘的经历,我觉得紧张程度不输于高三。每天脑袋里想的都是做题。到外面吃饭等饭时在想题,睡觉前也要想题。整个人就像泡在题海中一样。这直接导致后来睡觉之前不想题就睡不着了 = =||

首先是准备 CTSC 。于是那一段时间的模拟题都属于比较恶心的状态。CTSC 我倒是考得蛮好的,具体原因大概是 day1t2 那个啥电阻的题写了 60 分算法,day2t1 由于在之前研究过后缀自动机,所以在调了 3h 程序以及调了 1h 暴力后终于 A 了,其余的题把暴力写完就有金牌了。这么说来有一件很囧的事,day1t3 是一个提交答案题,每个题输出 0 就可以得到 1 分,我有两个点打错文件名了导致少了 2 分。后来想着两分也决定不了什么是吧。然后……然后……xhr 225 分,我 226 分,xpd 227 分,gsh 228 分。整个人都木了。不过非集训队第四也是个不错的成绩了。另外不得不提某盾,最后那句“在最后一次 OI 考试中帅气的做出一道很难的计算几何题”真的让人很感动,不过对应的也使得向总有点失落。某盾你的小秘密还藏着呢。

接下来就是湖南 OIer 万众瞩目的省选了。省选前我的状态不太好,于是老李还特意找了我谈话,大概就是高原反应 balabala 的。然后大大夸了我一番,说啥你的竞赛水平一流进省队没问题的,啥实在没进省队我们还有保送生考试的,啥没进省队保送生考试那天生病了没去我们还有自主招生的,啥自招没过我们还有高考还有 20 分加分还有很多充足时间你可以赶上的。其实我没啥担心的说,我就觉得,去年都进了,今年进省队应该没啥问题的,争取好好考进 A 队的说。

湖南省选向来以坑爹著称,上次 day2t1 真是让人难忘啊,不知道这次会玩出啥花样。day1 考完的时候自我感觉很不错的,因为我主攻前两题,第一题 A 掉应该是没问题的,第二题 YY 了一个结论,最后数位 dp 不会写是神马情况?结果发现惨跪啊,后两题比前两题好拿分的多。第三题就是一个简单的排列组合题,把小学的我拉过来绝对推出公式没问题。可是这次就写了个暴力 dp 10 分哭了,最后一题写都没写。第二题全场最高分就 40 分,但后来观察数据发现不写数位 dp 写搜索都可过啊亲~第一题数据超水直接暴力可以拿 90 分啊亲~所以 day1 就 150 ,排名已经是十几名去了,先别说 A 队先进了 B 队再说。

于是 day2 拿到题目。完了第一题不会做,完了第二题不会做。再一看,第三题不是 lrj 讲过的裸启发式合并平衡树吗?1h 怒敲。第四题我记得在 Matrix67 的 blog 上看过的,某状压 dp ,于是 YY 了一下再对拍了一下没问题就撤了。可是前俩题真心不会做啊。于是第二题把式子化一化之类的发现可以动态维护凸包 = =|| 这货太难写肯定写不出来于是我就暴力维护凸包吧,发现再好写不过了 40 分到手。第一题就写个扫描线算了吧,算算期望似乎有 80 分呢亲。感觉 day2 平均分绝对没有 330 的说于是进队应该没问题。最后发现 day2t1 写挂了,80 分不见了哭。其余的分倒是拿到了。最后两天总分 390 感觉有点点悬啊。

最后成绩排下来居然可以排到第四?一中 jtc 和我同分,A 队必须有个女生导致男生只有 4 个名额,于是又 PK NOIP 。完了我 NOIP 只有 470 啊,结果发现 jtc 比我少 10 分 lol 省队分数线恰好 300 ,结果 300 的有 3 个,只有 2 个名额了,于是天聪凭着 NOIP 10 分的优势抢到一个名额。然后我在想————现在看起来我们的 NOIP 似乎考得不错? lol

然后又有人离开了。这次走的是本性,算得上是我认识的所有 OIer 里面和我关系最好的一个了。他离分数线差 10 分。上次 NOIP 离分数线差 15 分。也算得上一个悲剧男了。秋锅和整容都挂了。我看到他们在长沙理工大学的路上走着,走着,说不出的眼神。

然后又有个蛋疼的清华夏令营。省队的四个人一起去打打酱油。轩犇拿出去年的笔记本,发现讲的内容一模一样,然后有人爆料连学长的演讲稿都几年没变了。算了算了这不是重点。首先我习惯不了键盘, | 键的位置习惯不了,而且我写程序需要键盘的空格一定要灵,没空格会死星人一个,另外编程环境也是一个很囧的问题——windows 下有 xmodmap 吗?。不过再怎么说也改变不了跪的本质,第一题大水题我写了 2h 还调了好久的暴力。第二题想写个按时间分治的算法结果没写出来怒跪,第三题根本就没想。后来发现第三题不就是一个裸模型吗,考场上智商捉鸡啊。最后居然还进了面试?感动的要哭了。面试官问我:“你觉得你和 lzn 谁更厉害些?”我:“……”问:“从古至今你最欣赏哪位科学家?”我想起了 Donald.E.Knuth 但是忘了他的中文名是高纳德还是高德纳了,于是随便 YY 了一个,然后我看到面试官笑了一下。然后他还要我介绍一下 Knuth ,装逼失败……凭记忆随便 YY 了几件事。然后他还问我 TeX 怎么读,我还真就不知道 = =||

然后莫名其妙就直签了。我怎么看都觉得我这成绩过不了的啊。

在这里见识到了许多神犇。见到了高高帅帅的 XLk (我只敢远眺之,他怎么可能认识我),见到了一个抵俩的 kAc ,以及 cp 。当时没几个人认识我的吧。等待面试的时候认识了 xhr 。也还算得上拓宽了眼界吧。

然后又是省队集训。pty 天天惨无人道地虐场,人民群众表示强烈不满。我又是送了一套水题的说。xpd 和 xcr 似乎都是不想写程序的,基本上没交题。不过在这里认识了 fotile 主席还真是让人感到惊喜啊。省队集训的时候雅礼的陈老师把 HN 的几个人凑起来做团抗,全明星阵容:清华夏令营直签的 4 位加上 zpl/ayq ,算得上是顶尖配置了。但是最后团抗效果却不咋地,诶……

最后是全国 OIer 最大的欢庆:NOI。省常中伙食蛮不错的说。我就不吐槽住女生宿舍了,不过除了这一点外无可挑剔。我对他们的生活老师印象极其深刻,非常热情,有什么问题都可以去找他们。省常中真心高富帅啊,居然每人送一个箱包,还有 Google 赞助的说。

说到欢庆,我就想到整容。他在我们出发前夕才得到确切消息,他不能参加全国赛了。但他的坚强真心让人感动。挫折,让人生更美丽,让生活更美好,让意志更坚强。出发的早上,他赶来送我们,给了我们每个人一个本子,里面有他画的一幅画。心里一股暖流流淌。

NOI 倒也还是考得可以。d1t2 真心不会拍,于是把手解方程和二分一起拍,d1t3 只看过树上的,二维平面上的不会做了,于是就三种情况分别处理,期望得分 80 吧。但是第二种情况写挂了,但第三种期望只有 20 的但居然有 40 ,所以这个题 60 分,然后 d1 260 也不错了。春宵 d1 280,他第三题交换了行列于是有 80 分。d2 就跪了。第二题大家都会的网络流我不会,第三题又是一个恶心的游戏题,还不给 demo 的,于是全部暴力只有 100+20+23=143 分。一开始吃饭的时候说 XLk 要虐场了,大家都会做第二题,于是感觉前途无望啊。后来发现 day1 实在是考得太好了,就 day2 这渣水平居然还可以拿金牌 = =|| 不敢想象。NOI 的结果呢,几家欢乐几家悲。

NOI 的时候正式认识了 XLk 、学军众犇。考完之后去杭州转了一下,参观了学军神校并巧妙把节操全部送了 qdc ,感谢 ryz 给我们提供的导游服务呢。

(好像今天码了 2h 的字。下次再填坑吧。)

高三上

高三算得上是比较轻松的了,起码有大学上了。

于是高二暑假的时候谢老师给我放了十多天的假,我和老爸四处旅游,倒也是玩了很多地方呢。

在贵州玩的时候闲着无聊,参加了 tyvj 上办的一些 NOIP 模拟赛,顺便还参加了 vijos 复活赛,还赚了件衣服回来呢。

回到学校后又开始搞培训了。首先是和学军一起集训了一下,快 IOI 了李超要集训的说。国家队出去之前要搞了个啥集训,于是 hwd 找谢老师要题,于是我和 cwx 就被狠狠地坑了一把 = =|| 。本来还想用 ryz 的一道题的,后来一看情况不对立刻换题,否则就囧了。

然后迎来人生第三次 NOIP 。这次就变成出题者了。当然我的题照样是第一个考。

NOIP 又去酱油了一次。d1 的题做的比较轻松,做完后大概还剩 1h 的样子,于是玩 Emacs 自带的贪吃蛇、五子棋、俄罗斯方块玩过去了。d2 就做的比较囧了,一看 d2t2 觉得是标记线段树无误,速写发现过不了常数被卡了……于是赶紧转二分 + 线性判定,发现还是会超,最后加了一个 ws 的常数优化后大概要跑 0.7s 左右差不多可过吧。虽然最后写出来了但是心情被弄得大糟。d2t3 YY 了一下觉得贪心往根上走应该是可以的,为了维护的需要又写了个倍增,最后发现沙茶了 dfs 一遍就可以了。还有这个题该怎么拍啊……于是我脑拍了几组数据觉得没错就算了吧 = =||

最后出来的时候觉得 d2t2 很可能会 T 一堆点 d2t3 很可能全 WA 。结果居然 AK 了……我都不知道当初是怎样的手气。

在 NOIP 的时候借口刷题逃了若干神级 NOIP 模拟题,然后就迎来了集训队作业,于是我和 cwx 开始刷集训队作业。速度嘛,似乎我要快一点的说,不过也差不多啦。话说集训队作业给我们很大的帮助就是,以后出题可以从作业里蒯好多呢。

然后就要到北京集训去了。这次给我的打击很大的说。 day1 考得还不错,原因是 day1 题目比较水,而且若干人看错题了。当时我是闲着无聊看了看 t3 的样例解释发现和我理解的不一样,重新看一遍题目发现我看错题了,于是速改,在考试结束前 10min 改出来了,zpl 说他看的好惊悚的。day2 就怒跪了。我坐在 jzp 旁边,看着 jzp 开始写 splay 维护凸包。他写的比我晚,代码比我长,但是写完的比我早……被虐爆了。最后我还是没调出来,就交了个暴力上去。后来发现最可做的 t1 理解错题了。day3 day4 相继跪掉,于是最后排名是在十几,压力非常大的呢。

回来的那几天心情特别不好的说。后来 zrx 说我那几天看起来好恐怖的,和以前的很不一样了。一种从未有过的悲伤。

后来就是一直在考试,顺便刷刷 TC/CF 之类的。然后就是 WC 了。

WC 嘛,就是 OI 生涯的重点。考试前一天晚上,心理防线被谢老师和向总攻破。哀兵必胜?sigh 。

一开始我想写的是 100 + 70 + 30 ,结果发现 100 写不完,于是准备写 50 + 70 + 30 。最后 50 写挂了,所谓的“禁区”这个点没有处理好。如果当时能够再测一下其余数据神马的,结局或许就不同了。不过现在怎么说都没用,每个人都有自己的一段黑历史。

Epilogue

回顾我的 OI 生涯,发现前面都是一帆风顺的。习惯了成功,才会有如此的挫折感。期望越大,失落越大。这一次的失败,对我也是另一种锻炼吧。

一段坎坷的人生也是一段经历。想起了昨天不敢用大号做 TCO 13 R1A 时, xiaodao 说的:rating 不就是用来跌的吗?习惯了 TC 的涨,跌跌又何妨呢。人生大起大落的刺激,又有几人能享受到?给别人看你表现的最完美的一面,却看着失败的一面哀伤。自己了解自己,却害怕别人了解自己,也活得累呢。

你抬头看着天
洒一身红太阳
也许心中不在感到受伤

送你希望  送你力量
愿你一路走好别彷徨
明天总会不一样
日子更久长

后会有期。

TCF 一起跌,再也没有生活的信心了。

Solution

A

排序后贪心即可:如果没选 a[i] / k ,那么就可以选 a[i] ,set 维护一下够了。

B

考场上我写的很奇怪的算法。YY 错了算法,我以为把所有的数变成和根一样就可以了 lol 。于是这个题变成了一个很简单的 dp 题,方程为 f[i] = \|v[i] - v[fa]\| + max(f[j])

于是开小数组 FST 了。

于是考后重交一次过了 lol 我该如何表达我心中的 ** ?我交的时候还是最短代码呢= =||

正确做法是分正负两种情况讨论即可。

C

感觉 C 和 D 的分数分配不合理啊。

YY 的一个结论:最后消失的洞要么是被某个锐角三角形围起来了,要么是被一个矩形围起来了。

考虑原图的所有三角形。首先钝角三角形不会对答案作出任何贡献(围成一个 hole ),锐角三角形会一定会作出贡献,直角三角形可能会做出贡献。

对于锐角三角形来说,肯定是用外心更新答案。对于直角三角形,我们找是否可以构出矩形,如果可以,用矩形的中心更新答案即可。

D

我会说我随手写个 sort 过了 pretest ?

正解就是拓扑图搞搞。把每一行 sort 一遍可以得到若干个元素的相对大小,于是构出一个拓扑图。然后随便求个拓扑序就可以了。无解对应着没有拓扑序。

E

看着这个图就让我想到 CodeJam 的图啊,于是我就没做了。

situation

A 水题秒掉。

B 居然不会做!于是 YY 了错误算法居然还可以错 pretest 。xwlj 数组开小 FST ……然后重交一次发现可过= =|| 最后写 solution 的时候发现这个算法是错的 lol

C 感觉半平面交乱搞一通。放一放吧。

D 第一想法是用平衡树维护拓扑序 = =|| 觉得略麻烦。灵光一闪觉得可以直接 sort 啊,怒 sort 过 pretest lol 。

看了 E 的图觉得毫无兴趣回去看 C 。

哇 C 感觉就是 Voronoi 图乱搞一下啊。不会 V 图于是半平面交吧。最后 O(n) 的半平面交懒得写于是写了 O(n^3) 的半平面交= =|| 然后似乎整个算法都是跪的。

System Test 之前我是 #3 ,System Test 之后是 #300+ ,人生大起大落真是太刺激了。再这么下去小号连 div1 都不保了啊。

others

XLk 你说你不想做了于是居然和 xhm 开黑这不欺骗我感情么!

Petr 作为唯一一个交了 E 的人还 FST 了。

liouzhou_101 过了 ABD ,D 手速快于是 #14 怒 +60 于是总 rating 虐我了。

lyd ABD #30 (感觉 ABD 大众分啊)

xiaodao ABD #32 (+1/-2 相当于啥都没做 = =||)

好吧 xhm 的两个号也都红了,发现自己真是废啊。

nonsense

最近准备和主席、xiaodao 一起初一场 CF (赚外快),发现我完全没有出题能力,专业酱油男 T_T

我就不说这场 TC 真跪了。rating -= 81 T_T 保持了好久涨的趋势我容易么我……

Solution

250

暴力 dfs 就可以了。

550

考虑任意一条原图中不存在的边。这条边的两个端点一定不可能都在团中,于是我们枚举哪个点不在。这样可以删除一个点。由于限制了团的大小至少是 2n/3 ,所以至多删 n/3 个点,也就是说至多枚举 2^16 次,可以接受。

1000

(坑)

situation

看了一眼 250 题目短真是太开心了。发现是水题真是太开心了,于是果断 dfs 暴力发现写挂了还调了一下 T_T

550 的想了好久没啥好想法,觉得暴力求每个团应该没问题,于是开始写暴力,然后发现不是求最大团的话某些剪枝不能用真是桑心。

然后就没然后了。一堆人暴力求团都跪了。

然后就是 cha 人。看到了这个代码:

int s = 1, r = 0;
while (s <= n) s *= 10, ++r;

觉得如果 n = 10^9 会不会死循环 lol ?于是很 happy 地 cha 别人发现自己跪了 T_T

最后 #250 ,果然是个 250 。如果不 cha 别人的话应该可以混到 #130 左右的。rating 也不会跌得这么惨了 T_T

挂了还被 XLk 黑好不开心。

others

CLJ 过了前俩题 #30 。事实证明只要过了前俩题我就妥妥的涨了 T_T 只可惜自己弱想不出来啊。

Egor 550 FST 1000 被 cha 好可怜。不过人家不会在意嘛。

xiaodao #115 第二题被 cha 。

然后就没人做了。

XLk 注册了然后突然发现找不到自己名字了?很悲剧地发现被 deactivate 了。好像是和 xiaodao 他们开黑被抓了 = =||

nonsense

最后那个好不和谐的跌 T_T

Sorry, the picture can't be loaded

老早以前老师就说要做个内部 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 我会捕获两遍。是本来就要调用两遍还是我写挂了啊……

0%