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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1070-1079)  

2012-04-15 12:11:00|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1070:修车:裸的二分图最小权匹配。若用最小费用最大流来写用时460ms,用KM来写用时104ms。
1071:组队:先把不等式调整一下,然后得到:A * height + B * speed <= minH * A + minV * B + C,于是计算出两个序列,一个按速度排序,另一个按A * height + B * speed排序,然后枚举最小高度,再枚举最小速度就可以了。
1072:这题是DP。
1073:“给你一个图,把1到n的所有简单路按长度从小到大排序,长度相同按字典序排序,问你排在第K个的路径是哪个。”首先我们要放弃邻接表,用前向星存图,使得所有边都是按字典序存下来的。然后二分答案,即K短路长度,DFS判定。得到了长度,再DFS一遍,求出K短路。在这里要注意剪枝……我是在DFS里套一个SPFA进行剪枝的。
1074:折纸:计算几何题。逆向思维。想着把纸慢慢翻开时候的情况,然后就成水题了。
1075:最优驾车:共三个人AC此题,其中一个是个我不认识的人,另一个是我的大号,另外一个是我的小号。我小号是专门用于提交0AC或1AC的题的,不是用来增加我大号的AC率的……这道题其实是记忆化搜索。f[i, j, a]代表到达(i, j),用时为a时的最优方案是多少。因为a可能为分数,所以把所有的分数都乘以最小公倍数来存即可。
1076:奖励关:递推即可。好像这种算概率的递推有一个特殊的名字——马尔可夫链。
1077:天平:首先把质量相同的砝码用并查集合一起。然后枚举进行判定……相信我,会纠结得你想跳楼的……
1078:斜堆:呃……找找规律……递归求解。
1079:着色方案:这题是DP。

好吧我很懒……题解都三言两语的……

知识点总结:
KM:会写不会证,求大神证明之。
  评论这张
 
阅读(535)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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