Skip to content

Tag Archives: 省选

给正为4月26日奋斗的学弟学妹们

大约是去年侥幸得了河南省选第一的缘故,好几个下一届的学弟学妹找我问怎样准备省选,在这边统一回答一下。 第一,把USACO Training做完。我曾经不无天真地认为,只要做完了USACO,进河南省队就没有任何问题。然而事实上,按照07年的情况来看,这个判断好像真的没有例外。在现在时间比较紧的情况下,写不出来就看题解没问题,但要保证看完题解以后代码是自己独立完成的,且你真的理解了这题目的算法。 第二,学一些最常用的高级数据结构与算法,但不必全学,按照自己的时间安排和兴趣选学好了,因为谁也不知道会考什么。参考清单:网络流(最好学Dinic算法,要知道最大流最小割定理的内容)、Treap或者Splay、KMP算法、Trie树、线段树、求割点和桥、收缩强联通分量。 第三,找一些高质量的套题限时做。这样的目的一方面是查漏补缺,另外是培养比赛的感觉。推荐山东、浙江、天津、重庆、河南的一些省选题,难度适中且比较贴近国情。也推荐USACO历次月赛的Gold和部分Silver题,这些题的好处是有完整的题解,当然阅读英文有障碍的就很遗憾了。 第四,把心态放低,告诉自己省选没有那么重要,进NOI并不是值得赌上全部去追求的东西,若选不上不一定是坏事,在河南这种太受歧视的地域,也许有保送资格以后把文化课搞好才是更合适的道路。把心态放稳,告诉自己河南是弱省,根本没什么强人,只要发挥正常就能进。心理调节很重要,我的经验是,当你心中不会经常出现“省选”或者“省队”这些字眼,而只会专注于一个一个的算法、一道一道的题目时,状态是最好的。 第五,需要更多心理调节以及任何合理的帮助可以直接打我手机,号码给我留个言就会告诉你,MM特别欢迎。

郑州之行

20日。 物是人非。Nothing changed but you. 这是我的翻译。我不想多做解释。 一往如常的街道,依然闪烁的城市霓虹,去过的餐厅,和眼前似乎突然增多的美女。 提包里几十页密密麻麻的打印纸,记载了这三个星期的努力和梦想。考前看两遍,重要的都看了三遍。 21日上午。 进考场,在座位前看到几个在网上见过的同学,寒暄几句。 发试题,看完题目后就平静下来。没难题。 一个小时左右,写完题目。第一题是O(n^2)的算法,第二题是有技巧的暴力算法。 想出了二维RMQ该怎么弄,重写一遍第二题,约用半个小时。 将第一题改成了O(nlogn),原型/迭代,很Agile,很eXtrem Programming。 两个小时过去了。 剩下的一个多小时,对前两题设计测试数据。 出来以后对老师说,展现出了自己的全部真实实力,但也没有超常发挥。 中午昏昏沉沉,没怎么睡。 下午心态挺轻松,两道题都没有去想完美的算法,第一题用了随机化贪心,第二题则搜索加剪枝。 出来以后,便听说我是上午的第一,190分。同时得知上午的第一题竟完全理解错了题意。 后面的事情不复杂。过一会儿就知道自己是总分第一。看到了郑州的一些牛人,略谈几句。 晚上老师请客,无聊地看电视,两点还没睡着。 次日归家。 今日,学校门口已宣传起来。

4月21日,请祝福我!

4月21日就是省选了,这是我放弃其它一切付出最大努力认真准备了三个星期的一次考试。 它的结果将密切影响我高中阶段的走向,所以很重要。 我已充满信心和勇气去面对它。我相信我超群的实力,我相信我一定会成功。 我的朋友,4月21日,请祝福我! 明日是最后的调整时间,休博一天,勿念。

省选训练总结0416

很容易看出来这几天的效率降低了,似乎已经没有了那么多的算法要学,也没有那么多题目可写。是调整状态和心境的时候了。 消除了写并查集时的一个重大缺陷,值得微笑。 初步掌握了用矩阵乘法优化的DP,第一次写这种题目就AC了呢!实在是太高兴了。 掌握了求凸包的Gramham’s Scan的简便实现方法,大大缩短了代码长度。 认识了一位伊朗同学,呵呵,练了练英语,体验了不太寻常的经历,是很有意思的放松方式。 做了几套题目。山东04day2很有意思的说:prz是区间加法,lan我用了记忆化搜索(又很练了下静态调试),pro考到了并查集,最后作了一个不太严谨的优化,不过还是过了,呵呵。浙江05day1有广搜,有矩乘的DP,有思路特别的DP(其实还是跟背包相关)。这两套题目做的时候好像分别都放弃了一题,但基本保证了剩下的题目不出错(除了没辙的思路方向问题),这样也是值得的。学会细心,学会取舍。 做USACO的feb07gold也很有收获。newbarn是对中位数的比较强的考察,我更加理解了这个概念和应用,不过我还是觉得标程的算法有洞;lilypad是点带权值的最短路,给了我最短路模型构图的新思路;csort考到了置换群,算是对这个生僻的东西再用了一下。这次比赛的题目很有些“剑走偏逢”,真是收获不小。 下面这几天保证一天至少做一套题目就行,看看比较重要的代码,再编几遍重要的东西,比如说平衡树什么的;每天晚上可以看看小说放松自己,尽量午休,千万别把自己累着了;基本上没什么新东西需要学了。

省选训练总结0412

这两天里又学了好几个新的算法,做了好几套题目,还是蛮充实的呢。 Hungary算法现在已经可以熟练快速地一次写对了,对它的理解也有更深入哦。 RMQ问题掌握了线段树和ST算法两种方法,应该是够用啦,不过ST还没到能够一次写对的程度。 KMP算法虽然早就知道是第一次写,呵呵,还抄袭了libg++。反正就那几行,大不了打印了背下来嘛。 LCA问题的Tarjan算法基本上掌握了,不过还是要找时间再看看。 图的割顶与桥已经理解的比较深刻了,其实只要记住Low的定义以及充要条件就好了啊。 又做了好几套题了,有必要总结一下。 写了浙江2006二试。题真的很难呢,得了200左右/400。kaj不用说,xn就不多研究了,polygon和gen(特别是前者)有空还是争取能写满分。 写了好几套USACO月赛。jan07gold里面的lineupg就是RMQ;psolve是一道较难的DP,有点像多进程,应该用心体会;schul就不研究了……nov06silver里面badhair一次写对的,自己设计的借鉴了最小前缀和的算法,与标准答案不太相同哦;bigsq只要想到了枚举对角线,加上我的无敌的剪枝,还是相当容易的,第一次错了几个,原因是没有考虑到某些两个点是不能作为合法的对角线的;rndnum是组合数学,自己调试了半天,最后还是出了一点点低级错误挂两个点,不过这类题目应该已经比较熟练了。nov06gold里的plank就是一合并果子,太水了一次AC;block是第二最短路,不知道在哪里听来的可以用SPFA解,自己写了一下一次AC了呢,看来我对SPFA的理解已经比较深入了;cowfood初看时不知道怎么做,看了analysis才知道是状态压缩的DP,应该由“放了以后四周就不能放”这个条件联想到,照着标程画瓢了一个程序,还要仔细体会。 接下来几天一是要做真题,二是要做USACO月赛,均摊每天不少于两套嘛。最近没怎么做搜索题好像,要找一两倒做做,特别是广搜。好像想不到什么需要学的新算法了,树状数组是需要再写写的。