poj 2886 Who Gets the Most Candies?

题意:约瑟夫环游戏，第 p个出来的人有F（p）（求p的反素数）个糖果，问糖果最多的人的名字和它有多少个糖果，如果最多的有几个人，输出最先出来的那个人

解题思路：这个题目有很多细节要注意，首先，顺时针的话大的是在他的左边，然后就是要注意它的步数是否是大于人数的，利用线段树的基本性质搜索它的位置就行了

解题代码：

  1 #include <stdlib.h>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #define MAXN 500005
  5 int n, k ;
  6 int a[MAXN];
  7 struct node
  8 {
  9     int left ,right ,mid ;
 10     int num ;
 11 }tree[MAXN * 4];
 12 int L(int c)
 13 {
 14     return 2 * c;
 15 }
 16 int R(int c)
 17 {
 18     return 2 * c + 1;
 19 }
 20 void build(int c, int p , int v)
 21 {
 22     tree[c].left = p ;
 23     tree[c].right = v;
 24     tree[c].mid = (p+v)/2;
 25     tree[c].num = (v-p+1);
 26     if(p == v )
 27     {
 28         return;
 29     }
 30     build(L(c),p,tree[c].mid);
 31     build(R(c),tree[c].mid + 1, v);
 32 }
 33 int tsum = 0  ;
 34 void getsum(int c, int p ,int v )
 35 {
 36     if(p <= tree[c].left && v >= tree[c].right)
 37     {
 38         tsum += tree[c].num;
 39         return;
 40     }
 41     if(v <= tree[c].mid) getsum(L(c),p,v);
 42     else if(p > tree[c].mid ) getsum (R(c),p,v);
 43     else
 44     {
 45         getsum(L(c),p,tree[c].mid);
 46         getsum(R(c),tree[c].mid+1, v );
 47     }
 48 }
 49 int ok =0 ;
 50 void update(int c, int p)
 51 {   tree[c].num -- ;
 52     if(tree[c].left == tree[c].right)
 53     {
 54         ok = tree[c].left;
 55         return;
 56     }
 57     if(tree[L(c)].num >= p ) update(L(c),p);
 58     else update(R(c),p - tree[L(c)].num);
 59 }
 60 char str[MAXN][13];
 61 int RPrime[]={//反素数
 62     1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,
 63 1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,
 64 45360,50400,55440,83160,110880,166320,221760,277200,
 65 332640,498960,554400,665280
 66 };
 67 
 68 int fact[]={//反素数约数个数
 69     1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,
 70 90,96,100,108,120,128,144,160,168,180,192,200,216,224
 71 };
 72 
 73 int main()
 74 {
 75 
 76     while(scanf("%d %d",&n,&k) != EOF)
 77     {
 78         int P = 0 ;
 79         for(int i= 0; RPrime[i]<= n;i++)P=i;
 80         for(int i = 1;i <= n;i ++)
 81         {
 82             scanf("%s %d",str[i],&a[i]);
 83         }
 84         build(1,1,n);
 85         update(1,k);
 86         int temp = a[k];
 87         int t = 1 ;
 88         int temps = k ;
 89         if(t < RPrime[P])
 90         while(tree[1].num != 0)
 91         {
 92             t ++ ;
 93             if(temp < 0 )
 94             {
 95                 tsum = 0 ;
 96                 getsum(1,1,temps);
 97                 temp = (-temp)%(tree[1].num);
 98                 if(temp == 0 )
 99                     temp = tree[1].num;
100                 if(tsum >= temp)
101                 {
102                     update(1,tsum-temp + 1);
103                 }
104                 else
105                 {
106                     update(1,tree[1].num - (temp - tsum) + 1 );
107                 }
108             }
109             else
110             {
111                 tsum = 0 ;
112                 getsum(1,temps,n);
113                 temp = temp%(tree[1].num);
114                 if(temp == 0 )
115                     temp = tree[1].num;
116                 if(tsum >= temp)
117                 {
118                     update(1,tree[1].num - (tsum - temp));
119                 }
120                 else
121                 {
122                     update(1,temp - tsum);
123                 }
124             }
125             temps = ok;
126             temp = a[ok];
127         //    printf("%d
",ok);
128 
129             if(t >= RPrime[P])
130                 break;
131 
132         }
133         printf("%s %d
",str[ok],fact[P]);
134     }
135     return 0 ;
136 }

View Code

ps：poj上排名第一的既然是3xian，应该是用图灵树撸过的，无限orz！

没有梦想，何谈远方