POJ 2886 【线段树模拟约瑟夫环】.cpp

题意：

　　一群小孩顺时针坐然后在玩约瑟夫环的游戏..

　　从第k个小孩开始..每个被选中的孩子扔出手中的纸牌..

　　然后按着纸牌上面的数找下一个被选中的小孩..

　　如果牌中的数是正数就顺时针数..

　　如果是负数就逆时针数..

　　其中第 i 个被选中的小孩会得到f( i )颗糖..

　　f( i )表示 i 的正因子个数..

　　要求是找出得到糖最多的孩子个数..

输入：　　

　　n k 表示有n个小孩..从第k个开始

　　接下来 n 行有n个小孩的名字和他手上的牌的编号..

思路：

　　一开始想的是暴力找出这个小孩..

　　但是会很麻烦..

　　然后这里就用到了反素数了..

　　反素数：<http://acm.nenu.edu.cn/us/?p=91>

　　找出f[ j ] > f[ i ] ： f[ j ]为 j 的正因子个数..

　　然后就可以找出n之前正因子最多的那个数即得糖最多的那个小孩编号 ans..

　　再找出这个小孩是谁..

　　用线段树模拟找的过程..感觉跟二分有点像~感觉..

Tips：

　　※ 改的是 rt 是 sum 的..但是输入的per的数据是 l 和 r

　　※ 还有一个让我很纠结的就是根据数的正负向左数还是向右数..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 
 4 const int MAXN = 500010;
 5 
 6 struct P
 7 {
 8     char name[20];
 9     int sum;
10 }per[MAXN];
11 int sum[MAXN<<2];
12 
13 int antiprime[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,
14                  7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,
15                  166320,221760,277200,332640,498960,554400,665280};
16 int factorNum[]={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,
17                  100,108,120,128,144,160,168,180,192,200,216,224};
18 
19 void pushup(int rt)
20 {
21     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
22 }
23 
24 void creat(int l, int r, int rt)
25 {
26     if(l == r) {
27         scanf("%s %d", per[l].name, &per[l].sum);
28         sum[rt] = 1;
29         return;
30     }
31     int mid = (l+r)>>1;
32     creat(l, mid, rt<<1);
33     creat(mid+1, r, rt<<1|1);
34     pushup(rt);
35 
36 }
37 
38 int modify(int k, int l, int r, int rt)
39 {
40     if(l == r) {
41         sum[rt]--;
42         return l;
43     }
44     int mid = (l+r)>>1;
45     int loc;
46     if(k <= sum[rt<<1]) loc = modify(k, l, mid, rt<<1);
47     else loc = modify(k-sum[rt<<1], mid+1, r, rt<<1|1);
48     pushup(rt);
49     return loc;
50 }
51 
52 int main()
53 {
54     int i, j;
55     int n, k;
56     int loc, tmp;
57     int ans;
58     while(scanf("%d %d", &n, &k) != EOF)
59     {
60         creat(1, n, 1);
61 
62         for(i = 0; i < 36; ++i) if(antiprime[i] <= n) ans = i;
63 
64         k = ((k-1)%n+n)%n+1;
65         loc = modify(k, 1, n, 1);
66 
67         for(i = 1; i < antiprime[ans]; ++i) {
68             if(per[loc].sum > 0) k = ((k+per[loc].sum - 2)%sum[1] + sum[1])%sum[1] + 1;
69             else k = ((k+per[loc].sum-1)%sum[1] + sum[1])%sum[1] + 1;
70             loc = modify(k, 1, n, 1);
71         }
72 
73         printf("%s %d\n", per[loc].name, factorNum[ans]);
74     }
75     return 0;
76 }

题目链接：http://poj.org/problem?id=2886