「fjWC2015」世界树
「题目描述」
奥丁杀死的巨人伊米尔后，从伊米尔的尸体上生长出来一株巨大的梣树，它是整个宇宙的核心，被称为世界之树，这个巨木的枝干构成了整个世界，它被神秘的奥术力量所守护。
奥丁发现，世界树的每个节点至多有两棵子树，其蕴含的奥术力量是子树奥术力量的最大值+1，如果一个节点没有子树，其奥术力量为1，这些节点被称为“源”。
世界树在悠长的岁月里形成了奇妙的魔法平衡，具体来说，它的左子树与右子树的奥术力量的差的绝对值不会超过1。若一个节点只有一棵子树（不妨设为左子树），则右子树的奥术力量视为0。
现在奥丁想知道，在n个节点的世界树中，最高和最低的两个“源”的深度差最大是多少？
「输入格式」
第一行一个整数T，表示数据组数。
以下T行，每行一个整数n表示世界树的节点数。
「输出格式」
T行，每行一个整数表示任意两个“源”的奥术力量的差的最大值。
「样例输入」
2
5
12345
「样例输出」
1
9
「数据范围」
对于10%的数据，n <= 10
对于40%的数据，n <= 2^31 – 1
对于60%的数据，n <= 10^100
对于80%的数据，n <= 10^1000
对于100%的数据，1 <= n <= 10^10000, T <= 50
前八个点时间限制2000ms，最后两个数据点时间限制6000ms
题解
搬运coolinging神犇学长的题解
为了求在包含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 * 高精度运算)
实际上边矩乘边二分说的是二进制拆分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define rad 100000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char tmp[10005]; string ch; int bin[20]; struct data{ int l;ll v[2005]; data(){ l=1; memset(v,0,sizeof(v)); } inline ll& operator[](int x){ return v[x]; } friend data operator+(data a,data b){ if(a.l<b.l)swap(a,b); for(int i=1;i<=b.l;i++) a[i]+=b[i]; for(int i=1;i<=a.l;i++) if(a[i]>=rad) { if(i==a.l)a.l++; a[i+1]+=a[i]/rad; a[i]%=rad; } return a; } friend data operator*(data a,data b){ data c; for(int i=1;i<=a.l;i++) for(int j=1;j<=b.l;j++) c[i+j-1]+=a[i]*b[j]; for(int i=1;i<=a.l+b.l;i++) { if(c[i]>=rad) { c[i+1]+=c[i]/rad; c[i]%=rad; } if(c.v[i])c.l=i; } return c; } friend void print(data a){ for(int i=a.l;i;i--)printf("%.8I64d",a[i]); puts(""); } friend bool operator<=(data a,data b){ if(a.l<b.l)return 1; else if(a.l>b.l)return 0; for(int i=a.l;i;i--) if(a[i]<b[i])return 1; else if(a[i]>b[i])return 0; return 1; } }n; data get(string ch){ data a; int t=ch.length();ch=" "+ch; a.l=(t-1)/8+1; for(int i=1;i<=a.l;i++) { ll k=1; for(int j=1;j<=8;j++) { if(t-8*(i-1)-j+1>=1) a[i]+=k*(ch[t-8*(i-1)-j+1]-'0'); k*=10; } } return a; } struct M{ data v[2][2]; friend M operator*(M a,M b){ M c; for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) c.v[i][j]=c.v[i][j]+(a.v[i][k]*b.v[k][j]); return c; } }t[20],a; int main() { //freopen("world.in","r",stdin); //freopen("world.out","w",stdout); bin[0]=1;for(int i=1;i<=15;i++)bin[i]=bin[i-1]<<1; t[0].v[0][0]=t[0].v[0][1]=t[0].v[1][0]=get("1"); for(int i=1;i<=15;i++) t[i]=t[i-1]*t[i-1]; int T=read(); while(T--) { a.v[0][0]=a.v[1][1]=get("1"); a.v[1][0]=a.v[0][1]=get("0"); scanf("%s",tmp); int len=strlen(tmp); ch=""; for(int i=0;i<len;i++)ch+=tmp[i]; if(len==1&&ch[0]=='6'){puts("0");continue;} n=get(ch)+get("1"); int now=0; for(int i=15;i>=0;i--) { M tmp=a*t[i]; if(tmp.v[0][0]<=n) a=tmp,now+=bin[i]; } printf("%d\n",(now-2)/2); } return 0; } |
OI 课件=>
