POJ2886线段树 Joseph游戏(单点更新)

题目：Who Gets the Most Candies?

 

题意：

1.n个人进行Joseph游戏，游戏共p轮（p为 思路：用相对坐标来处理，例如这一轮出局的是p，下一个要+m，则p出局时p+1就变成了p（因为是相对

坐标），则下一个人应该是p+m-1,再注意循环和m的正负的处理，不要忘了取模。

2.求解原始序号时维护一棵线段树，类似上一题插队的方法建树，每个节点为该区间段的人数，则要在(l,r)区间踢出第p个人，若p小于等于tree[rt<<1]，则在

左半区间踢第p个人，否则在右半区间踢第(p-tree[rt<<1])个人（tree[rt<<1]为左半区间人数），如此向下处理，直到踢出该人。

#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;}

总结

以上是生活随笔为你收集整理的POJ2886线段树 Joseph游戏(单点更新)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。