Skip to content

Accepted Melody

 

生教育课作业:对大学的感悟和期待。远子学姐和芥川neta自文学少女。文笔很水,请见谅。文中所有人事皆为虚构,切勿对号入座。

Accepted Melody

Accepted是在OIACM竞赛里某题答案正确的意思。

第一乐章:Prelude(前奏曲)

“我们之间的差距,不只是1分而已。我的天才是你不论用多少汗水都换不来的。”

Alexa用鄙视的眼光看着我,对败家之犬一般的我,抛下了这句话。

 

 Olympiad in Informatics(简称OI),属于高中五大学科竞赛之一。凡是在五大学科竞赛中获得一等奖的高中生,都有资格获得大学的保送资格。因为能绕过高考的独木桥,所以每年都会吸引众多有能力的高中生参加。OI竞赛分3级:省级赛,省队选拔赛,全国赛。

NOIP(省级赛)是面向来自全省的OIer(指参与OI竞赛的高中生),由全国统一出题。每个省根据各省参赛人数决定省内一等奖人数。凡是获得省内一等奖的高中生就会获得大学的保送资格。

省队选拔赛:顾名思义就是省队选拔赛,高中阶段获得省级一等奖的在校高中生都有资格参加省队选拔赛。由省内命题,每省根据成绩排名选出全省最好的OIer参加全国赛。

全国赛:类似NOIP,来自全国各地的高水平OIer一决高下的最后决赛。最终获得金牌的选手可以免试进入清华北大。

OI竞赛的难度:省级赛<省队选拔赛<全国赛。

 

用这么多文字介绍OI竞赛,也该说说自己了。

 

与其说高中时候的我是一名高中生,倒不如说是一名OIer。每天大多数的时间都是泡在机房里与各种OI题目打交道。

08年NOIP的时候我获得了一等奖。

09年省队选拔赛落败。结果连NOI长什么样都不知道,就结束了自己的OI生涯。除了拿了个一等奖,我的高中生活就没有什么可圈可点的了吧。

2010年1月,我通过技科子电大学的保送生考试。因为不用参加高考,所以现在正在家里等待大学开学。

 

屏幕上又返回了一个“Accepted”,但是我怎么也高兴不起来。虽然已经没有机会参加OI竞赛了,但是每天都要到网络上的题库做题的习惯却保留了下来。如果哪天不去解解题目,写写代码的话,就会浑身不舒服。面对这样的自己,我时常会想:明明已经没有意义了,还要继续做下去,人类还真是奇怪的生物呢。

第二乐章:Variation(变奏曲)

QQ弹出了好友请求的对话框。

“你好,我是科子电大二的ACM队员,也就是说是你的学姐哟。”虽然这句话看起来很可疑,我还是点击了接受

“哟!为了找到你的联络方式,我可是大费周折呢。”看了这位看起来朝气蓬勃的学姐的发言,更显可疑了。

“我的队伍因为有一个队员中途退出ACM竞赛,导致缺一个人。据说你是OIer,所以我们队的第三名队员就是你了!”

说实话我现在有种点“举报”的冲动。

首先这位学姐是怎么找到我的。

其次为什么她知道我是OIer

最重要的是为什么我非要做你们队的第三名队员啊!

面对这突如其来的邀请,我多少有些不知所措。总之先回复点什么吧。

“那个……为什么非要找我不可呢?”

“你想啊,现在大二队伍都固定了,大一新生还没来。就算大一的来了,不培训是不可能参赛的。所以暂时是找不到能够成为战力的队员的。”

“不过你就不一样了,你是OIer,到队里马上就能成为可靠的战斗力。”

本来就不想再继续参加这类竞赛的我正酝酿该怎样婉转的拒绝的时候。

学姐发来了意想不到的消息。

“我看过你的省队选拔赛的成绩,只差一分就能去全国赛了呢,好可惜啊。”

“听说Alexa拿了金牌呢,如果换做是你的话也能拿金牌的吧。每个省只能去一个人太不公平了……

 

省队选拔赛,全国赛,1分,Alexa,金牌……从学姐的嘴里吐出了一个又一个我不想听到的词语。

 

“请不要再说了!”

 

我的身体开始发抖。

如果不是那1分,如果再多拿1分。1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1分,1……

明明都已经决定不再想起来的。为什么要偏偏还要提起来?为什么她会这么了解这件事?

 

“我们之间的差距,不只是1分而已。我的天才是你不论用多少汗水都换不来的。”

 

又是那句话!

 

为什么要来妨碍我?如果没有Alexa,我就能去全国赛了,我就能拿金牌了。明明付出那么多努力了,明明都已经会那么多的算法了,明明……

面对逐渐失控的自己,我努力不去想这件事。不愿想起的事情,不去想就好了。

 

“唉呀,真对不起,让你想起不好的回忆了吧。”学姐察觉到我的异常,说出了道歉的话。

“你一定不甘心的,对吧?”

“被那种人超越,你一定不甘心的吧。你明明已经那么强了,没道理输给他的。”

虽然道歉了,不过这位学姐看起来并没有收手的意向。不,应该是变本加厉了。

 

“我调查了一下,Alexa也会参加ACM竞赛哟。高中没能超越他的话,就在大学对他进行复仇吧。”

“你没必要现在就决定是不是来我们队。下周六有一场ACM网络练习赛,虽说是练习赛,不过因为这次是由ACM传统强校——旦复大学出题,一定会吸引来自全国各地ACM队伍参加。届时Alexa的队伍也一定会参加的。”

“那场比赛你可以作为我们队的临时队员来参加比赛,你可以根据比赛的成绩决定是不是参加我的队伍。”

“顺便一提,我们队伍的名字是UESTC_Rhapsody。科子电大的狂想曲哟~

“你一个人无法达成的梦想,我们一起来帮你实现吧!”

第三乐章:Rhapsody(狂想曲)

最后我连学姐的名字都不知道就结束了和学姐在QQ上的对话。

我要去相信一个连名字都不知道的人吗?

 

周六很快就到了。

“等你很久了哟。上次忘记告诉你我的名字了。”

刚登陆QQ,就发现自己出现在了一个群讨论组里。

“我叫远子,主要负责 数学建模、模拟题和对比赛局势的掌握,以后请多关照咯~

“我叫芥川!初次见面!我主要负责 图论、计算几何、搜索!请多关照!”UESTC_Rhapsody队伍里的另一个队员向我打了招呼。

“我叫H。请多关照。”出于礼貌,我作出了简短的自我介绍。

H同学擅长什么类型的题目呢?”

“我?因为OI竞赛是个人比赛,并没有着重向某个方向发展。如果非要说一方面的话,自己倒是比较喜欢做博弈类的题目。”

“今天的比赛有10道题目,5个小时的时间。由我读ABCD四道题,芥川读EFG题,H学弟就读H I J吧。”看来远子学姐是这支队伍的队长呢。

远子学姐发过来私人信息:

“今天Alexa所在的队伍应该是第一次参赛,队名是THU_Opera。请不要太勉强自己了。记住ACM不是一个人的比赛。”

 

“加油!”

比赛开始前一秒,芥川用最大的字号发送出来。着实吓了我一跳。芥川学长好像每句话都要加个叹号,看来是一位很热血的学长呢。

 

比赛开始。

30分钟大家都在读自己负责题目。

Status(显示当前比赛状况的页面)十分平静,前30分钟内都没有任何队伍提交代码。这在ACM比赛里是少有的。

“两位有发现什么可解的题目么?”远子学姐发来消息。

“我读的三道题没有发现很明显的方法!看来是都需要仔细推敲才能解出来的题!”芥川发来带有他标志性符号的消息。

“我的题目也很难。今天旦复大学的出题人看来有意将比赛的难度抬高了呢。”

“大家都把每道题的大致题意说一下吧。”

在远子学姐的指示下,我们把题意做了简要的说明。

 

“啊!这道题不是2-SAT问题么?!”芥川学长听了远子学姐对A题描述之后大呼。在显示器另一边的我似乎都感觉到了芥川学长拍桌子的声音。

“模型像这样建立出来,就很容易解了。”芥川发来一条消息,并附上了一张带有画有模型的图片。

H你来验证一下芥川学长的方法吧。”远子学姐对我说。

看着远子学姐和芥川学长这么激情,自己多少有些不适应,毕竟这么长时间以来都是单打独斗,从来没有和别人配合一起解决题目。

 

在纸上对芥川学长的方法进行了简单的验证,对于题目给的测试数据,芥川学长的方法是可以成立的。

我把验证过程交给学长。

“那么芥川你就去写这道题的代码吧。”远子学姐有条不紊地指挥着队伍。

“是!队长!”

 

这时Status终于出现第一条Accepted记录:

THU_Opera队把B题攻破!

 

Alexa就在THU_Opera的吧。

 

“我们之间的差距,不只是1分而已。我的天才是你不论用多少汗水都换不来的。”

 

耳边又传来那句话,身体又开始发抖了。

 

“看来THU_Opera拿了这场比赛的Fisrt blood呢。第一次比赛就有这样的表现,实力不一般呢。”远子学姐感叹道。

“不过没关系我们的A题也很快就能拿到Accepted的哟。请相信芥川学长的实力,他的代码一直以来都是以稳定著称的。”远子学姐安慰道。

如果说让我去信任连面都没见过的,第一次合作的队友,那是不可能的。不过听了远子学姐的话,自己还是多少有些安心了。

 

C题仔细想想的话可能和矩阵乘法有联系,不过这里要用到4个递推公式。而且这4个公式是互相关联的,该怎么做啊……”远子学姐说着把4个递推公式发给了我。

我在演草纸上对4个递推公式进行变形,发现了这4个公式之间的奇妙的关系。

“如果把第一个和第二个公式展开,放到后两个公式里面的话。后面两个公式不就变成独立的两个式子了么?然后再用快速幂取模求解的话,应该就能很快解答出来了吧。”我把自己的发现告诉了远子学姐。

“果真如此呢!那就由我来写这道题的代码吧。我一定不会辜负学弟期待,写出能够Accepted的程序的!”学姐留下了必胜宣言,就跑去解决C题了。

 

下面我去看看其他题目吧,正当我这样想的时候,芥川学长发来了新的消息。

 

“我写完A题的程序了!大家等着我的Accepted吧!”芥川学长传来了热情十足的发言。

Submit(提交代码)!”芥川学长按下了提交的按钮。

我紧盯着Status页面不放。

 

我们的程序进入了Running阶段。

1秒,2秒,3秒!

评测系统在第3秒返回了

Accepted

UESTC_Rhapsody 攻破了 A题!

 

Good job 芥川学长!”看了这条Accepted记录,自己也跟着激动了起来。

好久没有这种感觉了。第一次与队友配合完成一道题目的感觉真的很奇妙。

 

之后的3个多小时里我们拿到了C题,D题,H题的Accepted。目前以4题的成绩排在排行榜第11。距离比赛结束还有不到1个小时。

其实第3名到第15名的队伍都是获得了4Accepted。但是由于我们完成4题的时间比较晚,所以只能排在第11名。

THU_Opera则排在第4名。

“我们只要再拿到一个Accepted就能排到第3了呢。”远子学姐观察了下场上的形式分析着。

我明白这句话的意思。只要我们在THU_Opera之前做出第五道题,就能超越THU_Opera。并且现在距离比赛结束只有不到一个小时了,能在一个小时内完成两道题目是肯困难。

也就是说,第5Accepted就是这场比赛的关键!

“话说THU_Waltz好厉害啊!已经做出了8道题目了!PKU_Sonata也做出了7道题目了!果然是国内ACM界的龙头队伍!不过我们也不能示弱啊!”虽然已经进行了4个多小时的比赛,芥川学长的热情仍然没有减弱的势头。

 

我们三人继续讨论还没有解决的题目。

 

“这道B题说是数学题又不像数学题,说是图论题又不像图论题。”远子学姐看着B题纠结起来。

是数学题又不像数学题,是图论题又不像图论题。如果把两个思路结合起来是什么样呢?一股电流从大脑穿过。那么,

“远子学姐,请把你对B题的数学想法告诉我。”

“芥川学长,也请把你对B题的图论想法告诉我。”

听了他们的想法,隐约感觉自己就在真相不远的地方,只要把眼前的迷雾拨开就能解决。

Konig定理?不对。Dancing Links?也不对。

动态规划?这样解决的方程规模太大了。诶?!如果把这个方程的通项公式写出来会不会是Sprague-Garundy 函数的变形呢?

“远子学姐,请把这个方程的通项形式帮我解出来。”

接到远子学姐的通项公式之后,我对芥川学长说:

“芥川学长,请把这个公式的离散图构建出来。凭我的代码能力估计无法在接下来的时间里完成这个复杂的图论程序。”

“但接下来的工作就与求解Nim取石子的博弈游戏很类似了,到时候请交给我吧。”

 

30分钟之后芥川学长将他的程序交给了我。

然后在芥川学长的程序上我又加入了Nim游戏的解答过程。

 

THU_Opera似乎也在尝试这道题呢,不过系统给他们返回了一次Wrong Answer。”在我手工测试程序的正确性的时候,远子告诉我。

 

一定是Alexa在做这道题。Alexa最擅长这类题目了。在省队选拔赛的时候,我就是在博弈上败给他的。

 

“我们之间的差距,不只是1分而已。我的天才是你不论用多少汗水都换不来的。”

 

相似的题型。

 

我完成了程序的测试,样例数据通过了。

 

相似的处境。

 

我坚定的点击了Submit(提交按钮。

 

不一样的是……

 

短暂的等待之后系统返回了一个Accepted,我似乎感觉到了屏幕对面远子学姐和芥川学长的欢呼声。

 

现在的我有了两个坚定可靠的队友。

 

“一个人无法完成的梦想,我们一起来帮你实现!”

 

后记:Scherzo(谐谑曲

第一次尝试用轻小说的风格进行写作。

小说的剧情算是根据自己的经历改编的吧,当然有相当程度的夸大。比如说在电子科大这种男女比例失调的理工科大学里,怎么可有有活泼开朗的学姐来拉我参加ACM竞赛呢?

其实把小说作为新生教育课的作业,我多少有些忐忑不安的。还请看到这篇文章的老师多多原谅。

我认为大学是一个帮自己实现梦想的地方。高中没有实现的梦想,大学可以给你更多的机会,帮你圆梦。不过最重要的是自己。只有自己为实现梦想不断努力,才能有所回报。

友情,信念,梦想永远都是少年漫画里最核心的主题。

我也希望能在大学里收获真正的友情,鉴定自己的信念,为梦想的实现打下坚实基础吧。

 

(全文完)

天津赛区总结

天津赛区 总结

热身赛略去,游行见闻略去。
简述一下比赛过程吧。

比赛开场 林添 和 陈岳航看题。林添读后3题,陈岳航读前4题,我则去配置机器。
待机器调试完毕,我去读题。
最先读E,发现E题可以对字符串排序,然后二分起点,再二分终点做。遂给陈岳航讲题+思路(失误点1)。陈岳航上机拍E。接着林添告诉我I题题意。经过一番讨论之后发现I题是网络流,但是要求字典序最大的,我自以为能解决,等陈岳航拍完E(失误点2)。
这时候陈岳航把E拍完,但是没发过样例,我就跟他一起在机调试(失误点3)。过了样例,我又说了一组数据,结果挂了,继续在机调试(这时代码已经200+行了)。 又调试一会,终于把我说的各种数据过了,提交,返回WA。
林添要求我去写I题。我写完I题发现没法按字典序最大出解,这里发现自己考虑的不周全。这时陈岳航和林添把A题想好了,并且林添发现E题用Trie树更好写。于是陈岳航上去拍A。

我读完C题,给林添讲题(失误点4),并发现这道题和多校联合第一场的题目几乎一样。暴力+KM算法,但是时间复杂度很危险,于是想让林添试一试。
陈岳航A题拍完,提交,WA掉。于是林添上机写E。过一会陈岳航发现A题有可能有负数,修改之后把A题过掉。这时我们第一个AC,此时比赛接近3小时。
过一会林添把E也AC了。

接下来我们要出C。
因为陈岳航打字速度快,于是让陈岳航上去拍KM模板。林添接着把程序写完。样例过,手测各种数据过。提交之后是TLE。因为这个题的复杂度很危险,我们就以为是预处理tle了,就想优化预处理(失误点5)。程序改成双hash预处理后,继续TLE。大家都很纳闷。就开始怀疑林添的模板有问题,我把自己的KM模板换上去,结果WA了,大家各种不理解,就但是放下C题(失误点6)。
我上机改I题。林添和陈岳航发现I题找字典序最大解的方法,我修改之后把样例过了。提交,WA。
这时大家都绝望了,1分钟之后,比赛结束。

失误点1:我不应该给陈岳航讲题和思路,导致思路上的误导。比赛的时候我第一个想的的确是两次二分。
失误点2:字典序问题没有考虑周全,导致大家都以为我的方法是对的。
失误点3:在机调试是要盯着巨大压力的,当时应该让陈岳航下机看代码,而不是在机调试。
失误点4:与失误点1类似,我万万不该给林添讲C题意。因为我理解错一个地方,虽然林添重新读题,但是我的想法先入为主,导致重读题也没发现错的地方。
失误点5:TLE之后想当然的以为是预处理错了,而没有去看KM有没有写错。
失误点6:C题WA的时候我们以为是双hash没卡住。双hash冲突是一件非常小概率的事件。我们到这时候还没想到重读题目!

总结:
1.在机调试是一件效率很低的事情;
2.过于依赖模板,导致模板写错了没发现;
3.状态问题:从Rating上看,我们队伍从开学之后状态就不断下滑。大家没有保持住状态,导致到区域赛只能发挥出30%的成绩;
4.ACM不是你思路正确就能获得AC的比赛。拥有高精度的代码能力才能为AC提供坚实保障。
5.我要扔掉gdb,扔掉模板,立帖为证!

希望大家能吸取我们队的教训,不悲剧。

P.S:恭喜UESTC008获得杭州赛区银牌。

新域名:hzhua.tk

先谢国家

本来想注册个hsama.tk来着,但是影响不好。

这篇文章应该叫Hello World吧.

72松的空间 希望能用的久一点

用公共空间的blog要记得时常备份.

我的hzhua314.cn没备份 结果杯具了.

Position:UESTC科研楼2楼