题解 P4583 【[FJOI2015]世界树】

一句话题意:求节点数为n的avl树叶子深度之差的最大值是多少 为了方便起见我们深度为这个点到树根路径上点的个数而不是边的个数 如果你仔细看过算法导论的话你会发现习题上有一个题是让你证明为什么深度为$i$的avl至少有$\sum_{p=1}^{i}fib(p)$个节点 其实没什么稀奇的，就是普通的$dp$,$dp(i)$深度为i的avl树的最少节点数目，我们至少会得出这样一个结论就是这个数组是单调的，那么有了这个性质我们就可以列一个dp出来，$dp(i)=dp(i-1)+dp(i-2)+1$接下来运用van能的数学归纳法♂我们就可以证明这个数组就是fibonacci数组的前缀和数组了 接下来我们会发现这样构造出来的树同样是叶子深度差最大的树，为了证明这点我们只需要证明这样构造出来的树最小深度同样最小就行了，你同样可以使用van能的数学归纳法♂来证明这个命题，你还可以列一个dp式子$mindep(i)=min(mindep(i-1)+mindep(i-2))+1$来解决这个问题 然后我们大力猜想一波对于一个有n个节点的avl树来讲如果$dp(i) \leq n \le dp(i+1)-1$，那么n的答案应该和有$dp(i)$个节点的树是一样的 那这么说来我们只需要将询问读进来排个序,写个暴力压位高精吧每个dp的值刷出来就行啦？ 然后你高兴的写了这个程序交上去发现wa的连姥姥都不认…… 为什么呢？ 试试6？显然答案是0因为此时唯一合法的avl树是一个完全二叉树,不过你的程序会输出1 情况开始变得辣手…… 于是你把6特判了之后交了上去发现ac了本题…… 为什么呢？ 因为6是唯一的反例 证明的话你考虑如果不动最浅的叶子的话我们最多可以向这棵avl树中插入几个节点，通过打表发现只有6的时候我们必须在最浅的叶子中插入节点，其他的时候我们总是有多余的空隙插入多余的节点 所以这题就是写个压位高精就没了…… 下面的代码有锅，会在数字后18位为000000000000000006的且这个数字不是6的时候wa掉，想改也很简单，不过这里懒得改了 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std;const int S=560;const int N=1e4+10;typedef unsigned long long ull; const ull mod=1e18;const int biot=18; struct bigi//压位高精 { ull s[S+5]; inline ull& operator [](const int& x){return s[x];} friend bigi operator +(bigi a,bigi b) { bigi c;ull sum=0; for(int i=1;i<=S;i++)sum+=a[i]+b[i],c[i]=sum%mod,sum/=mod;return c; } friend bool operator <(bigi a,bigi b) {for(int i=S;i>=1;i--)if(a[i]!=b[i])return a[i]<b[i];return false;} friend bool operator <=(bigi a,bigi b) {for(int i=S;i>=1;i--)if(a[i]!=b[i])return a[i]<b[i];return true;} inline void inc(){for(int i=1;i<=S;i++){s[i]++;if(s[i]!=mod)break;else s[i]=0;}} }ret[3],qr[55];int T;char mde[N];int mdp[3];int ans[55]; int main() { scanf("%d",&T); for(int i=1;i<=1e4;i++)mde[i]='0';//排序 for(int i=1;i<=T;i++)//压位 { scanf("%s",mde+1);int len=1;for(;mde[len+1]!='\0';len++); reverse(mde+1,mde+len+1);mde[len+1]='0'; for(int s=1,t=1;s<=len;s+=biot,t++) { ull ret=0; for(int j=s+biot-1;j>=s;j--) ret*=10,ret+=mde[j]-'0';qr[i][t]=ret; } for(int j=1;j<=len;j++)mde[j]='0';qr[i][S+1]=i; }sort(qr+1,qr+T+1);//排序 int tp=1;ret[1][1]=1;mdp[0]=mdp[1]=1; for(int i=1;i<=T;i++) { while(ret[tp%3]<=qr[i]) { tp++;ret[tp%3]=ret[(tp-1)%3]+ret[(tp-2)%3];ret[tp%3].inc(); mdp[tp%3]=min(mdp[(tp-1)%3],mdp[(tp-2)%3])+1; }ans[qr[i][S+1]]=(tp-1)-mdp[(tp-1)%3]; if(qr[i][1]==6)ans[qr[i][S+1]]=0; }for(int i=1;i<=T;i++)printf("%d\n",ans[i]);return 0;//拜拜程序~ } ```