POJ 2886 Who Gets the Most Candies?（反素数+线段树）

点我看题目

题意：n个小盆友从1到n编号按顺时针编号，然后从第k个开始出圈，他出去之后如果他手里的牌是x，如果x是正数，那下一个出圈的左手第x个，如果x是负数，那出圈的是右手第-x个，游戏中第p个离开的孩子得到的糖果是f（p）个，f（p）是p的约数的个数。

思路 : 因为f（p）是p的约数的个数，所以，要用到反素数，反素数的定义及求法。反素数s的约数个数比小于它的数的约数个数都多，最大反素数就是要找到的那个得到糖果最多的人。线段树记录的是还剩多少人未出列。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 506000 ;
char ch[maxn][15] ;
int data[maxn] ;

struct mode
{
    int l,r ;
    int value,sum ;
}tree[maxn * 4] ;
//反素数表
int rev[37] = {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,500001};
//反素数对应的约数个数
int revs[37] = {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,1314521};

void build(int v,int l,int r)
{
    tree[v].l = l ;
    tree[v].r = r ;
    tree[v].value = r-l+1 ;
    if(l == r) return ;
    int mid = (l + r) >> 1 ;
    build(v*2,l,mid) ;
    build(v*2+1,mid+1,r) ;
}

int query(int v,int x)
{
    tree[v].value-- ;
    if(tree[v].l == tree[v].r) return tree[v].l ;
    if(x <= tree[v*2].value)
    return query(v*2,x) ;
    else return query(v*2+1,x-tree[v << 1].value) ;
}
int main()
{
    int n, k;
    while(scanf("%d %d",&n,&k) != EOF)
    {
        int i = 0,maxx = 0,p = 0 ;
        while(rev[i] <= n)
        i++ ;
        p = rev[i-1] ;
        maxx = revs[i-1] ;
        build(1,1,n ) ;
        for(int j = 1 ; j <= n ; j++)
        scanf("%s %d",ch[j],&data[j]) ;
        int yy ;
        for(int i = 0 ; i < p ; i++)
        {
            n -- ;
            yy = query(1,k) ;
            if(n == 0) break ;
            if(data[yy] > 0)
            k = (k-1+data[yy]-1) % n + 1 ;
            else k =( (k-1+data[yy])%n+n) % n+1 ;
        }
        printf("%s %d
",ch[yy],maxx) ;
    }
    return 0;
}

View Code

POJ 2886 Who Gets the Most Candies?（反素数+线段树）

相关推荐