### 题解 P4583 【[FJOI2015]世界树】

posted on 2018-11-18 20:23:50 | under 题解 |

// 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;//拜拜程序~
}