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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

ZJOI2012《波浪》《灾难》题解  

2012-05-27 16:21:20|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我出题的特征很多人都已经发现了,那就是以“小强和阿米巴是好朋友”开头。

具体的题面可以去lydsy.com/JudgeOnline看看。
我说一下做法:

《灾难》
【题意简述】

给一个有向无环图,问每个节点删掉之后会导致多少个点不可达。

【算法描述】

有这样一个事实:
生物之间的灭绝的结构形成了一个树,树上的一个节点的灭绝会且仅会导致以它为根的子树的灭绝。我们管这个树叫“灭绝树”。
对于生产者,我们给它添加一个假想的食物:太阳。
这样,“灭绝树”就形成了一个以太阳为根的树。

下面说明如何通过增量法把灭绝树建出来,同时也是对灭绝树的存在性的证明。

首先,把食物网按从猎物到捕食者的顺序拓扑排序。
之后,依次考虑每个生物i.我们已经构建好了排序在i之前的生物组成的“灭绝树”了。
假设i的食物有x[0]~x[k](x[0]~x[k]在拓扑排序中比i靠前)。
很显然,只有x[0]~x[k]在树上的公共祖先的灭绝会导致i灭绝,否则i一定可以找到能让它活下来的食物。
                 
            ...  
         /       
        /        
      LCA        
      /|\        
    _/ ||        
   /   | \       
  O    |  \      
 / \    \  \     
x   x    x  x    
                 
       i         
                 
                 
于是,我们可以把i挂在x[0]~x[k]的最近公共祖先下面。

处理完所有的生物,我们得到的树就是整个图的灭绝树了。
一旦得到灭绝树,每个生物的灾难值就可以通过以它为根的子树的大小减1来计算.

【复杂度分析】

拓扑排序的时间复杂度是O(|E|)的。
一共有|E|次LCA的查询,和|V|次添加边的操作。
我们使用某种支持快速查询LCA、添加点的数据结构(例如动态树)。
这样,总的时间复杂度是O(|E|log|V|)。


《波浪》
题目意思可以用IO格式来概括。

【输入格式】

输入的第一行包含三个整数NMQ,分别表示排列的长度,波动强度,输出位数。

【输出格式】

输出一个数,表示一个随机的1~N的排列的相邻项差的绝对值的和不小于M的概率,四舍五入保留小数点后Q位。

一个典型的dp题。
我们把1~N依次插入到序列里。
每插入一个数,我们就要决定他左右两边的数是比他大还是比他小还是没有。
之后,计算好当前的所有数对绝对值和的贡献。
状态是:已经插入了i个数,留了j个位置可以供插空,两端的情况是k,当前的和是s的情况下,有多少种方法。
复杂度很高,但是是多项式的。
具体转移方法可以看程序:
  评论这张
 
阅读(5560)| 评论(19)
推荐 转载

历史上的今天

评论

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

页脚

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