kzoacn's Blog

即将退役,再不写点东西就没时间了

 

  有关OI的资料:http://pan.baidu.com/s/1dD2fqXr,还有一些在右边的GitHub里

 

  我最早接触OI是在初中的最后一年(有人叫初四有人叫初三,反正……我们那里叫九年级……),其实前两年信息老师早招过学生,可是我在五班,而老师只招了七班和八班的学生.实话说,我上初中时成绩相当不错,在一个三流城市不小的初中学校(一个年级8个班,每个班50-60人)年级能排到前几,而且也比较聪明,不怎么用功,平时非常闲,最大的爱好就是看数学书、玩电脑和打dota,自然而然地就想学习编程,自己买过《C语言从入门到精通》,然后下了个Turbo C自学,可是TC的尖括号"<",和括号"("显示出来是一样的……于是就没有写出过程序来,vc++也试过,但莫名用不了.

  有一天我妈跟我说她们聊天的时候(我妈是本校的老师),听说可以学编程,就让我去学,当时也想去,但也没什么时间,就放过了.八年级升九年级的暑假突然想起来有这事,就联系了一下老师在暑假里辅导一周.去了发现两个班的人就剩下bakser一个了……然后这一周就是学习了pascal基本语法(因为老师只会p),其他的时间就是在颓废,由于没有网而且系统还是win2000而且老师就教两个人也不管,我们颓仙剑,颓frontpage2000中的小车游戏,我还去学了一下Pascal的随机,写了一个和电脑玩蛇鹤虎龙拳的小游戏,后来听说非常受学弟学妹的欢迎.一些琐事:我们当时看普及组的题,发现一个都不会写,然后看了看提高组的题,看到了"能量项链",当时就觉得……这东西真的能用计算机写吗?然后看了看标程,只看见几行for循环和数组搞来搞去,当时我、bakser以及教我们的老师都认为:这一定是一种奇怪的冒泡排序！

  暑假结束后就没怎么写过程序,当时一直在思考一个问题:"一个程序能否不用文件输出自身源码",这个问题真是我自己想的……然而以当时的智商一直没有想出来.

大概10月份老师告诉我们去初赛,我们就去了,bakser跟我说初赛他两年都没过,然而过了一段时间我们得到消息,初赛都过了.11月份复赛去潍坊昌邑,头一次不是因为生病向老师请假.依稀记得当时台上走过一个学生代表,他说的话全都不记得了,只记得——"我们是OIer""作为一个OIer""OIer"……我当时不懂OIer是什么意思……因此印象特别深刻……然后就是普及组的考试,记得当年的第一题是给定一个数n=pq,pq是两个质数,求较大的那个质数,当时一看愣了,从小到大枚举碰到的第一个是小的,然后用n除小的不就是大的吗?当时也不懂复杂度的概念,只觉得这样肯定比枚举大的那个要快,然后看第二题,寻宝,当时看来题面好长啊……硬着头皮写,当时不会p的debug(现在也不会),看着坐在我右边的比我矮两头的小学生啪啪啪地敲着键盘,free pascal的界面上一个大大的watch,还有个条条在乱蹦,感觉……受到了极大的打击……然后寻宝死活也写不出来,看看最后一题能输出-1就打了一个writeln(-1),(事后证明此题没有-1的点)……我现在还记得外面下着大雨,考完后冒着雨回了宿舍,心情糟糕,问了问bakser也没有考好,后来怎么回来的也记不太清了.一些琐事：当时宿舍里没电,在宿舍里找到了一个饮水机用的插座,连上了插排,过了一会儿……有个人问能不能再连一个插排,于是就连上了,过了一会人越来越多,20+个插排连过整个一楼的场景相当壮观,然后围观两个不会打dota的人打dota,sven出门买一个+3敏捷的红鞋子以为能加移动速度……我至今记忆尤新.当然很快所有人就都被宿管大爷赶走了= =

  NOIP2012跪烂似乎对于我的生活没什么影响,该怎么样还怎么样,直到山东NOIP分数线划定那天我妈告诉我,我拿了100分,刚好拿到了普及一等.bakser拿到了三等.不久后的某一天周一升国旗,在一个百年没有人参加过NOIP复赛的学校,我和bakser被公开在国旗下领到了NOIP证书,当时的感觉是……又可以拿来和妹子装逼了.

  很快寒假过去,准备中考,我考的学校是本地最好的高中,和其他同学不同,全校和我考相同的高中的人用一只手就能数过来,总之中考时情绪相当不好,最后的中考成绩比平均水平少了十来分,不过还是上去了,中考分在高中里能排个中游偏上的水平.

  暑期颓废不止,把笔记本装上了win8,其他的事情似乎就是打dota和去图书馆.接着接到了报竞赛的通知,顺理成章地选了信息学,参加了一次智商(脑筋急转弯)考试,然后就和bakser进了机房,暑假在机房学c语言,语言其实还是比较好学的,于是就觉得"哎呀呀怎么这么简单,不写了,搞点有意思的事情",做过的事情有:破坏教师端软件,破解bios密码,用工具干掉windows然后看系统崩溃系统还原,当时还在Ti3,iG比赛的时候上面在上课,我就在下面偷偷看(我是iG脑残粉).过了些天语法讲完了,开始讲排序、最短路、搜索、贪心、动态规划,排序我和bakser曾认认真真地背过一份快排,最短路只背过了floyd,第一次用搜索做出八皇后的时候一脸兴奋地跟老李说,老李一脸呵呵的表情,贪心还是很好懂的,动态规划完全搞不懂(为以后埋下了祸根),开始在校内oj上做题,做题速度不敢恭维.而此时机房人也越来越少,只剩下了15个左右的人,然后我们接到通知,说是去烟台参加夏令营,嘛……干嘛不去.去之前当时毕业的高三一届回来机房坐坐,讲了一些网络流什么的内容,什么都听不懂,最后我问了sunmeng94那个能输出自身源码的程序,他说:"代码最后都是被转成机器码的,你没法输出".当时颓mc,被vnb看见,vnb:你们也颓这个啊.

  然后就去夏令营了,不得不说烟台开发区高级中学的宿舍确实不错,一个宿舍里4个人,每个人有一个上面是床下面是学习桌的东西,自带卫生间,而且插座还有电！和我同房住着两位师兄,然后写成流水账这个夏令营是大概是这样的:

  上午考试,什么都不会,写完没交.

  某天中午dc来到我们宿舍做课件,看到了dc删hosts,看到dc在玩C+C,手机一查发现是18x,于是好奇地用u盘要了过来……dc还真给了……jbr师兄:你这样带坏小朋友真的好吗?dc走后我问师兄来的人是谁,方才得知dc大名.

  晚上回宿舍和学长们打dota,玩rpg.

  由于考试完全不会于是翘掉考试去听别的讲课,然而并没有什么卵用,姿势根本没有增长.

  下午听dc讲课,还是什么都不懂,只脸熟了一波师兄

  晚上和师兄颓废

  上午照旧

  中午回来发现无线鼠标丢了啊啊啊

  下午拜托dc在屏幕上打寻物启事

  上午照旧,只是没了无线鼠标

  中午一位叫做刘亦伦的的小朋友把无线鼠标给了我！感激不尽

  晚上洗澡+颓废

  ...

  然后夏令营就这么过去了...除了学习到了OI圈内常用语言外没有别的收获……

  暑假的最后一周待在机房里逃掉了军训

 

  高中生活正式开始

  

  我个人非常喜欢数学,而且数学成绩也非常好,从小学开始当了得有7年的数学课代表,在新的班级里就主动申请并当上了数学课代表,班主任是一个年轻数学老师,而且带过竞赛生,非常支持我搞竞赛.我巨爽啊！初中所有的班主任都是语文老师,而我非常不喜欢语文……

  开学一周,奠定了以后的生活基调,每周三下午第三节课开始到晚自习第二节课结束要去新校机房(高一在新校区,高二高三在老校区),每个不放假的周末坐车去老校机房,放假的周末周日去老校机房.

  很快就和同学们混熟了,逐渐适应了高中的生活习惯作息时间,可是学习方式却没有适应,而且暑假里什么都没有学,第一次月考,班里20+,从初中来看,20+是年级名次还差的很远,直接在班里给我来个……真真切切地感受到了高中生活的压力.此后的生活与普通高中生没有什么太大不同,除了竞赛,每周三的那点时间学的东西不多,每个周末去老校学习的效率也非常低,那个时候每天干的事情就是把老校那些win98的老爷机统统做成linux系统,当时搞过ubuntu,xubuntu,lubuntu,kubuntu,linux mint,cdlinux,vectorlinux,winlinux等等等,一句话说就是不干正经事,noip级的算法学的半斤八两,不过各种stl却越来越熟练

  我:快排不用自己手写

  鸟哥:啊?!

  我:c++里有

  鸟哥:可我是c

  我:c的stdlib里也有qsort不用自己写快排

  此时在讲台上监自习的老李坐不住了,气急败坏地说：快排是每个人都得会的,你不单单是学这个算法,你有的时候还要改编这个算法,如果有谁不会写快排,咱们就不让他待在机房里了！

  不懂stl的人,唉……后来,1.我不会写快排,2.鸟哥stl只会用sort,3.老李没有把我赶走.

  关于stl,我用map<string,int>当哈希表过掉了八数码,自己发现可以用vector<list<int> >来当做邻接表, 当时的心情非常激动啊,因为我不会邻接表和链式前向星,直到今天我仍然用vector存图.

  从九月开学到noip前,提高组所需要的算法与数据结构都懂得了一些,成功地独立过掉了能量项链,期间机房换了一波电脑,由于不知道bios密码,linux的疯狂颓废就此结束.

  noip前停课了一周,老李让我们学树状数组和st表,看了看不明白x&-x是什么意思于是树状数组弃疗了,又看了看st表好多好多>> <<根本看不懂,于是noip之前我的知识水平主要有:半吊子的(搜索,贪心,dp和简单知识)+比别人多一点的stl

  于是就去烟台考noip了,第一题看出来是快速幂,然后我的快速幂大体是这么写的:

 int power(int x,int k,int p){
if(k==0)return 1;
int ans=power(x,k/2,p)*power(x,k/2,p);
if(k&1)ans=ans*x%p;
return ans;
}

  然后你懂得,第二题感觉是逆序对但是当时不会把式子拆开证,于是弃疗写了个n^2的(我也不会nlogn的……),第三题没看题以为是网络流,于是怒写EK(我当时居然会EK),然后发现牛头不对马嘴,写了个搜索过了样例时间就到了.出来真想骂娘.第二天第一题以为是线段树,于是写了一个搜索,第二题会70分的dp,第三题的搜索把自己写哭了,然后时间到,noip2013 GG.

  回来继续正常向的高中生活,noip出分那天看到了自己的成绩是80+70+10+30+70+0=260,十分感动……只学了几个月的鸟哥高一第一365还超过高二好几个,怒踩四年一等的GTY大哥5分.没几天分数线出来,SD一等线是270……把事情给班主任汇报,班主任的苦笑至今仍非常清楚地在我脑海里.

  11月转眼就到了1月,高一的第一个学期已经度过,我的文化课成绩每次考试都在上升,而且在这里说实话,我和同班的一个女同学关系非常好,可以说……唔……可以说是到了暧昧的程度,照这个势头发展下去,到高中毕业成为人赢也不是不可能,而OI方面则惨淡无比,和她聊天的时候她还时常把我拿了二等作为嘲笑的把柄.

  接着放寒假,当时的高二大哥们都去了wc,我们上清北学堂的网络课,给我们讲课的有毕克,胡渊鸣和贾志鹏.现在回想一下他们讲的真的很好,可是当时没有听懂多少……

  没过几天放寒假,回老家,在3G网卡20kb/s的速度下,我在csdn开了一个blog,下定决心开始认真搞OI.给自己的目标定的是进省队.(从此以后的OI生活大都记了下来,终于不用努力想以前的事情了……)

  首先学习的是单调队列,树状数组和st表这几个简单点的数据结构,并且终于学会了nlogn逆序对.接着看了看往年SDOI的题,发现每年必有一道数论和一道网络流.于是花了好长时间搞懂了扩欧,接着学了BSGS,紧接着就开学了.

  一周只有两次能够上机敲代码感觉不够用啊,于是每天在宿舍里捧着算导看,还是涨了写姿势.期间学习了匈牙利dinic和spfa费用流,然后在一轮前一个多月我听说了要停课一个月,停课=>去老校一个月见不到妹子=>妹子想我给我打电话&&我每天想妹子睡不着=>在机房睡觉,结论:妹子会影响我搞OI.于是我把妹子甩了……在当时看来这是一个无比悲壮且明智的决定,现在真想剁了自己……一入OI深似海,从此妹子是路人.

  停课后还是主要在学数论和网络流,懂得了phi,见过了不少网络流建模.那个时候看题解,神犇的blog中给我印象非常深刻的人主要有云神、黄学长和jiry_2,noip题解看的就是云神的,当时以为黄学长比我高一届,尤其值得一提的是jiry_2,2014年三四月份jry blog的头像应该是桐人和亚丝娜(没记错的话zjoi后变成了筒隐月子),当时看某篇题解的时候handsomeJian指着头像说:"快去看快去看,非常好看,我看了3遍",在此之前我对于动漫的理解就只有哆啦A梦和柯南,于是看了SAO第一季.看完第一季觉得不够爽,于是去看了原版小说,同时期仰慕陈老师的IOI游记,还看了幽灵恋人,同时顺便还把fate系列,空境,魔禁,加速世界等一大波轻小说塞进了mp3里,这个mp3其实是我妈没收学生的,然而那个学生毕业了,也没有回来要,就给我了……2005年出厂的老古董,存储空间256M,屏幕分辨率160x128,实在是想不到功能齐全,除了听音乐看小说之外居然能看视频……

  这一时期的主要生活方式是:

  早上急急忙忙地起床,卡着点去食堂买个面包然后去机房

  上午以极低的效率做题……

  中午有时做题有时睡觉有时看看scp基金会,越来越不打dota了

  下午经常犯困,极低的效率做题……

  晚自习以极低的效率做题……

  晚上回宿舍熬夜看小说,睡觉时间一般在0:30-2:00之间

  一般来讲每天早中晚各做一题,用一个月的时间成功地在一轮前在bzoj上做了一百道水题.省选前最后的几天主要在研究线性规划和FFT(因为我天天看算导),当时的成果好像还算可以.还有就是认识了两位HN前辈Randolph87和z55250825

  于是一轮省选前我的知识水平主要有:noip提高组算法基本掌握+熟练的stl+入门级的群论+入门级的数论+做过很多题的网络流+背代码的(FFT+单纯形).

  跟你讲一个笑话,我不会线段树.

  然后就去一轮省选了.

  day1T1一看就知道是数论,本着"我学数论啦我要做我要做"的思想在这题上死磕了4h,其他两题的暴力过了样例就没管.出考场看分,发现自己爆0了.

  讲题,T1是数论没错,可我TM可没学过莫比乌斯反演啊!,T2是AC自动机,没学过,T3是LCT或链剖线段树,我又不会,于是爆零妥妥的.回到宾馆后真的很悲伤,看了秒5安抚自己的心情.

  day2就是冲着3道暴力去的,然后向量集那题给的暴力分是凸包暴力……我连答案在凸包上都不知道,于是最后的得分就是30+0+30,实在想不到这样就是SDrank12,果然弱省省选就是认真敲好暴力就能进的.

  讲题,T1是网络流,反正我没看出来……T2是扩展二进制分组,T3是矩阵树定理.反正都不会就是了.

  靠着暴力有惊无险地过了一轮,回去学了一周的文化课又回来了.

  生活方式和以前没有什么不同,学习的内容线段树、平衡树等数据结构类偏多,也学了其他的不少内容,当我慢吞吞做题的时候却发现jry屯题屯地飞起！吓得我赶紧调查了一遍,得知jry跟我同一届之后我想……我们以后还有活路吗?

  二轮前三天,stl依赖症发作,给bzoj扔了一道题,标程是map<set<int>,int>……算了还是不多说了吧……

  二轮前我的知识水平已经比较完备了,也在wikioi上把自己刷到了SD前3,一轮的磨练让我懂得了暴力的重要性.

  出发去二轮省选.唯一的印象是宾馆外面有一棵二叉树,就是这颗树从地面0.5m左右分成了两叉,人称二叉树.

  day1的题发下来……卧槽这是连暴力都不会写啊……于是全程玩T2的2048,玩出来30分,这样居然就是rank15,Orz提答31的davidwang.

  听讲题,这TM都是什么玩意,Google公司常用算法关我们天朝屁事.

  day2的题发下来……卧槽这又是连暴力都不会写啊……于是全程玩交互题,以为可以压位但实际上不可以,但是下发的checker没有检查这一点……day2只有2分……

  听讲题,这TM又是什么玩意,插头dpFFT,可持久化Splay?

  我正好遭遇了SD史上最坑的Round2,于是自认倒霉,滚粗了.滚回新校去学文化课.

  停课这么长时间,美好的高中生活不再,其中***就是那个妹子,NKM的意思是"Nobody Knows Me".生活的孤独,OI的失败,让我经常梦到自己犯罪,更不可思议的是还能感受到犯罪的快感,我有点理解那些被社会所压迫,从而成为恶魔的那些罪犯的感受了.

  一周后参加省队集训的讲课,近距离仰慕了翱犇,加了tsyao友链,成为了权限狗,得知了两位HN前辈退役.

  然后回去文化课.

  期末考试已经不能看了.

  暑假开始,学会了fhqTreap,参加了SD的夏令营,被kAc叔叔说上课不认真听讲,发帖仰慕KuribohG,noi同步赛混了个Cu,出了一道水题从而认识了hzwer,maoxiaohan1999,ndsf.又学会了好多好多东西,总而言之这个暑假过的非常充实.暑期结束时算导综合症发作把vEB树扔给了bzoj,然后就被线段树过掉了.从暑假开始逛b站以及补番,从一名小说党变成动漫党.

  开学,依旧是做题做题做题做题.做PA题的时候认识了Claris.然后觉得PA题好有趣啊就去看了看PA2013,结果不知被谁被莫名其妙地搬到了BZOJ上.我能yy出策爷的心理活动:我搬完了PA2014,过几天再搬PA2013!(看BZOJ)卧槽?哪个逗比抢了老子的活?翻译的还这么渣,哦,原来是你这个逗比啊!被学军爷鄙视hit*1

  博客写的久了,就会有人加我……从某个时间点开始,就有人加我好友,"我是OIer",嗯,你是OIer,不跟我说你的id……好,就叫OIer了,没几天又来一个人……"我是OIer",嗯?你是OIer,可是OIer已经有了……,那就OIer2吧,接着又来一个……"我是OIer"……好,OIer3,"我是OIer"……好,OIer4……我的好友列表里有一坨叫OIerX的……

  由于搬到了老校,里机房也近了,老李允许我们在文科课和体育音乐美术课以及晚自习过去,每天都能敲代码做题感觉良好.这段时间知识增长的特别多.在noip前屯了一波题,由于时间太紧拿了usaco的水题凑数,许久不来机房的金牌学长sth回来看到了,用一脸鄙视的眼光看着我:"你做usaco的题",sth学长特别反对刷水题,他认为这样没有意义,尤其反感usaco的题,被鄙视了之后我再也没有做过usaco的题,不管金组银组.uoj似乎是在这个时期附近开张的,我终于明白了"能输出自身源码的程序"的学名叫"Quine"

  接下来的noip2014记的挺全的就不说了.

  之后依旧是做题+学习新算法.12月的时候想想省选已经过去半年了,还有半年就要迎来新一轮的省选,如果去年这个时候有个告诉我你该学什么,一轮的那些不算难的题肯定不在话下.由于不希望学弟重蹈覆辙就写了一发,给出了主要的学习纲领,我说:"FFT是装B用的啊不要学",本意是SD弱省,正常出题人几乎不可能出FFT,所以不要学.鄙视FFT自然地就遭到了数学名校学军爷的鄙视.被学军爷鄙视hit*2

  然后挖了坑做wc神题,被虐的欲仙欲死.

  时间进入新的一年.学习新算法的脚步一直没有停止,元旦过后想学toptree了,苦于找不到资料去贴吧求助,由于用词不当被喷了个狗血淋头,想纠正然后手一抖不小心帖子没了.算了算了这事过去了,自己啃英文原版又不是不行.然而我发现jry一直在用"强省专利"造句……要是像"是xx的特技,是特技的xx"这样的还行,这种本来就招致争议的东西还是不要的好.然而没几天贴吧里就出现了一个叫bottom tree的东西……我是在第二节课课间的时候看到的,内容是模仿的,这是赤裸裸的嘲讽,被学军爷鄙视hit*3,我发了个求不D,然后去上课,第四节课的时候去机房,此时这个帖子已经被删了.

  没几天BZOJ来了个新题3881,最近刚复习了AC自动机于是就写了一发不太对的暴力,喜闻乐见地比标算快,想不到jry亲自登门打脸,被学军爷鄙视hit*4,而且说的有理有据,我也没法辩驳,被打掉的牙只好往肚子里咽,看着楼下众神撕逼.

  带着不爽的心情学会了toptree,并且接到了BC的round的通知.由于noip差了5分,只能黑户去wc了.BC的round开始时我正好在济南,简单记一下这场被搞砸的round

  第一题的确稍微需要点知识,但想不到通过率这么低,大概acmer对于取对数的题见的不多?我看到了一波又一波的高精度模板……中间的注释看的我都会写高精度了.而且会取对数的人也不会浮点数比较……实际上我犯了一个错误,mathlover赛中告诉我取ln后最接近的两个数相差2e-9,我的标程的eps=1e-9,但我其实没有意识到这点,使得eps=1e-2就可以通过此题……

  第二题是从TimeMachine那里要了一道题,的确比较水……

  第三题是做spoj Longest Permutation所产生的idea,不得不说如果做过这题那么肯定会做C,由于存在O(n)的方法,为了恐吓一下O(nlogn)的算法,把数据范围开到了10^6,万万没料到手抖把中文的数据范围少打了一个0,事后统一修正为10^5.

  第四题的确是我自己yy的,只是考前前一周才发现它是原题……这题的本意就是防AK,目测有2个能写出来就不错了.但想不到日本人无节操帖板子……

  然后就被jry带头在uoj群里大婊特婊,被学军爷鄙视hit*5,仔细想想好像没有带脏字?毕竟错在自己,也不好吭声.

  忍无可忍,无须再忍,我们下个id见

  random了一个6位字符串

  反正要退役了我在这里吐个槽:

  

  "我艹TMD学军爷们怎么这么喜欢婊人！"

  

  WC游记写的也很详细就不多说了

  寒假里照常刷题,寒假前有一个同学托我下舰娘的本子,给了我一个8Gu盘,我登上他说的那个网站,一看卧槽18个G……三天三夜下完……三天三夜分三次给他拷走……

  寒假的某天手贱点开看了一个

  然后在一个良辰吉日抢到了号,我正式成为一名光荣的邪教教徒.

  从wc回来到一轮前主要就是做题、互测、肝船.互测天天垫底搞得我非常伤心,感觉自己一轮就会退役,写下了伤感的话.然而一轮考的非常好……回来不久得知nilihan1999和hzf HNOI退役了,似乎和我比较熟的HN人都退役了= =我是HN杀手？

  人考好就会浪,CTSC前就没怎么做题,于是CTSC铁牌滚粗,APIO痛定思痛拿了块Au,回来没几天就是二轮,浪的太久了被一巴掌糊在沙滩上.

  其实我应该是退役的.

  GTY回来改题的时候发现最后一题的数据错了,如果这个数据修正,其结果是:GTY进A队,王元炜被挤出A队,我无法进入面试,liangjs进入面试.可是名单已经发布,SD的老师们也已经被我的花言巧语蒙住,我就这样昧这良心成了B类,liangjs交了2w成了D类.良心不安.

  紧接着省队集训,每天垫底

  接着PKUSC,闷声滚粗

  改hosts,禁颓废

  接下来校内互测,依旧垫底

  心情忧郁

  学了一个月

  省队二轮集训,稍微好了那么一点点

  马上就noi了

  

  也该退役了

 

  我会记住OI给我带来的快乐与忧愁,泪水与汗水

 

  祝大家NOI一帆风顺

 

  Good Bye