poj 2886 Who Gets the Most Candies?

点击打开poj 2886

思路: 求因子数+单点更新

分析:

1 题目的意思是有n个人构成一个环，刚开始是第k个人先出来。每个人有一个名字和数值A，如果A为正数，那么下一个出去的人是他左边的第A个人，如果是负数那么出去的将是右边的第A个人

2 这么我们要注意一下，因为n个人是围城一圈，那么左边就是顺时针方向，右边就是逆时针方向

3 那么我们就可以来推没一次出去的人的在剩下中是第几个。

假设当前是第k个人出去，并且这个人的值为A，并且剩下有sum个人

A > 0 , 因为这个人出去了，那么后面的人的编号会先减一，那么下一个出去的人就是剩下中的 (k+A-1)%sum，因为我们知道%sum的结果是0～sum-1，但是我们要得到1～sum的结果，因此我们可以这样 ((k+A-1)%sum-1+sum)%sum+1。怎么理解呢，比如x%3，那么结果就是0～2，为了得到结果为1～3，那么我们可以这样(x-1+3)%3+1，括号里面加3怕负数的情况

A < 0 , 因为这个人出去，对前面的人是没有影响的，因此编号就是 ((k+A)%sum+sum-1+sum)%sum+1，根据上面的解释以及怕出现负数的情况，我们多加了sum来抵消

4 我们现在求出了每一次出去的人是剩下人中的第几个，但是我们怎么去求出具体的是哪一个人呢？

这个时候我们就可以利用线段树来维护，线段树的区间维护的是当前这个区间还有多少个孩子，那么我们只要查找前面求出的第几个孩子就可以得到编号

代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-09-13                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mid(x,y) (x+y)>>1

const int N = 11;
const int MAXN = 500010;

int num[MAXN];
int n , k;

struct Person{
    char name[N];
    int val;
};
Person p[MAXN];

struct Node{
    int left;
    int right;
    int sum;
};
Node node[4*MAXN];

// 打出所有的数的因子的个数
void init(){
    int t = sqrt(MAXN);
    for(int i = 1 ; i <= t ; i++){
        num[i] = 1;
        for(int j = 1 ; j <= sqrt(i) ; j++)
            if(i%j == 0)
                num[i]++;
        if(i > 1) num[i*i] = num[i]+1;
    }
    /*
    int i , j , limit;  
    limit = (int)sqrt(MAXN*1.0);  
    for(i = 1 ; i <= limit ; i++){  
        for(j = i+1 ; j*i < MAXN ; j++)  
            num[i*j] += 2;  
        num[i*i]++;  
    }
    */
}

void push_up(int pos){
    node[pos].sum = node[lson(pos)].sum+node[rson(pos)].sum;
}

void buildTree(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    node[pos].sum = right-left+1;
    if(left == right)
        return;
    int mid = mid(left , right);
    buildTree(left , mid , lson(pos));
    buildTree(mid+1 , right , rson(pos));
}

void update(int id , int pos){
    if(node[pos].left == node[pos].right){
        node[pos].sum--;
        return;
    }
    int mid = mid(node[pos].left , node[pos].right);
    if(id <= mid)
        update(id , lson(pos));
    else
        update(id , rson(pos));
    push_up(pos);
}

int query(int x , int pos){
    if(node[pos].left == node[pos].right)
        return node[pos].left;
    if(node[lson(pos)].sum >= x)
        return query(x , lson(pos));
    else
        return query(x-node[lson(pos)].sum , rson(pos));
}


void solve(){
    buildTree(1 , n , 1);
    int ans = 0;
    int nameId;
    int id = k;
    for(int i = 1 ; i <= n ; i++){
        update(id , 1);
        int sum = node[1].sum;
        if(ans < num[i]){
            ans = num[i];
            nameId = id;
        }
        if(sum){
           int A = p[id].val;
           if(A > 0)
               k = ((k+A-1)%sum-1+sum)%sum+1;
           else
               k = ((k+A)%sum+sum-1+sum)%sum+1;
        }
        id = query(k , 1);
    }
    printf("%s %d\n" , p[nameId].name , ans);
}

int main(){
    init();
    while(scanf("%d%d" , &n , &k) != EOF){
        for(int i = 1 ; i <= n ; i++)
            scanf("%s%d" , p[i].name , &p[i].val);
        solve();
    }
    return 0;
}