[原创]POJ 2886 Who Gets the Most Candies? [线段树-单点更新]【数据结构】

2016-11-15 20:30:35 Tabris_ 阅读数：198

博客爬取于2020-06-14 22:42:35
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53176786

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

------------------------------------.
Who Gets the Most Candies?
Time Limit: 5000MS Memory Limit: 131072K
Total Submissions: 13899 Accepted: 4397
Case Time Limit: 2000MS
Description

N children are sitting in a circle to play a game.

The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (−A)-th child to the right.

The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?

Input

There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 500,000) and K (1 ≤ K ≤ N) on the first line. The next N lines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.
Output

Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.

Sample Input

4 2
Tom 2
Jack 4
Mary -1
Sam 1
Sample Output

Sam 3
Source

POJ Monthly–2006.07.30, Sempr
-----------------------------------.

题目大意：
就是有n个人围城一圈，第一次第k个人离开，接下来离开的人是上一次离开的人的位置相对手上的数字相对位置上的人。
如果正的就是顺时针，负的就是逆时针

然后输出的是获得糖果最多的人。这个人获得的糖果数是f（p）f（p）第p个离开。f（p）f（p）是p的因子个数。

解题思路：
首先对于n个人来说，获得的最多的糖果个数和其是第几个离开的已经是确定的了,就是一个反素数，这个只要打个表就行了。

那么我们的任务就只剩下了 怎么找第K个离开的人。

每一次我们能够知道的离开的编号是哪一个，所以我们只要一个个的找就行了，但是直接暴力的找的话复杂度是O(n2)O(n^2),n又很大 一定会超时。

所以我们采取的就是用线段树维护的方法，每次离开的人放到树上，然后找下一个人，这样的话复杂度就降到了O(nlogn)O(nlogn).

维护的方法就是在树上的节点存储这个区间中剩下的没有离开的人的个数,然后更新的时候减掉1就行了.

这个与POJ2828一样 详情戳这里

附本题代码
----------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <math.h>

# define abs(x)          (((x)>0)?(x):-(x))
# define lalal           puts("*********")
# define Rep(a,b,c)      for(int a=(b);a<=(c);a++)
# define Req(a,b,c)      for(int a=(b);a>=(c);a--)
# define Rop(a,b,c)      for(int a=(b);a<(c);a++)
# define s1(a)           scanf("%d",&a)
typedef long long int LL;
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 9901;
/**************************************/

int RPrime[]= //反素数
{
    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,
    554400
};

int fact[]= //反素数约数个数
{
    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,216
};

const int N = 500000+10;
# define ll  (rt<<1)
# define rr  (rt<<1|1)
# define mid (tree[rt].m())
struct node
{
    int l,r;
    int val;
    int flag;
    int m()
    {
        return (r+l)>>1;
    }
} tree[N<<2];
char a[N][12];
int b[N];

void build(int rt,int l,int r)
{
    tree[rt].l=l,tree[rt].r=r;
    tree[rt].flag=r-l+1;
    if(l==r) return ;
    build(ll,l,mid);
    build(rr,mid+1,r);
}

int luck;
void update(int rt,int pos)
{
    tree[rt].flag--;
    if(tree[rt].l==tree[rt].r){luck=tree[rt].l;return;}
    if(pos<=tree[ll].flag)update(ll,pos);
    else    update(rr,pos-tree[ll].flag);
    return ;
}

int main()
{
    //freopen("out.txt","w",stdout);
    int n,k;
    while(~s1(n))
    {
        s1(k);
        build(1,1,n);
        Rep(i,1,n)
        {
            scanf("%s",a[i]);
            s1(b[i]);
        }

        int P=0;
        for(int i=0; RPrime[i]<=n; i++)P=i;
        int mod;
        luck=0;
        b[luck]=0;
        Rep(i,1,RPrime[P])
        {
            mod=tree[1].flag;
            if(b[luck]>0) k=((k+b[luck]-2)%mod+mod)%mod+1;
            else          k=((k+b[luck]-1)%mod+mod)%mod+1;
            update(1,k);
        }
        printf("%s %d\n",a[luck],fact[P]);
    }
    return 0;
}