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

A?BC!

¤★&#♂♀§

 
 
 

日志

 
 
关于我
LOFTER精选

NOIP2010 提高组 复赛 第四题 引水入城(flow) 题解  

2010-11-27 09:35:33|  分类: noip |  标签: |举报 |字号 订阅

        一开始看到这道题时,第一反应就是搜索。认真分析题目后发现,对问题的求解并非无规律可循。通过对样例的观察,我猜想:对于第一行的每一个格子,它所能影响到的最后一行的格子会不会是一段区间呢?

        在能满足条件的情况下,答案是肯定的。下面是我对这一问题的证明:

        假设第一行的A格所能影响的最后一行的区间为[l1,r1]和[l2,r2],r1<l2-1,即存在区间[r1+1,l2-1],因为能够满足条件,所以在第一行必然会有一格B会影响[r1+1,l2-1]中的元素,那么A到A影响的区间的路径必然会与B到B影响的区间的路径交叉,水会向下流,那么A也能影响B影响的区间[r1+1,l2-1]。

        所以,第一行中的每个格子,都会影响最后一行的一个区间,如果影响的是不连续的两个区间,那么一定不会满足条件。

        根据这个结论,我们还可以证明:对于第一行中的任意两个格子,一个格子影响的范围不会覆盖另一个格子所影响的范围。(#)

        接下来的问题就是如何确定第一行中的每个格子所影响的区间呢?

NOIP2010 提高组 复赛 第四题 引水入城(flow) 题解 - 渐渐 - A?BC!

         最后一行的高度会如图所示,形成一个个“山峰”,如果第一行的某个格子能都影响山峰,那么该格子一定能影响“整座山”。即,可以先计算出最后一行每个“山峰”影响的区间,再寻找能影响该“山峰”的第一行的格子(BFS),并更新这些格子的区间。当某个“山峰”不能被第一行的格子影响时,便说明不能满足条件,我们便将它记录下来,并将“这座山”去掉山峰,分成两半。

        做完这些处理后,程序主体已经完成了。(这时已经我已经很累了)

        如果不能满足条件,将记录下来的山峰数输出即可;如果能满足条件,用贪心计算出答案即可(贪心的可行性在前面(#)处已证明)。

        我的程序还未到手,大概过几天后能给我了,到时再贴出来。

  评论这张
 
阅读(1614)| 评论(1)
推荐 转载

历史上的今天

最近读者

热度

评论

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

页脚

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