Skip to content

Tag Archives: 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