本文主要是介绍POJ 2886 Who Gets the Most Candies?（单点更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：模拟约瑟夫环。有N（1<=N<=500000）个孩子围成一圈，他们被顺时针编号为 1 到 N。每个小孩手中有一个卡片，上面有一个非 0 的数字，游戏从第 K 个小孩开始，他告诉其他小孩他卡片上的数字并离开这个圈，他卡片上的数字 A 表明了下一个离开的小孩，如果 A 是大于 0 的，则下个离开的是左手边第 A 个，如果是小于 0 的，则是右手边的第 A 个小孩。游戏将直到所有小孩都离开，在游戏中，第 p 个离开的小孩将得到 F(p) 个糖果，F(p) 是 p 的约数的个数，问谁将得到最多的糖果。输出最幸运的小孩的名字和他可以得到的糖果。
F(p)的值直接暴力跑一下就可以了。
因为A的值可能很大，所以会用到模运算，这就要求下标是从0开始，但是小孩的编号从1开始，所以在更新的时候，要考虑两者的转换，即从编号下标从1开始的，转换成编号下标从0开始的，再转换回去，这也是为什么在A小于零的时候，先是减1，最后再加1的原因。在大于零的时候，K再减1，使得移动的步数保持不变，不然移动的步数就要减去1。仔细想想就能知道。
回答下面一楼的问题：
/*代码风格更新后*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int N=500005;struct node
{int lft,rht,valu;int mid(){return MID(lft,rht);}
};int y[N],step[N],n,K;
char name[N][15];void calu()
{int limit=(int)sqrt(N*1.0);for(int i=1;i<=limit;i++){for(int j=i+1;j*i<=N;j++)y[i*j]+=2;y[i*i]++;}
}
struct Segtree
{node tree[N*4];void build(int lft,int rht,int ind){tree[ind].lft=lft; tree[ind].rht=rht;tree[ind].valu=0;if(lft!=rht){int mid=tree[ind].mid();build(lft,mid,LL(ind));build(mid+1,rht,RR(ind));} }int query(int valu,int ind){int lft=tree[ind].lft,rht=tree[ind].rht;if(lft==rht){tree[ind].valu=0;return lft;}else {int pos,num=tree[LL(ind)].valu;;if(num>=valu) pos=query(valu,LL(ind));else pos=query(valu-num,RR(ind));tree[ind].valu=tree[LL(ind)].valu+tree[RR(ind)].valu;return pos;}}
}seg;int main()
{calu();while(scanf("%d%d",&n,&K)!=EOF){seg.build(0,n-1,1);for(int i=0;i<n;i++) scanf("%s%d",name[i],&step[i]);int ind=-1,imax=0,&num=seg.tree[1].valu;for(int i=1;i<=n;i++){int pos=seg.query(K,1);if(y[i]>imax) imax=y[i],ind=pos;if(step[pos]>0){K=((K-2+num)%num+step[pos])%num+1;}else {K=((K-1+step[pos])%num+num)%num+1;}}printf("%s %d\n",name[ind],imax);}
}/*代码风格更新前*/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=500005;
int a[N];
struct child
{char str[15];int num;
}per[N];
struct node
{int left,right,cnt;int dis(){return right-left+1;}int mid(){return left+(right-left)/2;}
};
struct Segtree
{node tree[N*4];void build(int left,int right,int r){tree[r].left=left; tree[r].right=right;tree[r].cnt=tree[r].dis();if(left<right){int mid=tree[r].mid();build(left,mid,r*2);build(mid+1,right,r*2+1);}}int updata(int pos,int r){tree[r].cnt--;if(tree[r].left==tree[r].right){return tree[r].left;}else{if(pos>tree[r*2].cnt) return updata(pos-tree[r*2].cnt,r*2+1);else return updata(pos,r*2);}}
}seg;
void deal()
{for(int i=1;i<sqrt((double)N);i++){for(int j=i+1;j*i<N;j++){a[i*j]+=2;}a[i*i]++;}
}
int main()
{int n,k;deal();while(scanf("%d%d",&n,&k)!=EOF){for(int i=0;i<n;i++) scanf("%s %d",per[i].str,&per[i].num);seg.build(0,n-1,1);int p_cnt=1,pos,&num=seg.tree[1].cnt,imax=0,ans;while(num){pos=seg.updata(k,1);if(imax<a[p_cnt]) {ans=pos;imax=a[p_cnt];}p_cnt++;if(num==0) break;if(per[pos].num>0){k=(k-2+per[pos].num)%num+1;}else{k=((k-1+per[pos].num)%num+num)%num+1;}}printf("%s %d\n",per[ans].str,imax);}return 0;
}
这篇关于POJ 2886 Who Gets the Most Candies?（单点更新）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
