首页 > 代码库 > POJ 2886 Who Gets the Most Candies? 反素数+线段树

POJ 2886 Who Gets the Most Candies? 反素数+线段树

2024-07-11 22:19:53   218人阅读

题意：变形的约瑟夫环模型，每个人有一个数字a，从第K个人开始出列，如果数字是正的，就往后数a个人出列，如果书负数，就往反方向数。

然后用最基本的线段树处理约瑟夫环的方法即可

但是题目要求的是第x个出列的人的名字，x为1-N中约数最多的数中的最小的那个。这里需要求反素数，即不大于N约数最多的。

写起来比较多，容易写错，一开始连素数打表都写作了QAQ

#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <cstdlib>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <stack>#include <climits>using namespace std;typedef long long LL;const int maxn = 500000 + 5;int sum[maxn << 2];//线段树#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,rvoid build(int rt,int l,int r) {    if(l == r) sum[rt] = 1;    else {        int mid = (l + r) >> 1;        build(lson); build(rson);        sum[rt] = sum[rt<<1] + sum[rt<<1|1];    }}void update(int rt,int l,int r,int tar,int x) {    if(l == r) sum[rt] = x;    else {        int mid = (l + r) >> 1;        if(tar <= mid) update(lson,tar,x);        else update(rson,tar,x);        sum[rt] = sum[rt<<1] + sum[rt<<1|1];    }}int query(int rt,int l,int r,int v) {    if(l == r) return l;    else {        int mid = (l + r) >> 1,lc = rt<<1,rc = lc + 1;        if(sum[lc] >= v) return query(lson,v);        else return query(rson,v - sum[lc]);    }}//反素数生成int prime[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};int minv[maxn],times[40];void dfs(LL arr,int nowcnt,int nowt,LL lim) {    if(arr > lim) return;    //cout << arr << " " << nowcnt << " " << nowt << " " << lim << endl;    minv[nowcnt] = min(minv[nowcnt],(int)arr);    for(int i = 1;nowt == 0 || i <= times[nowt - 1];i++) {        arr *= prime[nowt];        if(arr > lim) break;        nowcnt = nowcnt / i * (i + 1);        times[nowt] = i;        dfs(arr,nowcnt,nowt + 1,lim);    }}char name[maxn][20];int k[maxn],N,K;void solve() {    int nowpos = K,ans,ansv,nowk,pos = K;    build(1,1,N);    for(int i = 1;i <= N;i++)        if(minv[i] <= N) ansv = i;    for(int i = 1;i <= N;i++) {        pos = query(1,1,N,nowpos);        update(1,1,N,pos,0);  //      printf("%d:%s out in %d\n",pos,name[pos],i);        nowk = k[pos];        if(i == minv[ansv]) {            ans = pos; break;        }        if(nowk > 0) nowpos = ((nowpos + nowk - 2) % (N - i) + (N - i)) % (N - i) + 1;        else nowpos = ((nowpos + nowk - 1) % (N - i) + (N - i)) % (N - i) + 1;    }    printf("%s %d\n",name[ans],ansv);}void setfile() {    freopen("in.txt","r",stdin);    freopen("a.txt","w",stdout);}int main() {//    setfile();    for(int i = 1;i <= maxn;i++) minv[i] = INT_MAX;    dfs(1,1,0,maxn);    while(scanf("%d%d",&N,&K) != EOF) {        for(int i = 1;i <= N;i++) scanf("%s%d",name[i],&k[i]);        solve();    }    return 0;}

　　


联系
我们