題目：Who Gets the Most Candies?

?

題意：

1.n個人進行Joseph游戲，游戲共p輪（p為 思路：用相對坐標(biāo)來處理，例如這一輪出局的是p，下一個要+m，則p出局時p+1就變成了p（因為是相對

坐標(biāo)），則下一個人應(yīng)該是p+m-1,再注意循環(huán)和m的正負(fù)的處理，不要忘了取模。

2.求解原始序號時維護一棵線段樹，類似上一題插隊的方法建樹，每個節(jié)點為該區(qū)間段的人數(shù)，則要在(l,r)區(qū)間踢出第p個人，若p小于等于tree[rt<<1]，則在

左半?yún)^(qū)間踢第p個人，否則在右半?yún)^(qū)間踢第(p-tree[rt<<1])個人（tree[rt<<1]為左半?yún)^(qū)間人數(shù)），如此向下處理，直到踢出該人。

#include <stdio.h>#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1#define N 500010int tree[N<<2];const int antiprime[]={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,665280};const 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,100,108,120,128,144,160,168,180,192,200,216,224};struct child {char name[15];int val; }c[N];void Build(int l,int r,int rt) {tree[rt]=r-l+1;if(l==r)return;int m=(l+r)>>1;Build(lson);Build(rson); }int Update(int p,int l,int r,int rt) {tree[rt]--;if(l==r)return r;int m=(l+r)>>1;if(p<=tree[rt<<1])return Update(p,lson);return Update(p-tree[rt<<1],rson); }int main() {int i,n,k,&mod=tree[1];while(~scanf("%d%d",&n,&k)){for(i=1;i<=n;i++)scanf("%s%d",c[i].name,&c[i].val);Build(1,n,1);int cnt=0;while(cnt<35 && antiprime[cnt]<=n)cnt++;cnt--;int pos=0;c[pos].val=0;for(i=0;i<antiprime[cnt];i++){if(c[pos].val>0)k=((k+c[pos].val-2)%mod+mod)%mod+1;elsek=((k+c[pos].val-1)%mod+mod)%mod+1;pos=Update(k,1,n,1);}printf("%s %d\n",c[pos].name,factorNum[cnt]);}return 0;}

總結(jié)

以上是生活随笔為你收集整理的POJ2886线段树 Joseph游戏(单点更新)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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