线段树单点更新+反素数 poj-2886-Who Gets the Most Candies-白红宇

线段树单点更新+反素数 poj-2886-Who Gets the Most Candies

阅读量：4516 次

发布时间：2019-06-08

本文共 2808 字，大约阅读时间需要 9 分钟。

题目链接：

题目意思：

编号为1-n的n个人逆时针围成一圈玩游戏，每个人有一个非零的数的卡片，开始从第k个人开始，一次出圈，当第i个人出圈时，如果他的卡片上的数正数p，则他左边的第p个人下个出圈，如果他卡片上的数是负数p,则他右边的第p个人下个出圈。当第i个人出圈时，他获奖励是F(i),F(i)为i的正约数的个数。求获得的最大的奖励是哪个人，及奖励数。

解题思路：

1、反素数的应用。设F(i)为i的正约数个数，若对任意的x<i,有F(x)<F(i),则i为反素数。找出不超过n的第一个最大的反素数即可。

打印反素数代码：

#include
    
     using namespace std;__int64 bestnum;__int64 bestsum;__int64 n;__int64 prime[10]={2,3,5,7,11,13,17,19,23};__int64 limit[10];void creatLimit(__int64 n){memset(limit,0,sizeof(limit));__int64 i,rn;for(i=0;i<=8;i++){   rn=n;   while(rn>prime[i])   {    limit[i]++;    rn/=prime[i];   }}}void creatRPrime(__int64 num,__int64 k,__int64 sum,__int64 limit) //num:数 sum: 因子数{__int64 i,p;if(num>n)return;if(sum>bestsum){   bestsum=sum;   bestnum=num;}else{   if(sum==bestsum && num
     
      8)   return;p=1;for(i=1;i<=limit;i++){   p*=prime[k];   creatRPrime(num*p,k+1,sum*(i+1),i);}}__int64 log2(__int64 n)   //求大于等于log2（n）的最小整数{__int64 i = 0;__int64 p = 1;while(p

2、用一颗线段树维护原始区间内剩下的人的个数，从而找到顺序出圈的人的原始序号。注意借用前面的人在上一区间的标号位置，这点很关键。

关键：上一原始位置与下一顺序位置的关系。

详见代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #define eps 1e-6#define INF (1<<30)#define PI acos(-1.0)using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define maxn 510000int sum[maxn*4];/*freopen("data.in","r",stdin);freopen("data.out","w",stdout);*/struct Inf{ char name[30]; int value;}inf[maxn];void build(int l,int r,int rt){ sum[rt]=r-l+1; if(l==r) return ; int m=(l+r)>>1; build(lson); build(rson); return ;}int update(int target,int l,int r,int rt){ sum[rt]--; if(l==r) return l; int m=(l+r)>>1; if(target<=sum[rt<<1]) return update(target,lson); return update(target-sum[rt<<1],rson);}int main(){ 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}; int factors[]={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}; //一共36个 int n,k,&mm=sum[1]; //用引用，当人数改变时，mm也改变 while(scanf("%d%d",&n,&k)!=EOF) { //getchar(); build(1,n,1); for(int i=1;i<=n;i++) scanf("%s%d",inf[i].name,&inf[i].value); int cnt=0; while(antiprime[cnt]<=n) //找到不超过n的最大的反素数 cnt++; cnt--; int pos=0; inf[pos].value=0; //构建第一个人的情况 for(int i=1;i<=antiprime[cnt];i++) //一步一步找出顺序出圈的人，直到第antiprime[cnt]个人为止 { if(inf[pos].value>0) k=((k+inf[pos].value-2)%mm+mm)%mm+1; //这样可以取到第m个数，不然用-的话为零 else k=((k+inf[pos].value-1)%mm+mm)%mm+1; pos=update(k,1,n,1); } // printf("pos:%d\n",pos); printf("%s %d\n",inf[pos].name,factors[cnt]); } return 0;}

转载于:https://www.cnblogs.com/jiangu66/archive/2013/04/05/3000340.html

你可能感兴趣的文章