首页 > 代码库 > (中等) POJ 2886 Who Gets the Most Candies? , 反素数+线段树。
(中等) POJ 2886 Who Gets the Most Candies? , 反素数+线段树。
Description
N children are sitting in a circle to play a game.
The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (−A)-th child to the right.
The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?
题意大致等同于约瑟夫环的问题，一次出来一个，然后出来x个人，其中x表示约数个数最多的数中最小的那个。
做这个题时还不知道什么是反素数，用最笨的方法 (用了3s+时间) 打出了表，直接复制上的。然后就是构建线段树了，这个的线段树不难构建，就是记录区间内还没出去的人的个数。然后更新的话是标记某个点为出去了，并且返回这个点的位置，作为下一次计数的起点。询问的话就是某个区间的没出去的个数。
反素数的话也在学习中，推荐ACdreamer的文章： http://blog.csdn.net/ACdreamers/article/details/25049767
代码如下：（注：写的比较乱，水平有限。）
#include<iostream>#include<cstdio>using namespace std;const int remMax[36][2]={ {1,1},{2,2},{4,3},{6,4},{12,6}, {24,8},{36,9},{48,10},{60,12}, {120,16},{180,18},{240,20},{360,24}, {720,30},{840,32},{1260,36},{1680,40}, {2520,48},{5040,60},{7560,64},{10080,72}, {15120,80},{20160,84},{25200,90},{27720,96}, {45360,100},{50400,108},{55440,120},{83160,128}, {110880,144},{166320,160},{221760,168},{277200,180}, {332640,192},{498960,200},{500001,200}};int N,K;char name[500005][14];int number[500005];int BIT[500005*4];int findM(int x){ for(int i=0;i<35;++i) if(remMax[i][0]<=x&&remMax[i+1][0]>x) return i;}void pushUP(int po){ BIT[po]=BIT[po*2]+BIT[po*2+1];}void build_tree(int L,int R,int po){ BIT[po]=(R-L+1); if(R==L) return; int M=(L+R)/2; build_tree(L,M,po*2); build_tree(M+1,R,po*2+1);}int query(int ql,int qr,int L,int R,int po){ if(ql>qr) return 0; if(ql<=L&&qr>=R) return BIT[po]; int M=(L+R)/2; int temp=0; if(ql<=M) temp+=query(ql,qr,L,M,po*2); if(qr>M) temp+=query(ql,qr,M+1,R,po*2+1); return temp;}int update(int un,int L,int R,int po){ --BIT[po]; if(L==R) return L; int M=(L+R)/2; if(BIT[po*2]>=un) return update(un,L,M,po*2); else return update(un-BIT[po*2],M+1,R,po*2+1);}int main(){ int temp,temp1; int n,las; int times,fp; while(~scanf("%d %d",&N,&K)) { for(int i=1;i<=N;++i) scanf("%s %d",name[i],&number[i]); build_tree(1,N,1); temp=findM(N); times=remMax[temp][0]; fp=remMax[temp][1]; las=0; for(int i=1;i<=times;++i) { if(K>0) { K%=(N-i+1); if(K==0) K=N-i+1; } else { K%=(N-i+1); if(K==0) K=1; else K=(N-i+2)+K; } temp1=query(las+1,N,1,N,1); if(temp1>=K) K=(N-i+1)-(temp1-K); else K=(K-temp1); temp1=update(K,1,N,1); las=temp1; K=number[las]; } printf("%s %d\n",name[las],fp); } return 0;}
(中等) POJ 2886 Who Gets the Most Candies? , 反素数+线段树。