注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1010-1019)  

2012-04-09 20:11:24|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1010:玩具装箱:斜率优化DP。方程是f = min{sqr(i - j + 1 +sum[j] - sum - L) + f[j]}。
1011:遥远的行星:坑爹题。用数学公式随便搞搞就出来了。传送门:
1012:最大数:这题是很基础的RMQ问题。ym这题用线段树的……其实这题是单调队列+二分查找。WJMZBMR用单调队列+并查集时间复杂度比我低程序却跑得比我慢……orz呀orz……
1013:球形空间产生器:列个方程,然后消掉二次项,然后高斯消元。
1014:火星人:这题是rp完全问题……用splay维护某一段字符串的哈希值,哈希的话我用的BKDHash。每次要查询就先二分答案,然后判断哈希值是否相等……各种拼RP……
1015:星球大战:逆向思维就行了。它要求不停地删边,于是我们反过来,把命令倒着扫,问题变成了不停地添边,不停地询问联通块个数……一秒钟变水题……并查集即可。
1016:最小生成树计数:这题很有趣。因为要求最小生成树个数,所以我们考虑Kruskal的过程:给边排个序,然后顺着扫,用并查集维护。那么什么决定了Kruskal产生的最小生成树的样子呢?答案就是——排序!同一边权的边顺序不同,产生的最小生成树才可能不同。但是,同一边权的顺序对后面Kruskal的运行无任何影响。基于这样的思路,我们可以把边按边权排序,像普通Kruskal一样从后往前依次处理每条边。不过边处理还要边找出每一块边权相同的边们,用乘法原理把方案数乘出来。处理边权相同的边的方案数时,由于边权相同的边很少,用dfs决定它们是否被选中,选中了的就将两端点归为一个联通块,然后再判定是否每条边两端点都在同一联通块中,是的话return 1,不然return 0。
1017:魔兽地图:这道题我印象很深……当时我做这道题时网上题解很少……然后这道题纠结了我很久……其实这道题就是道树形DP。具体做法就不说了。
1018:堵塞的交通:这道题是用线段树维护图的连通性。每个节点开个数组记录在当前子图中,(l,0),(l,1),(r,0),(r,1)四点之间是否有路可到达。很是感慨的一段整齐的代码:

图片

话说还有一题,ds总是在念叨。WC2009 shortest(http://www.lydsy.com/JudgeOnline/problem.php?id=2104)这道题也是用线段树维护图的连通性,ymds把shortestAC了。我蒟蒻就没写。

 1019:汉诺塔:强烈鄙视某人不理解WJMZBMR推出的公式却死搬照抄。WJMZBMR的方法我就不说了,我用的是我自己想出来的DP。详见albus的百度空间:http://hi.baidu.com/mathalbus/blog/item/609d598ecaffd70eb21bba23.html


知识点总结:
斜率优化:能优化形如f = min{g + h[j]}(或max)的式子。要用这种优化,就把关于i的归一类,关于j的归一类,然后观察h[j] < h[k]的条件,即h[j]/h[k]<1。具体请见周源的论文《浅谈数形结合思想在信息学竞赛中的应用》。
单调队列:这玩儿有各种应用,如上面那个斜率优化。
高斯消元:能解多元一次方程组。拓展是解线性模方程组和APIO时莫涛讲的xor方程组。
字符串Hash:Hash真是神奇的东西。Hash的比较:http://www.byvoid.com/blog/string-hash-compare/
splay:此物不是平衡树,胜似平衡树,是OIer的杀题越货之必备良品。(ym用Treap相信rp的,ym会写SBT的,ym会写AVL的)
并查集:通常用来维护图的联通性。
Kruskal:求最小生成树的。
树形DP:通常写的递归,所以比较好写,但是慢……这玩意儿倒是有非递归版本:1.手工栈(非无聊勿写) 2.记每个节点还剩几个儿子,DP完一个就把父亲的儿子数减一,如果有节点儿子数为0,就插入到队列中。
线段树:变换多端的一个数据结构。通常是递归的,但也有非递归版本:zkw线段树。碰到线段树的题使劲写就可以了。
  评论这张
 
阅读(1003)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017