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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

NOI2011Day1题目大意及算法  

2011-08-08 15:53:45|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一题:
有一个类似fibonacci的数列,不过公式变成了:
f[i]={         f[i-1]+f[i-2]-1     如果f[i-1]+f[i-2]模K余1,且i>=3
                f[i-1]+f[i-2]        否则
      }
它起始是:f[1]=1,f[2]=1
你要回答f[N]模P余数
N<=10^18
P<=10^9
K<=10^6
算法:
注意到这样一个事实:对任意的K<=10^6,fib数列前2000000项中必然有一个K的倍数。
于是,我们发现这个数列很快就会出现模K余0.
我们可以想办法从一个模K余0的项在O(1)的时间里查询出下一个模K余0的数出现的位置。
注意到:
a 0 a a 2a 3a ...
实质是重新开始,不过乘以了a。我们可以利用扩展Euler计算每一个由0开始的段何时终止(要么存在一个b使a*b%K=1,要么重新回到0)
很快(追踪O(K)个0),我们就能够观察到数列的循环。
这样,我们找到了的减1的位置的规律,使用矩阵乘法来完成模P余数的计算。

第二题:
横摆着一排N个长方形,相邻的两个必然有紧密相邻的边。
问在这个图形内部从一个点到另一个点的最短路。
N<=2000
算法:
通过扫描来计算一个矩形的顶点连直线能够到达哪些其他的顶点。
Dijkstra。O(N^2)
另一个来自cqx的O(N)算法:
观察最短路树,我们实质上只维护它的两条链,这两条链一个在上面,一个在下面,挡住了其他点向右走的路。
通过两个栈来维护两条凸线以及他们在最短路树上的LCA。线性扫描即可。

第三题:
有一个字典树。每次询问(从根到一个节点x的路径所代表的字符串)在(根到另一个节点y的路径所代表的字符串)中出现了多少次。
N<=10^5,Q<=10^5
算法(来自另一个省的同学):
建立AC自动机,把失败指针视作父子关系。
通过dfs序,把问题转化成询问一个点到根(在原先字典树中)的路径上有多少个数在给定区间里。
使用dfs+平衡树/树状数组来计算。

大家成绩普遍很高。
我的分数虽然是北京第一,但总体来说处在中等偏上一点(20名以里一小点吧)。
北京其他同学发挥基本正常,产生很多块金牌是有希望的。
  评论这张
 
阅读(1884)| 评论(16)
推荐 转载

历史上的今天

评论

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

页脚

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