首页 > 代码库 > POJ 2886 Who Gets the Most Candies?

POJ 2886 Who Gets the Most Candies?

2024-07-14 09:42:59   229人阅读

思路：

对于 k 位置的 孩子，他的 数字是 +num 那么因为他自己本身是要被踢走的，所以相对位置 为k= k+num-1

如果数字是 -num，那么按正着数就没影响，k=k-num。线段树存储当前区间共有多少个人，每一次找到第k （前面有k-1个）个孩子，经过的区间都要 -1，然后记录被踢走的孩子编号

对于第几个出去是最优可以预处理，网上看到了反素数，反素数 是  如果一个数  x  所有   y<x的   y的因子都小于x则称x为反素数，很明显就是小于n的最大的反素数就是我们要的答案。反素数可以预处理打表。

 

 

#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include <iostream>#define N 500050#define L(x) (x<<1)#define R(x) (x<<1|1)#define debug(x) printf(#x"= %d\n",x);using namespace std;struct node{    char s[12];    int va;}s[N];int cprim[] = {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 fac[] = {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};int sum[N*4];void build(int l,int r,int i){    sum[i]=r-l+1;    if(l!=r)    {        int mid=(l+r)>>1;        build(l,mid,L(i));        build(mid+1,r,R(i));    }}int update(int l,int r,int p,int i){    sum[i]--;    if(l==r)        return l;    int mid=(l+r)>>1;    if(p<=sum[L(i)])        return update(l,mid,p,L(i));    else return update(mid+1,r,p-sum[L(i)],R(i));}int main() {    int n,k;    while(scanf("%d%d",&n,&k)!=EOF)    {        for(int i=1;i<=n;++i)            scanf(" %s %d",s[i].s,&s[i].va);        build(1,n,1);        s[0].va=0;        int now=0;        while(cprim[now]<=n)now++;        now--;        int pre=0;        for(int i=1;i<=cprim[now];++i)        {            if(s[pre].va>0)            {                k=(k+s[pre].va-1)%sum[1];                if(k<=0)k+=sum[1];            }else            {                k=(k+s[pre].va)%sum[1];                if(k<=0)k+=sum[1];            }//            debug(k);            pre=update(1,n,k,1);        }        printf("%s %d\n",s[pre].s,fac[now]);    }    return 0;}

 

 

 


联系
我们