开学转眼也就一个月了,而自己,什么都没干.暑假为之努力了一个夏天的ACM因为不能参赛而被我任性的抛到了一边,WHUMSC的项目也因为自己能力不足而无法实现,学习么,当然是什么都没干,天天上课睡觉聊天,作业不到马上要交不会写,并且一般还都是copy.
本来还想这个学期可以好好干一下的,现在却被WOW给完全占据,前几天都开始戒掉了,今天又开始玩了…不过相信自己可以从游戏中脱离出来的,只是需要一个过程.
十一的时候打算回家一下,票都买好了,越来越想爸爸妈妈了,还有家里那熟悉的味道和可口的饭菜~
总结,可以这么说吧
集训是一个很不错的经历,虽然在武汉呆了一个暑假,虽然没能回去,虽然自己还是那么菜,比起师兄师姐来还是那么弱,虽然可能感觉自己还是没有什么提高.但是,近2个月的集训中,还是从各位身上学到了不少东西,并且好像明白了Grope的那句话”NB就是一种状态”,虽然自己距离那种状态还有无穷远.
被N多人的成绩给吓倒,被N次考试的rank打击,被N次讲课给郁闷,看了N个让自己感觉无知的code.但是更多次的去想证明自己,更多次的在考试中好好发挥,更多次的去学更多的新的东西,更多次的去努力将自己的代码写的更加漂亮.
呵呵,也是时候该反省一下自己这两个月来的行为了.
7.11正式开始集训,去机房调试机器,占位子.安自己需要的乱七八糟的软件,把学院机器上原来的乱七八糟的东西给删掉.
然后就开始做题,做题,开始的时候龙飞还有计划,准备一步一步来,于是开始去做模拟题.10个题目花了至少3天吧,好像最后还留了一个没做,现在好像也还没AC.
中间因为个人原因回了趟湖南,不过也只是回去了一天,也没回家,就是在长沙绕了一圈.不过对集训没有什么影响,只是偶尔因为这个事情而担心一下.
集训中得知能参加ACM集训的其实都是成绩非常好的,听师兄师姐们说平均分都是至少80+的,90+的也不是少数,并且现在集训队基本上把02,03的优秀同学都集中过来了.突然感觉压力特别大,因为自己没有什么能特别拿的出手的,并且成绩估计比起同样参加集训的低了10分以上,唯一可以欣慰一下的就是自己的经历在某个角度上来说要丰富一点,可能题感要好一点.自己还弱弱的要死,看别人都是好像什么都知道的样子,听课的时候感觉自己全然不会.被龙飞的DP郁闷,被组合数学郁闷,被计算几何郁闷,被aftermath的数学郁闷,被Grope的搜索郁闷.
在ZOJ上做题,某个时期就是为了rank而做题,把problems按照AC人数排序,然后挑简单的做,终于也赶在8.1以前solve过了100,rank进了前1000.这样的确可以满足一下自己的虚荣心,也能练一下自己做简单题的速度和准确率,但是发现题目做不动以后感觉自己这种做法还是太愚蠢了,应该去有选择性的做题的.
这个时候的考试也开始多了,隔三差五就有考试,并且组队的时候经常还是打乱了的,感觉前期打乱比赛还是比较好的,能互相配合,补充自己的不足的地方.考试后一般都能拉下不少感觉可惜的题目,这个时候做题一般都偏向考试了,并且一般上次考试的题目都可以在下次考试前好好折磨一下自己了.还好每次考试也还都能拿出一个过得去的rank.在考试中让知识更全面(个人赛)或者更注意深度(组队赛).
等待结束,等待最后的rank,等待看见自己的名字在前面,等待组队…
希望一直能记住的是AC后的愉悦,而不是RPWT后的郁闷.
“轻轻” 失落
本来应该昨天就开始写这些东西的,但是昨天比较还是没有这么”轻轻地”失落.
昨天一天,手机上都是问别人是否回家,何时回家,是否到家的msg,那些本来每天也见不到面的朋友就仓惶离去后虽然还是依旧不见,但是还是失落.发msg开始没人回了,想说点什么也找不到人说了.点开QQ的好友列表,一列下来都是灰色的.
今天早上一如既往的晚起,但是比平时晚了太多.起来后发现手在隐隐的疼,心里也有什么东西被堵住了一样.
不管承认与否,在机房确实是没有状态,经常走神在看手机,希望什么时候能响起收到msg的”嘀嘀嘀”的声音.看一下任务栏上的时间,就在想,现在,他们&她们,都在干吗?
整个暑假,其实都没有遇见多少同学,但是,一直的msg或者QQ联系,并且知道对方也在不远的地方,心里总是比较踏实,比较和睦的感觉.现在,终于都仓皇而逃,逃回自己温暖幸福的家里,而我依旧一人在武汉的夏天机械的敲着键盘.每次手指跟键盘接触的时候都感觉有些疼:(
整天,人都是飘的,连下午的ZOJ比赛都做的一点感觉都没有…发的msg,一直都没有回复:(
谁人离开?谁人到来?
暑假已经过了一大半了吧,集训也进入了一个相对比较艰苦的时期,发现现在开始做题已经很慢了…
明天就是英语口语的最后一天了,到时候很多人会离去,很多同学约在那个时候闪人…估计学校里面一下子会冷清不少.但是很多高年级的人陆续也该返校了,其实也一样.只不过熟悉的人少了很多,认识的人少了很多,想见的人少了很多,不认识的人增加了很多,想念的人增加了很多,收到的***上估计+86的也多了很多…
小小离别,没什么好感慨的.
改QQ的QMD了,对集训有一些怀疑和不信任自己的成分在里面,To be or not to be,这是个问题…Follow my head or follow my heart,同样是个问题.
集训队估计马上就要开始残酷的淘汰机制了,有人离去,无人到来.谁人黯然离开,谁人轰然倒下,谁人踏着前辈铺就的路大步前行,谁人能昂首挺胸踏进World Final?
昨天WHU的个人赛
队里自己的比赛,本来说是Team的,结果临时改成Personal,稍微有点措手不及的说
做题策略上出现了很大的问题,一开始是按照惯例扫题,但是本次题目长了点,看懂A和B后都感觉没戏,A的BFS优化太复杂,B的那个数据结构不好处理
准备看C的时候听别人说E,扫了一下发现跟HNOI2002的第一题有很大相似(样例数据),直接放弃,去看C和D,C马陈告诉了我基本的意思,D我看明白了一些,都是感觉没戏的.
整个机房都是一股悲观的情调,而我也在抱怨,听zap说题目其实也不难,A和B慢慢弄还是能出来的,所以想了想就是B还有点搞头,于是想B的数据结构.不知道是佩服我心理素质好还是该bs我没有上进心,这个时候居然还因为拉肚子去厕所大号了一把,悠哉乐哉.-_____-b
把B想破了头也没想出来一个比较好的树表达方式,对指针的操作还是太麻烦了点.要考虑建立以及搜索的方便性,两者之间结合点不好找.
ddoonn__cc等一干人都开始弄E比较久了,重新去看了看E的题目,发现比起HNOI2002来还是要简单很多,只有两个运算LOOP和OP,一乘一加,并且变量只有一个,OP后面还不能接n.比起HNOI2002来简化了至少一个数量级的难度.
粗略想了想应该如何操作就开始动手了,途中遇见的困难还是比较方便的得到解决了,但是算法离一开始想的还是有不少的差距,虽然都是模拟.关于递归函数的参数选择上就变了好几次才完全实现所想的的那些功能.在最后提交前对于程序中一个地方还是不很确定,因为最开始实现写那个部分的时候,是在我的参数改变前,但是后来因为过测试数据也没什么问题,所以没有提出比较BT的数据自己测试就直接提交了.WA了马上意识到那个地方出了毛病,自己写了个比较强的数据一测,果然,修改后提交,AC,前后不到十分钟.
在做E的时候其实也抽空想了一下B,突然开窍的提出了一个很好的数据结构,不需要在输出数据的时候再去遍历树,可以直接输出的.并且在建树的时候并不会麻烦多少,想通了这一点,感觉写代码就是一件手到擒来的事情了,稍微考虑了一下输入怎么处理后看了看时间,不够:(写了写主要的处理过程,但是最主要的输入部分还没有开始写,比赛结束了.
吃饭的时候想了想,应该比较好处理的说,同时跟Knuthocean放话说半个小时搞定(没有说大话的成分,考虑了一下可能情况后作出的理性判断),同时赌上了一顿BG.回来后因为一开始的思路就比较好,所以一直没有走什么弯路的搞定了.但是在处理输入的’)’和’,’方面考虑不够全面,以至还进行了一次比较慢的调试并且修改了一下递归内部结构.递交后一次AC,但是比约定的时间慢了2分钟,含恨啊……
一些教训:
1.以后不要太贪图快,读题快并且仔细现在已经是一个优点了,但是在处理算法方面还是显得有些急躁并且考虑不周全.
2.对于E题,一开始纯粹是自己在吓自己,直接导致题目都没仔细看.对E的算法设计也显过于急躁,在思路没有理顺之前就贸然开写了,然后导致在写的过程中几乎对整个程序都进行了改动,并且直接导致了后来对一个for语句的判断不清,致使那次WA然后被罚时20min(虽然事后看来也不影响什么).
3.对于B,则在判断输入的时候忽略了一个应该记住的细节问题,那就是'(‘和’,’绝对是单个出现的,但是’)’后面还是可以接’,’或者’)’的,所以本该25min内搞定的读入建树因为调试和修改超出了预定达到32min,错失一顿BG倒是小事,但是如果是比赛,7min对于一个简单题的影响是很大的.
版聚回来
其实也不能算ACM版聚,因为缺了太多的人.但是应该也是人比较齐的了,除了今年的新队员(貌似我算老队员了^__^),李老师没过来,一个遗憾,littleken现在在广东也没有过来.
aftermath要出国了,NY的某某大学(我还是没有记住),学Science而非Technology,感觉也比较符合他的专业方向吧,偶们的专业术语就是DP方向.
一桌的人除了我都是在为前途奔波的,aftermath出国搞定了,dragonflywww安心保研,属于比较平和的吧.Grope还是在准备考GRE,flirly准备考PKU的物理,两个牛人…zap还是在担心他的保研,不过个人感觉他84的平均分死活也够了,如果只是本校.今天才知道dongfangxu原来是那么牛,91点多的平均分,年级第一,真是BT(很不好意思说这句话,实在是….让人太不平衡了!!!)而dongfangxu的MM居然在零陵学院上学,学的外语,但是为什么一直都能在WHU看见呢?奇怪一下,现在在准备考WHU的研.zap和dongfangxu估计下个阶段还要去数模…
刘老师对我的定义就是未来的旗帜人物,而不是技术人才…-____-b,现在是扛旗的,估计是要起到一个带头作用.重新看了看ACM关于参赛的资格,感觉不是很好了,因为每个人只能参加4次区域赛,所以现在出去是很不明智的,浪费资源.下个学期的公费旅游,算了吧,如果能一起出去观摩而不是参赛倒还是可以^__^.
感觉集训队太多牛人了,今天也知道了很多BT的事情…dongfangxu91+的平均分,dragonflywww全国一流的DP(Grope和aftermath都是推崇倍至),除了我以外他们所有人的学习成绩(又被打击了),Grope那过分的谦虚(也太过分了).
今天喝酒回来就睡觉了,刚好最近也比较累,然后12点多起来洗澡后到现在都睡不着了,郁闷:(
今天PKU_Team_Exercise3
开始了龙飞GG所说的2天一次比赛的时期,今天PKU进行Team_Exercise_3
换队友了,MM谢金晶
开始后感觉还不错,快速把题目扫了一遍就发现有ZOJ上的原题,可以我没做:(,一个是最长不下降子序列,一个是那个键盘的问题.反正队里题目还没有打印出来,于是商量好我做最长不下降子序列的D,让队友去做键盘I.
D是很简单的DP,连最后的序列都可以不用输出,并且数据很小,DP都是用最笨的方法去DP,提交后WA,检查了一下发现了几个可能影响结果的小bug,继续WA,被打击了.
刚好这个时候题目打印出来了,我就把机器腾出来让队友上去写键盘,跟她说了一下题目意思我就去读其他题目了.发现最近看题目特别有感觉,几乎所有的题目都能看懂了,并且很多BT题目都有心情慢慢看懂,不借助词典搞定,但是没发现太容易的(前面几个).
Knuthocean在我读过几个题目后大喊一声:D这个题目是最长上升子序列,不是不下降!是小于不是小于等于,我AC了!马上到机器上把那个’=’去掉,submit后AC,狠狠的骂了一顿PKU的OJ继续看题,然后队友很快也把键盘那个题目给弄出来了,
这个时候很多人都是4AC或者3AC了,真是急人…而PKU那个OJ也真是的,浪费偶那么多时间来改D,并且没有一次AC,罚时罚惨了.题目有问题也不说一下.
看题目后我感觉F比较容易,而队友认为H比较容易,于是分工好两人分别计算,我很快把F写了出来,提交后WA,然后就想是不是不是一组测试数据,并且那个过半到底是基于什么考虑的,屡次提交还是WA.明明是一个简单题却WA成这样,是个人都不能被这么打击啊,于是去写H,本来还以为要高精的,但是ddoonn__cc用了一个巧妙的方法转成了double以内的,反正精度只要小数点后5位,就用log10和pow把乘方改成了乘法.写好后发现数据根本不对,准备打印代码的时候看见自己又是低级错误,一个是把i写成k,一个是把i+1写出i-1,估计是气晕了,修改后提交,AC,终于尝到一次AC的感觉了,但是居然没有一次写AC,失败啊.
这时候我跟队友都觉得J是一个数学推理题,应该可以把那个高精除+高精乘+高精加转成高精乘+高精加,并且判别方法我提出了一个简单的方法,最后证明是对的,但是我当时无法证明其正确性,所以不敢写.于是我跟队友分工她去推公式,而我继续改F.
F在WA了无数次后并且把代码打出来给N多人看了无数次都认为没错后我彻底崩溃了,无奈中跟Knuthocean要来代码对字母(-_______-b也只有气急败坏的时候才这样),结果一样的思路和算法写出来差太远,本来不抱什么希望了后来突然描见输出的时候把n和p给写反了-___-b,因为自己的测试数据一直都是n==p,所以也没有发现这个问题,改动后就AC了.当时对自己的bs真是有如滔滔江水连绵不绝…
这个时候队友也推出了J的公式,我看了看,高精的单精乘方+高精加,直接用高精乘实现那个高精的单精乘法,然后加了一个高精加,TLE了T___T(给我一个RP差的理由先),想了想如何优化,被打击的让队友去写了,跟她说如何优化就OK了,果然很快队友就AC了.
这个时候过5个,队里还算比较好的,Knuthocean跟ddoonn__cc还有mast他们都说G可以贴龙飞的标程过,于是找到那个标程,看了看接口,叫ddoonn__cc说了说意思,自己写了个输入输出和转换函数就算了,提交后WA(-___-b,不要紧,习惯了),然后看了看怎么回事,这个时候dongfangxu已经过来登记结果了,我抗议比赛还没结束继续改代码,终于看到了龙飞的标程数组从1开始而不是0,小小修改后提交,AC,刚好dongfanxu过来,登记6AC,爽!!!!
今天的RP真是差到了极点,没有一个程序是一次写对的,并且回去后看队友过J的代码,跟我的算法也基本一样,没有优化什么,居然就0s过了,后来问别人了才知道可能是我对于t==1的情况没有考虑好.
不过最后结果还算能过得去,6AC,也是一次突破了吧,但是这次的题目也太简单了点,并且一共有10个题目,所以也没有什么好炫耀的,mast他们还过7个了呢.
对POJ极度不满,题目有错也不说,害我一开始就在D上面不停的WA,弄得信心全无,后来写代码都有心理障碍了,只要觉得能让队友搞定的都不去抢了,还主动让掉.应该也算一种团队能力吧:)
很乱的心情
不知道为什么最近老是有想写点什么并且想说点什么的冲动,也许被压抑太久了,也许是kitty去了重庆终于让心里最后的一丝希望破灭,然后baby又用几乎威胁的口气跟我说他一定回去重庆的.
其实,我想说,我在武大很好,这里有那么多我特别欣赏的人,有那么多的牛人,有无数值得我学习的人和值得我学习的东西.发现自己越来越不足为道,在卧虎藏龙的武大,有太多的人其实都是曾经梦想中PKU的人选,只是各地不同的高考政策使得很多人和我一样来到了武大,也是不错的选择,虽然心里仍然有那么一丝不甘.
思绪很乱,我都不知道要说什么.我想跟kitty说,我怕我真的要忘记你了,这样下去我太累了,并且我也不知道你到底怎么想的.我怕自己再次受伤后真的伤口只能一直滴血而无法愈合,或者是现在我真的想找到一个人来使我彻底忘记你,同时填补或者让我忘却那些刻骨铭心.
我想跟现在和我在一起的女孩说,我喜欢你,虽然现在我都几乎处于与世隔离的境界,每天看不见几个女生.我想说的是我只能看见你的好,然后从你身上看见我是多么的不上进.或许我只是想找个很好的朋友,同时能够提醒我并能一起携手前进的人,但是,我做不到那么单纯.
我想对自己说,你真的明白你现在在干什么吗?你到底想干吗?你的激情到底去了哪里,随便什么的激情都没了.曾经你那么狂热的投入到了OI的世界里,现在你以为你可以像以前那样全身心的投入到ACM的世界里,但是你变了,你对于这个已经像看破世间万物的老人一样只是想站在旁边静静看着.
你知道你以后的目标么?不管在哪里,无论ACM或者MSC.你明白出路在哪里吗?你选择的是什么?
对于女孩,你是否还是忘不了那个曾经在你的生命里留下了太多太多的kitty?但是,时间是最好的疗伤药,你难道还没有醒来?其实,生命才刚刚开始,很多事情不要那么固执.并且,生命中的机会不是一直存在的,有些事情,有些缘分,一旦错过就不再.
先想到这里,其实回头把思路理清还是可以写很多心情的.现在没有写日记的习惯了,在blog上涂鸦吧…
今天的woj_teamtest1
WHUACM2005第一次内部组队赛,人和上次PKU的一样,dragonflywww出题,3简单+2中等,都是最近上课讲的东西
本次要求2个人用一台机器,分工要搞好,提示可以使用打印机把代码打印出来,然后在纸上自己debug
分工是蓝蜂看后面两个,我看前面3个,他一开始就说D比较好弄,我看了后发现C的数据量比较小,是可以不用母函数DP直接DFS出来的,然后我上去写C,自己随便测了几个数据有问题,于是让蓝蜂上来写D,我把代码打印出来坐一边自己看去了
D是一个超级麻烦的题目…简单但是麻烦,是我最讨厌的难写但是能过的那种题目,跟上次PKU的A差不多,真是辛苦蓝蜂了:P
我在一边很快找到了C我的代码的问题所在,改变了几个值,同时对剪枝强化了一下,提交后AC,开心^___^
这时候我把所有的题目都好好看了一遍并且简化成了数学模型,A无疑是一个母函数的DP(事实证明这样做也是不对的,真正的标程是递推),B是一个计算几何题,人工来思考很简单,但是用code实现太麻烦,C就是一个01背包的变种,已经被AC了,D是一个模拟题,简单但是麻烦,E就是最短编辑距离,经典DP,但是上次龙飞来说过后一直没看,最近在写搜索算法,自己想了一下觉得太麻烦,就没写了
蓝蜂把D写好后测试了几个数据都OK,然后提交,但是WA掉了,他想了想重新测了个数据,果然有问题,这个时候他把代码打印出来在一边处理,我把A用搜索写了一遍,提交后TLE(不TLE才怪了),然后感觉用搜索出不来,把机器让给蓝蜂调D,我去看他的D决定自己去试试看
弄了比较久蓝蜂的D还是有问题,于是跟他说这个我来试试看,跟他说清A的意思,让他用母函数解决
我上机按照他读懂了的题目很快写出了代码,跟他一样,前3个条件(回文,只由两个数字组成,步长1的递增或者递减)都很好解决,最后一个循环的条件不好判断,不过我的是用数组实现的,调试相对容易,多花了些时间但是也搞定了,把所有可能的数据自己测试了一遍提交,AC通过
这时候A是蓝蜂在做,我看B能想出算法,但是计算几何实在是搞不定,而E我把问题复杂化了,反正时间也不多了,就当是进入垃圾时间了
OVER
晚上看解题报告发现C用搜索实在是幸运,本来这个也应该用母函数来解决的,不过数据比较小(是最坏情况,不是钻数据空子),并且我想了想按照我的剪枝绝对能PASS的,最后看Status,我的代码还是最快,最小内存,最小代码长度的^__^
E那个DP其实和LCS是一样的,但是我把问题复杂化了,so…不应该啊!!!!!
B的算法和我想的果然一样,不过我还没有考虑两根线重合的情况,但是就算算法对了写不出来也是白搭…-_______-b
A龙飞说是递推,没人过所以没有解题报告,但是Knuthocean说了他看了代码后的理解,不过还是没有看懂:(,太麻烦了,看标程的代码,也看不懂:(
感觉最失误的就是没有去做E,虽然自己以前没做过,但是想想也应该不难的,尤其是一开始自己就把问题复杂化了更是不应该,最后的rank一点也不好看:(
今天的PKU monthly
今天PKU的monthly,有钱,估计会吸引更多的人,并且现在是各高校集训时间,人会更多.事先去调查了一下,发现能过一题基本就能保证top100了,看到的最差是top125,最好是top45.前面12次loutiancheng拿了4次冠军,-____-b
今天开始分组弄,暂时还是2人组,偶的N多队友提议都被枪毙:(,不过也好,看看自己到底什么水平,其实大家也都是很不错的,刚好取长补短
一开始和蓝蜂分工,他从前面开始,我从后面开始,一开始他就耗在A上面,我也觉得不是很难,只是处理比较麻烦(偶最讨厌这种了)
我因为是换机器用,等把东西调试好都过了很久了,快速把所有题目扫描了一次,觉得H是最容易下手的,开始写,很简单的题,只用了不要一屏的代码就搞定了,在纸上推了一下提交,WA T_T
重新考虑了一下,发现题目中的C完全是一个陷阱,根本不需要用,结果一改,代码更简单,AC了,但是时间都快过了1个小时,这个时候队里N多人都已经AC好久了,就是我排在后面,真是一失足成千古恨啊
然后看F,感觉是个DP题(事实上也是),但是数据量N大的说,虽然时间也有20s,写代码后感觉不好处理,估计会超时,蓝蜂说你写了就交吧,提交后等了N久,TLE T_T
把能优化的地方全都给优化了一遍,感觉时间复杂度还是降不下来.10^6的输入数据,做出来至少要10^12的数量级,20s绝对不够,不过抱着死猪不怕开水烫的心态还是submit了一把,TLE,决定放弃F,这时已经过了2个小时了
把所有的题目再扫了一遍,还是没有可以下手的,于是看蓝蜂写A,他弄了N久都没出来,而这个时候一个机房的人都在弄A.我准备玩的时候被人说了一下,于是开始写A,基本算法已经在脑子里了,就是判断上下两个对应的数字就可以了,使用分开调试的方法花了一个小时左右基本搞定,但是发现数据大了就不对了:(,感觉是精度的问题,于是把需要大数据的地方都改成了long long,结果还是在非常大的数据量的时候有问题(感谢Grope提供了几个大数据的输出,不然怎么死的都不知道),后来调试的时候发现long long=long*long的时候long long得到的还是long范围内的值,一气之下把所有的long都用long long替换掉,看了看自我感觉良好,提交
这个时候N多的人在做F和D,都是限时超过20S的,等了半天才等到我,看时间已经剩下不到20分钟了,而机房没一个人搞定此题,焦急的等待绿色的Waiting变成Running,然后看着变成蓝色的Accepted,差点没幸福死
最后就是这样了吧,其他人也都没有AC,其他题目也还是下不了手
第一次在队里排NO.1,好爽…