Skip to content

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

2 Comments

  1. 西木 wrote:

    我看不懂。。。在你面前,作为大龄青年我都抬不起头了。。 :roll:

    Thursday, March 22, 2007 at 22:14 | Permalink
  2. tianyi wrote:

    这种东西没多少人能看懂的……“左手程序右手诗”可不是瞎吹的。(是有根据的吹的 8) )

    Friday, March 23, 2007 at 11:32 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*