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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

在北京的集训(7-20)  

2012-07-20 20:31:48|  分类: OI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天依然何博硕讲课。
三个题,还比较可做。

第一个题:
给一个有向图G(节点数<=50),求一片森林,满足:
A如果是B在森林里的祖先,那么A在G中可以到达B;
如果B在G中可以到达A,那么B不能是森林里A的儿子;
如果A、B在G中可以相互到达,那么他们在森林里不能有相同的父亲。
你要输出森林里至少由多少个树组成。

这题很经典吧,一看就是网络流的题。如果你打算去NOI,那么建议你先思考一下建图的方法。
先计算强联通分支。
之后,核心思想是让父亲和儿子建立匹配的关系,可以:
每个强联通分支作为左边的点,向右匹配(当儿子)
每个点作为右边的点,接受左边的匹配(当父亲)
这样,可以构造一个网络流的图。我们发现,刚好能够满足题目所说的三个条件。
当然了,也可以贪心。(这是我的做法)
方法:拓扑排序,每次插入一个点,让他当尽量多的人的父亲。这个可以用数学归纳来证明正确性。

第二题:
给一个树(N<=50000)(每个边有权,权可能是负的),对每个点,求到他距离第K小的点是谁。

这题很变态啊。我想到的时间复杂度是O(Nlog^3N),代码写了5K(之后竟然一遍AC)。
算法一言难尽,总之就是树链剖分+平衡树+二分答案。
可以看我的代码。

第三题:
提交答案
给一个无向图,有些点有数,有些点要填上数,使得所有的边两端的数的差的绝对值的和最小。

这题其实可以线性规划来搞,或者也有网络流(移民站选址?),这样小数据就水过了。
大的数据,可以用各种调整法。
例如:每个点调整成邻居的中位数/平均数。
综合各种乱搞,可以拿到不错的分数。
当然,也有用模拟退火/随机调整/遗传算法那高分的。
  评论这张
 
阅读(1372)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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