> #include <stdio.h>
> #include <string.h>
> #define MAXN 500100
> struct People
> {
>    char name[12];
>    int shift;
> }arr[MAXN];
> int ant[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,
>        15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500100};
>        
> int ans[]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,
>         160,168,180,192,200,0};       
>        
> int mat[MAXN*3];
> int tree[MAXN*3];
> 
> void init(int left,int right,int v)
> {
>    tree[v]=right-left+1;
>    if(left!=right)
>    {
>       init(left,(left+right)/2,2*v);
>       init((left+right)/2+1,right,2*v+1);
>    }
>    else mat[v]=left;
> }
> int main()
> {
>    int n,k,f,t,left,right,v,count,i;
>    while(scanf("%d%d",&n,&k)!=EOF)
>    {
>       for(i=1;i<=n;i++) scanf("%s%d",arr[i].name,&arr[i].shift);
>       memset(mat,0,sizeof(mat));
>       init(1,n,1);
>       for(t=0;t<36;t++) if(n<ant[t]) break;
>       t--;
>       for(i=1;i<ant[t];i++)
>       {
>          left=1,right=n,v=1;
>          while(left!=right)
>          {
>             tree[v]--;
>             if(k>(left+right)/2) 
>             {
>                left=(left+right)/2+1;
>                v=v*2+1;
>             }
>             else 
>             {
>                right=(left+right)/2;
>                v=v*2;
>             }
>          }
>          //if(i==3) printf("%d--\n",v);
>          tree[v]--;
>          if(arr[k].shift>0)
>          {
>             f=v/2;
>             count=arr[k].shift;
>             //if(i==3) printf("%d--\n",count);
>             while(f)
>             {
>                if(v==f*2&&tree[f*2+1]>=count) 
>                {
>                   v=f*2+1;
>                   break;
>                }
>                if(v==f*2) count-=tree[f*2+1];
>                v=f;
>                f=v/2;
>             }
>             //if(i==3) printf("%d--%d--%d\n",v,f,count);
>             if(!f) count%=tree[1];
>             if(!count) count=tree[1];
>             //printf("%d--%d\n",tree[1],count);
>             while(!mat[v])
>             {
>                //printf("%d--\n",v);
>                if(tree[v*2]>=count) v=v*2;
>                else
>                {
>                   count-=tree[v*2];
>                   v=v*2+1;
>                }
>             }
>             //printf("%d-------------\n",v);
>             k=mat[v];
>             //printf("%d----\n",k);
>          }
>          else 
>          {
>             f=v/2;
>             count=-arr[k].shift;
>             while(1)
>             {
>                if(v==f*2+1&&tree[f*2]>=count) 
>                {
>                   v=f*2;
>                   break;
>                }
>                if(v==f*2+1) count-=tree[f*2];
>                v=f;
>                f=v/2;
>             }
>             if(!f) count%=tree[1];
>             if(!count) count=tree[1];
>             while(!mat[v])
>             {
>                if(tree[v*2+1]>=count) v=v*2+1;
>                else
>                {
>                   count-=tree[v*2+1];
>                   v=v*2;
>                }
>             }
>             k=mat[v];
>          }
>       }
>       printf("%s %d\n",arr[k].name,ans[t]);
>    }
>    return 0;
> }

• 什么意思？ (0) nuanran 2006-08-07 20:21:21
  • 递归一下不很好么 (0) frkstyc 2006-08-07 20:22:24
    • 弱问一下，能不能根据子树的left,right确定父亲的left,right,现在搞晕了．．．． (0) nuanran 2006-08-07 20:46:42
      • 呼，终于过了！把一个while(f)写成while(1)了，还以为我找的时候太笨了，不过再问一下为什么C++会RE,G++就过了呢？ (0) nuanran 2006-08-07 21:09:38
    • 还有结点数最多是N几倍呢？ (0) nuanran 2006-08-07 21:15:15