http://poj.org/problem?id=2886

恩，分糖果，快樂(lè)的童年啊！

題目意思大概n個(gè)小孩圍成一個(gè)圈，每個(gè)小孩手里有張卡片，記錄著一個(gè)數(shù)字。開(kāi)始從第k個(gè)孩子，該孩子離開(kāi)圈子，然后告訴別人他手里的數(shù)字，接下來(lái)便從位于該孩子的位置加上孩子手中的數(shù)字的孩子開(kāi)始，直到所有的孩子都離開(kāi)了圈子，游戲便結(jié)束。每個(gè)跳出圈子的孩子都能得到一定的糖果，數(shù)目是他跳出圈子的順序數(shù)的因子數(shù)之和。 例如第6個(gè)跳出的孩子能得到(1,2,3,6)四個(gè)糖果。

?

這個(gè)游戲，其實(shí)和猴子選大王是一樣的！只要注意好求解相對(duì)位置即可，所謂相對(duì)位置，例如：

a,b,c,d四個(gè)人，a對(duì)應(yīng)1，b對(duì)應(yīng)2，c對(duì)應(yīng)3，d對(duì)應(yīng)4.但是當(dāng)b不在以后，c便相對(duì)的為2，d也相對(duì)的為3.

然后利用線段樹(shù)，輕松解決！

?

這里關(guān)鍵是學(xué)習(xí)了一下反素?cái)?shù)表。

反素?cái)?shù)：

對(duì)于任何正整數(shù)x，其約數(shù)的個(gè)數(shù)記做g(x)。例如g(1)=1，g(6)=4。
如果某個(gè)正整數(shù)x滿足：對(duì)于任意i(0 < i < x)，都有g(shù)(i) < g(x)，則稱(chēng)x為反素?cái)?shù)。

而反素?cái)?shù)表就是對(duì)應(yīng)上面反素?cái)?shù)所建立的一張表，這張表好處多多，例如給你一個(gè)n，你便可以輕松的找出1~~n范圍內(nèi)，誰(shuí)的因子數(shù)之和最多！

給出個(gè)簡(jiǎn)單的打表方法

View Code

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int dp[600001];

int main()
{
int i,j;
    freopen("D:\\in.txt","w",stdout);
    memset(dp,0,sizeof(dp));
for(i=1;i<=500000;i++)
    {
for(j=1;j<=500000;j++)
        {
if(i*j<=600000)
                dp[i*j]++;
        }
    }
int max=0;
for(i=2;i<=600000;i++)
    {
if(dp[i]>max)
        {
            max=dp[i];
            cout<<i<<",";
        }
    }
    cout<<endl<<endl;
    max=0;
for(i=2;i<=600000;i++)
    {
if(dp[i]>max)
        {
            max=dp[i];
            cout<<dp[i]<<",";
        }
    }
return 0;
}

?

這是一個(gè)效率很低的程序，只是為了這道題打表而已。

?

接下來(lái)模擬猴子選大王就是了，當(dāng)給定一個(gè)n的時(shí)候，先找出1~~n內(nèi)因子數(shù)之和最大的那個(gè)數(shù)，因子數(shù)之和便是candy的答案，假設(shè)那個(gè)數(shù)是m，那么模擬到第m個(gè)人的時(shí)候，那個(gè)人便也是答案！

?

View Code

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int max_turn[40]={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 max_candy[40]={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};

struct child
{
char name[10];
int pos;
};

child num[500001];
int n,k,pos;

struct node
{
int l;
int r;
int left;
};

node tree[2500000];

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

void updata(int i,int w)
{
if(tree[i].l==tree[i].r)
    {
        tree[i].left--;
        pos=tree[i].l; //記錄目前的實(shí)際位置
        return;
    }
if(tree[2*i].left>=w)
        updata(2*i,w);
else if(tree[2*i+1].left>=w-tree[2*i].left)
        updata(2*i+1,w-tree[2*i].left);
    tree[i].left=tree[2*i].left+tree[2*i+1].left;
}

int main()
{
int i,turn,&mod=tree[1].left,candy;
    freopen("D:\\in.txt","r",stdin);
while(scanf("%d%d",&n,&k)==2)
    {
        build(1,1,n);
for(i=1;i<=n;i++)
        {
            scanf("%s %d",num[i].name,&num[i].pos);    
        }
        i=0;
while(max_turn[i]<=n) //尋找最大的n'
            i++;
        i--;
        candy=max_candy[i];  //記錄最多的糖果
        turn=max_turn[i]; //第max_turn[i]出來(lái)的人將得到最多的糖果
        pos=0;
        num[0].pos=0;
for(i=0;i<turn;i++)
        {
if(num[pos].pos>0) //求解相對(duì)剩余位置
            {
                k=((k+num[pos].pos-1)%mod+mod)%mod;
if(k==0)
                    k=mod;
            }
else
            {
                k=((k+num[pos].pos)%mod+mod)%mod;
if(k==0)
                    k=mod;
            }
            updata(1,k);
        }
        printf("%s %d\n",num[pos].name,candy);
    }
return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/ka200812/archive/2011/11/14/2248914.html

總結(jié)

以上是生活随笔為你收集整理的线段树专辑——pku 2886 Who Gets the Most Candies?的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。