Skip to content

Category Archives: 军机处

NOI计划,五月下

1,《组合数学》《Code Complete》两书看完并写完全部的缩写/笔记,这个尽量快些,每天都要有进度。 2,后缀数组要会O(n)算法,height相关的东西要写熟;后缀树的话,至少会个O(nlogn)吧,要多做几道相关的题。串处理方面一定要加强,看论文,看CLRS。 3,做SGU,所有1000+的题目要都做掉,然后写一个阶段的总结。然后开始做600+的,尽量也都做掉。看看有没有相关的好玩儿的数据结构/算法(估计不太有)。 4,本月暂时不学Vim和Linux。 5,不能荒废时间,放松一下可以,你知道怎么样算荒废时间。

鞍山一中邀请赛总结

这次的题目还是不错的,有梯度,我的最终成绩是200/400。 第一题是简单的枚举,注意是可以翻转的。我错了10分是因为“Impossible”写成了“impossible”……汗一个…… 第二题其实是贪心,先把所有的东西排一序从大往小了吃就行了。我考试时理解错题意了……只得了10分……这真的太不应该了。 第三题要判断树的同构。我是这样做的:求出树中每对节点间的最短距离,对于每个节点的序列先排序再hash得到一个数,再对现在的n个数先排序再hash,就是这棵树的hash值。就这样AC了。 第四题是一数学题……不说了。

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

省选训练,0410总结

自从省选训练的上一阶段(做完及总结USACO)圆满结束之后,又过了几天,有必要把这几天再适当总结一下。 写了平衡树两种——自顶向下Splay以及Treap,感觉对后者理解比较深刻,但前者实在强大,二者是都需要十分熟练地掌握的,在省选前还要写个两三遍。 理解了虚二叉树,但它的可替代性比较大,不需要再练习了。 写了2007天津选拔一试,第一遍得分只有140/400。第一题对了,但一开始没看清题导致浪费了一点时间,要注意通读、精读题目。第二题现在还没完全搞懂。第三题当时对了一半,应该主要是没有预先排序的缘故,没有深刻地理解某些东西。第四题的确是想复杂了,当比分有序之后就变成了最少用几个不下降序列覆盖,这个东西等于最长下降序列的长度,这也是刚刚知道的。总之,注意读题。不过想来真正考试的时候有纸版的卷子勾勾划划应该好些。 写了2006浙江选拔一试,第一遍得分170/360,很有进步。第一题显然需要用两个平衡树来乱搞,根本就没有写,哪天精神状态很好时可以尝试写一下,不过考试时真遇到这样的题估计还是放弃;第二题真是要感谢USACO,和“丑数”原来是一样的,WA一组似乎还是因为没看清本质——质因数个数大于前一个数里面的最小的,多加了一个限制条件就漏了解。第三题核心部分是很简单的DP,但预处理得出所有的路径是一个麻烦事;在得出路径时我剪枝很多——当前可以到达终点的只能往终点之类,而这是错的,这是有权图,而且不一定满足三角形不等式,把这剪枝去掉,再加一个若有多余的点则剪枝的条件就能AC了;第四题树形DP,很简单,一遍AC,yeah(不过分值怎么偏小呢……)!这次给我的启迪是:剪枝条件是一定要仔细思考、耐心检查的部分。 下一步准备打印一些经典的代码,比如treap、splay、flow、hungary,等等……多看多背。 本周每天至少写两套题,写一个新算法。