JZYZOJ1237 教授的测试 dfs

http://172.20.6.3/Problem_Show.asp?id=1237

 

锻炼搜索的代码能力，不错的题。

开始对dfs到底向下传递什么搞不清楚，需要想一下，noip难度的题还有这种情况，果然还是太蒻。

代码

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<vector>

 using namespace std;

 int n;

 int f[]={};

 int mm[][]={},tot;

 void init(int x,int siz,int xu){

     if(siz==||siz==)return;

     int w=xu,z;

     for(int i=;i<siz;i++){

         if(w>f[i]*f[siz--i])w-=f[i]*f[siz--i];

         else{z=i;break;}

     }

     int zz2=w%f[siz--z];

     int zz1=w/f[siz--z]+;

     if(zz2==){zz2=f[siz--z];zz1-=;}

     if(z!=){mm[x][]=++tot;init(tot,z,zz1);}

     if(siz--z!=){mm[x][]=++tot;init(tot,siz--z,zz2);}

 }

 void put(int x){

     if(mm[x][]){printf("(");put(mm[x][]);printf(")");}

     printf("X");

     if(mm[x][]){printf("(");put(mm[x][]);printf(")");}

 }

 int main(){

     int ma=;

     f[]=;f[]=;

     for(int i=;f[i-]<ma;i++){

         for(int j=;j<=(i-)/;j++){

             f[i]+=f[j]*f[i--j]*;

             if(j==i--j){

                 f[i]-=f[j]*f[i--j];

             }

         }

     }

     while(~scanf("%d",&n)){

         if(n==)break;

         memset(mm,,sizeof(mm));

         tot=;int siz;

         int q=;

         for(int i=;;i++){

             q+=f[i];

             if(n<=q){siz=i;q-=f[i];break;}

         }

         init(,siz,n-q);

         put();

         cout<<endl;

     }

     return ;

 }