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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

省选前衡八题目汇总梳理(1000-1009)  

2012-04-08 19:53:19|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1000:A+B:我就不说了……
1001:狼抓兔子:求平面图最小割,等价于求对偶图最短路。
1002:轮状病毒:有人说是DP,但我使用基尔霍夫矩阵推的。结论都一样,是F(n) = 3F(n-1) - F(n-2) + 2。
1003:物流运输:DP+最短路。f = min{cost(1,i), f[j] + cost(j + 1, i) + k(2 <= j < i)}
1004:Cards:伯恩赛德引理+DP 传送门:http://vfleaking.blog.163.com/blog/static/17480763420111169520556/
1005:明明的烦恼:用普吕弗序列推公式。写这题是学到了另一种高精度:记录一个数的分解质因数后的形式,适用于只用乘除的题目。
1006:神奇的国度:弦图的完美消除序列。这种东西我忽略掉算了……除了这题貌似我就没见过哪题考了这玩意儿。
1007:水平可见直线:裸的半平面交。把直线按极角排序,然后扫,开个栈。
1008:越狱:啊!大水题!!!简单的组合问题,计算时快速幂一下。注意逆向思维。
1009:GT考试:KMP+矩阵乘法。

知识点总结:
平面图最小割:不会的话建议学学,今年浙江省选就考了平面图最大割的(http://www.lydsy.com/JudgeOnline/problem.php?id=2657)。原理相同,只是一个是求最短路另一个是求最长路。
基尔霍夫矩阵:呃,不会的话了解一下吧。不了解也罢。
伯恩赛德引理:同上
普吕弗序列:同上
弦图相关知识:同上。(详细可见陈丹琦的论文:《弦图与区间图》)(这东西我已经忘干净了)
(HNOI2008怎么考一堆奇怪的知识)
半平面交:求半平面交最快是O(nlogn)的算法,但我没写过完整版的半平面交。有两种算法:分治和排个序顺着扫。
KMP:字符串匹配算法。matrix67写过一篇著名的博文。
矩阵乘法:这个可以用来优化递推式。去年省选考过(http://www.lydsy.com/JudgeOnline/problem.php?id=2326)。

       距离省选还有13天……以后每天梳理一下我在衡八上做的题好了。话说AC衡八上第一题还是去年8月10号的事,距离现在已经有半年多了。截止我写日志,我衡八顺着做做到了1110,再不梳理一下就忘光了……今年省队名额蒟少,虽然写的不很详细,ds、lk、hf、fjh、chy、albus,但愿你们看了能有所帮助吧……
  评论这张
 
阅读(828)| 评论(3)
推荐 转载

历史上的今天

评论

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

页脚

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