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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4135][FJOI2015]世界树  

2015-06-20 16:52:20|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4135: [FJOI2015]世界树

Time Limit: 15 Sec  Memory Limit: 32 MB
Submit: 16  Solved: 9
[Submit][Status][Discuss]

Description

奥丁杀死的巨人伊米尔后,从伊米尔的尸体上生长出来一株巨大的梣树,它是整个宇宙的核心,被称为世界之树,这个巨木的枝干构成了整个世界,它被神秘的奥术力量所守护。
奥丁发现,世界树的每个节点至多有两棵子树,其蕴含的奥术力量是子树奥术力量的最大值+1,如果一个节点没有子树,其奥术力量为1,这些节点被称为“源”。
世界树在悠长的岁月里形成了奇妙的魔法平衡,具体来说,它的左子树与右子树的奥术力量的差的绝对值不会超过1。若一个节点只有一棵子树(不妨设为左子树),则右子树的奥术力量视为0。
现在奥丁想知道,在n个节点的世界树中,最高和最低的两个“源”(即叶子节点)的深度差最大是多少?

Input

第一行一个整数T,表示数据组数。
以下T行,每行一个整数n表示世界树的节点数。

Output

T行,每行一个整数表示任意两个“源”的奥术力量的差的最大值。

Sample Input

2 5 12345

Sample Output

1 9

HINT

对于100%的数据,1 <= n <= 10^10000, T <= 50

Solution

考察要点:递推证明(数学归纳法)、高精度、矩阵乘法、二分


解题报告:


为了求在包含n个节点的世界树中,最高与最低的叶节点之间的深度差的最大值,考虑固定最低的叶节点的深度为h(h也即树的高度),转而去求最高的叶节点的深度的最小值。

 

以下结论可通过数学归纳法或递推证明得到:(定义空树的高度为-1)

高度为h的世界树,至少包含S(h) = fib(h+3) – 1个节点。

在高度为h的世界树中,任一叶节点的深度均不小于[h/2](上取整)。

 

以下结论可通过构造法证明得出:

存在高度为h的世界树,它的某个叶节点的深度为[h/2](上取整)

当n大于10时,n个节点的世界树的最高与最低的叶节点的深度差不小于n-1个节点的世界树的最高与最低的叶节点的深度差,即本题满足答案单调性(实际上仅n=6时不满足单调性)。

 

故本题转化为判断n处在哪两个Fibonacci数之间,更准确地说是找到最大的h,满足fib(h+3) – 1 <= n,本题答案即为[h/2](下取整)

 

对于40%的数据,n <= 2^31 – 1。

直接递推Fibonacci数列即可求出答案。

对于60%的数据,n <= 10^100。

使用高精度即可。

对于80%的数据,n <= 10^1000。

线性递推会超时,使用二分答案与矩阵乘法快速幂快速求解Fibonacci。

时间复杂度:O(T * log^2n * 高精度运算)

对于100%的数据,n <= 10^10000。

边矩阵乘法边进行二分。

时间复杂度:O(T * logn * 高精度运算)

Code

/**************************************************************
    Problem: 4135
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:6936 ms
    Memory:1812 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
const int mod=100000000,length=8;
char st[20010];
struct B{int len;long long s[1300];}c,one,zero,x;
#define rg register
void getB(rg B&a){
    a=zero,a.len=1;gets(st);
    rg int i=0,l=0,ff=1;
    for(;st[l];l++);
    for(l--;~l;l--){
        a.s[a.len]+=ff*(st[l]-'0'),ff*=10,i++;
        if(i%length==0)a.len++,ff=1;
    }
    if(a.s[a.len]==0)a.len--;
}
B operator+(const B&a,const B&b){
    c=zero,c.len=max(a.len,b.len);
    for(rg int i=1;i<=c.len;i++){
        c.s[i]+=a.s[i]+b.s[i];
        if(c.s[i]>=mod)c.s[i]-=mod,c.s[i+1]++;
    }
    if(c.s[c.len+1])c.len++;
    return c;
}
B operator*(const B&a,const B&b){
    c=zero,c.len=a.len+b.len;
    for(rg int i=1;i<=a.len;i++)
    for(rg int j=1;j<=b.len;j++)c.s[i+j-1]+=a.s[i]*b.s[j];
    c.len=a.len+b.len+1;
    for(rg int i=1;i<=c.len;i++)
    if(c.s[i]>=mod)c.s[i+1]+=c.s[i]/mod,c.s[i]%=mod;
    while(c.s[c.len]==0&&c.len>=1)c.len--;
    return c;
}
bool operator<=(const B&a,const B&b){
    if(a.len!=b.len)return a.len<b.len;
    for(rg int i=a.len;i>=1;i--)
    if(a.s[i]!=b.s[i])return a.s[i]<b.s[i];
    return 1;
}
struct M{B m[2][2];}I,pw[20],ans,tmp;
M operator*(const M&a,const M&b){M c;
    for(rg int i=0;i<2;i++)
    for(rg int j=0;j<2;j++)
    c.m[i][j]=a.m[i][0]*b.m[0][j]+a.m[i][1]*b.m[1][j];
    return c;
}
int t,i,tot,final;
int main(){
    one.len=one.s[1]=zero.len=1;
    I.m[0][0]=I.m[1][1]=one,I.m[1][0]=I.m[0][1]=zero;
    pw[0].m[0][0]=pw[0].m[1][0]=pw[0].m[0][1]=one,pw[0].m[1][1]=zero;
    for(i=1;i<=15;i++)pw[i]=pw[i-1]*pw[i-1];
    for(scanf("%d\n",&t),tot=0;t--;){
        getB(x),ans=I,final=0;
        if(x.len==1&&x.s[1]==6){
            puts("0");
            continue;
        }
        x=x+one;
        for(i=15;~i;i--){
            tmp=ans*pw[i];
            if(tmp.m[0][0]<=x)ans=tmp,final+=(1<<i);
        }
        final=final/2-1;printf("%d\n",final);
    }
}

  评论这张
 
阅读(356)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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