Skip to content

Tag Archives: USACO

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

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

我的USACO心得

几周前终于做完了USACO Training的全部题目,感觉收获极丰,便有将这些题目做一总结的想法。 写时根据算法对题目进行分类,只求使自己从USACO中得到的知识条理化、系统化,并不求能给他人什么教诲。 笔耕数日,终于约一周前写完全部四篇初稿。又经过近日的几度增添润色和几位好友的帮忙校对,终能在省选的前夕发布所谓“正式版”。 本人自知水平有限,文中断少珠玑之言,而若此“心得”能为你的OI征程有所裨益,也不枉本人几周来的一番心血。 下载地址

USACO Training 通关

USACO Training是一个美国的计算机竞赛题库,共有循序渐进的6章,23节,97道题目。其特色有:1.题目质量很高。2. 不做对本节的所有题目就不能看到和开始做下一节的题目;3. 除题目外,还有讲解精辟的课文。4.每道题都配有详细的分析和讲解,但必须做出这道题后才能看到。 2006年11月22日,注册了 USACO 的 ID:dd.ener1。 2006年11月30日,做完 Chapter 1: Getting started (21道题)。 2006年12月11日,做完 Chapter 2: Bigger Challenges (19道题)。 2006年12月23日,做完 Chapter 3: Techniques more subtle (21道题)。 (以上做题目的时间都是利用的每天中午约一个半小时。) (2006年12月26日至2007年3月1日做题进程停顿,2007年3月也几乎没有在做。) 2007年3月30日晚,开始省选集中训练,全天在机房。首先就计划做完 USACO Training。 2007年4月2日,做完 Chapter 4: Advanced algorithms and difficult drills (15道题)。 2007年4月5日中午,做完 Chapter 5: Serious challenges (18道题)。 2007年4月5日晚,做完 Chapter 6: Contest Practice (3道题),通关USACO Training。 明天开始整理所有程序,本周内写作《USACO心得》,并发布定稿的“USACO […]

USACO Elite 2007 March Competition

这是第二次参加USACO的月赛。由于上次的失误加之自己太懒,这次参赛还是只能参加Bronze组……郁闷死……不过Analysis Mode的存在就是为了我这种人吧,哈哈哈。 正赛的成绩还不赖,只错了一个点,是第三题n=1的一个特殊情况没考虑到。下次就能进Silver了太高兴了。教训是测试!还是测试……做完了别觉得没事儿了溜达,拿出举办比赛的劲头从各种刁钻角度出数据测试啊! 今天看到Silver的题目,觉得真有意思!于是晚上就开始做呀做呀。 第一题开始根本没理解题意,第一个程序只残忍地过了三个点。看来我英语还是不是那么好。诶……后来在matrix67牛的帮助下完全理解了题意就做出来了。对于每个节点求出两个值,一个是它到barn的路径数,一个是它到相应的 grazing locations的路径数。每条有向边两边两个数一乘就是该边的possible paths。找最大的即可。 第二题很有意思。事实上考的是线性扫描算法。你知道的我对这东西向来不太灵光……写出的O(n^2)算法猛优化也有三个点超时。这种用hash辅助的线性扫描一定要记住。关键是转换条件,注意前缀思想。 第三题是我花费时间最短AC的,但基本也是我最不懂的……(汗……)一开始乱搞出一个二分答案+贪心的程序,竟然只有三个点没过!原因还是一开始的循环不变式没有保持,二分的下界有问题。不过这道题乱搞的结果的出乎意料也是情理之中的,谁让我对二分答案和贪心都掌握得那么好呢? 下次做Silver,再下次一定冲Gold!不过据说Gold的题没有Silver有意思……看来如果真的得到了Gold的Invitation又该面临艰难抉择了。 本次的所有AC程序: balance.cpp expense.cpp fireshow.cpp latin.cpp round.cpp traffic.cpp