0%

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

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 我会捕获两遍。是本来就要调用两遍还是我写挂了啊……

玩脱了,目测要是用大号或者小号的话都会跌吧,幸亏用小小号 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 。截图如下,我多么希望网速能够慢一点啊。

Sorry, the picture can't be loaded

others

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

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

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

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

然后没谁参加了……

nonsense

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