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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

一道动态树好题  

2011-06-26 15:43:53|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我造了一个动态树好题,欢迎各位鉴赏!

有N个未知数x[1..n]和N个等式组成的同余方程组:
x[i]=k[i]*x[p[i]]+b[i] mod 10007
其中,k[i],b[i],x[i]∈[0,10007)∩Z
你要应付Q个事务,每个是两种情况之一:
一.询问当前x[a]的解
A a
无解输出-1
多解输出-2
否则输出x[a]
二.修改一个等式
C a k[a] p[a] b[a]

输入格式:
N
下面N行,每行三个整数k[i] p[i] b[i]
Q
下面Q行,每行一个事务,格式见题目描述
输出格式:
对每个询问,输出一行一个整数。

对100%的数据,1≤N≤30000,0≤Q≤100000,时限2秒,其中询问事务约占总数的80%

样例输入:
5
2 2 1
2 3 2
2 4 3
2 5 4
2 3 5
5
A 1
A 2
C 5 3 1 1
A 4
A 5
样例输出:
4276
7141
4256
2126

这个嘛,当然是用动态树来搞了!具体实现请自己思考思考吧。
话说经过实际测试,纯随机数据的暴力的时间复杂度约为O(Qsqrt(N))
那么怎么把暴力卡掉呢?当然要构造出特别长的环。这个怎么方便地构造呢?
我想的方法:p[i]=(i+1+rand()%10)%N+1,呵呵,这样环就特别长了。
我写的一个可以AC的程序长3131B,基本上当成NOI级别的题目挺适合的。



详细的解题过程可以到这个地方去找

经过众多同学鉴定,上面网址贴出的代码是bug多多的。。。请大家关注评论。
  评论这张
 
阅读(2582)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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