【POJ】2886 Who Gets the Most Candies?

  1 #include<cstdio>
  2 #define MAXN 500010
  3 int n,k,ans,cnt;
  4 int prime[]={2,3,5,7,11,13,17};
  5 struct node
  6 {
  7     char name[12];
  8     int val;
  9 };
 10 node p[MAXN];
 11 int tree[MAXN<<2];
 12 void AntiPrime(int res,int count,int index,int limit)
 13 {
 14     if(res<=n)
 15     {
 16         if(count>cnt)
 17         {
 18             cnt=count;
 19             ans=res;
 20         }
 21         else if(count==cnt&&res<ans)
 22             ans=res;
 23         int i,temp;
 24         for(i=temp=1;i<=limit;i++)
 25         {
 26             temp*=prime[index];
 27             if(temp*res>n)
 28                 break;
 29             else
 30                 AntiPrime(temp*res,count*(i+1),index+1,i);
 31         }
 32     }
 33 }
 34 inline void PushUp(int rt)
 35 {
 36     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 37 }
 38 void Build(int L,int R,int rt)
 39 {
 40     if(L==R)
 41         tree[rt]=1;
 42     else
 43     {
 44         int mid=(L+R)>>1;
 45         Build(L,mid,rt<<1);
 46         Build(mid+1,R,rt<<1|1);
 47         PushUp(rt);
 48     }
 49 }
 50 int Update(int x,int L,int R,int rt)
 51 {
 52     if(L==R)
 53     {
 54         tree[rt]=0;
 55         return L;
 56     }
 57     int mid=(L+R)>>1,res;
 58     if(tree[rt<<1]>=x)
 59         res=Update(x,L,mid,rt<<1);
 60     else
 61         res=Update(x-tree[rt<<1],mid+1,R,rt<<1|1);
 62     PushUp(rt);
 63     return res;
 64 }
 65 int Query(int x,int y,int L,int R,int rt)
 66 {
 67     if(x<=L&&R<=y)
 68         return tree[rt];
 69     int mid=(L+R)>>1,res=0;
 70     if(x<=mid)
 71         res+=Query(x,y,L,mid,rt<<1);
 72     if(y>mid)
 73         res+=Query(x,y,mid+1,R,rt<<1|1);
 74     return res;
 75 }
 76 int main()
 77 {
 78     int i,mov;
 79     while(~scanf("%d%d",&n,&k))
 80     {
 81         for(ans=cnt=i=1;i<=n;i++)
 82             scanf(" %s%d",p[i].name,&p[i].val);
 83         AntiPrime(1,1,0,19);
 84         Build(1,n,1);
 85         k=Update(k,1,n,1);
 86         for(i=1;i<ans;i++)
 87         {
 88             mov=Query(1,k,1,n,1);
 89             if(p[k].val>0)
 90                 mov+=p[k].val;
 91             else
 92                 mov+=p[k].val+1;
 93             mov%=tree[1];
 94             if(!mov)
 95                 mov=tree[1];
 96             else if(mov<0)
 97                 mov+=tree[1];
 98             k=Update(mov,1,n,1);
 99         }
100         printf("%s %d\n",p[k].name,cnt);
101     }
102     return 0;
103 }
新博客：www.zhixiangli.com