poj2886 - Who Gets the Most Candies? - 线段树+约瑟夫环+反素数

题目连接

思路：

1.首先，我们要求n个数中，因子数个数最多的数，因子数相同则取最小的数。

可见其符合反素数的定义，则用dfs搜索出来该数ans，以及其对应的因子数maxn（在题目中表示第ans个跳出来的孩子，能得到的糖果数最多，为maxn）

筛反素数

2.然后用线段树，维护区间里人的个数，eg，tree[rt]=5，rt对应的区间还有5个人。（k:=每次在剩下的小孩中，第k个小孩跳出去）

tid=update(k,1,n,1)，表示第k个小孩跳出去，返回的tid是跳出去小孩的原始的下标。

3.然后，往前/后数a[tid].num个小孩跳，怎么知道这时对应的小孩，是剩下小孩里第几个呢？

更新k，

if(a[tid].num>0){//nn表示现在有多少人

    k=(k-1+a[tid].num-1)%nn+1;

}

else k=((k-1+a[tid].num)%nn+nn)%nn+1;

往后走，原本第k个小孩已经退出游戏了，现在第k个小孩是原来的第k+1个，所以要先-1，后面的-1是为了防止出现0。

往前走，第1个-1就不用了

代码如下：

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<vector>

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ll long long
using namespace std;
const int N=500005,mod=1e9+7;
const int INF=0x3f3f3f3f;
int n,ans,maxn,tree[N<<2];

struct A{
    char name[15];
    int num;
}a[N+5];
int p[]={0,2,3,5,7,11,13,17,19,23,29,31};
int use[12];

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

void dfs(int id,int now,int tot){
    //id:第几个质因数
    //now:数的大小
    //tot:因子的个数
    if(tot>maxn||(tot==maxn&&now<ans)){
        ans=now;
        maxn=tot;
    }
    use[id]=0;
    while(now*p[id]<=n&&use[id]+1<=use[id-1]){
        use[id]++;
        now*=p[id];
        dfs(id+1,now,tot*(use[id]+1));
    }
}

int update(int k,int l,int r,int rt){//求出更新区间中第k个值，所对应的数组下标为多少;并更新
    tree[rt]--;
    if(l==r){
        return r;
    }
    int m=(l+r)>>1;
    if(tree[rt<<1]>=k){
        return update(k,lson);
    }
    else return update(k-tree[rt<<1],rson);
}


int main(){
    ios::sync_with_stdio(false);
    int k;
    cin>>n>>k;
    use[0]=1<<29;
    dfs(1,1,1);
    for(int i=1;i<=n;i++){
        cin>>a[i].name>>a[i].num;
    }
    build(1,n,1);
    int nn=n,tid;
    for(int i=1;i<=ans;i++){/
        tid=update(k,1,n,1);//tid表示相当更新的值的下标
        nn--;
        if(nn==0)break;
        if(a[tid].num>0){
            k=(k-1+a[tid].num-1)%nn+1;//k表示去掉一些人后，下次更新现有人的第k个人
        }
        else k=((k-1+a[tid].num)%nn+nn)%nn+1;
    }
    cout<<a[tid].name<<" "<<maxn<<endl;
}