Skip to content

省选训练总结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月赛,均摊每天不少于两套嘛。最近没怎么做搜索题好像,要找一两倒做做,特别是广搜。好像想不到什么需要学的新算法了,树状数组是需要再写写的。

Post a Comment

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