題意:
n個小孩站一圈,每個小孩拿一個數字,從第k個孩子開始出局,然後下一個出局的孩子是剛剛出局的孩子之前或之後第v個(剛剛出局的孩子的數字是+v則之後v個,-v則之前v個),這樣所有孩子終將出局,第p個出局的孩子得f(p)分,f(p)定義為p的因子個數。求分數最高的孩子。
分析:
設順時針為正方向,關鍵是模擬出每次出局的孩子是剩下的孩子中的正方向的第幾個,設當前要出局的是第k個,然後要求出第k個小孩的下標(pos)以便下一次計算下一個出局的孩子是第幾個,這些步驟可用線段樹維護。
代碼:
//poj 2886 //sep9 #includeusing namespace std; const int maxN=500010; int n,ids; int ans[maxN]; struct Node { int v; char name[16]; }child[maxN]; struct seg_tree { int l,r,sum; }T[maxN*4]; void build(int l,int r,int k) { T[k].l=l; T[k].r=r; T[k].sum=r-l+1; if(l==r) return ; int mid=(l+r)>>1; build(l,mid,2*k); build(mid+1,r,2*k+1); } void ini() { memset(ans,0,sizeof(ans)); for(int i=1;i<=n;++i){ ++ans[i]; for(int j=2*i;j<=n;j+=i) ++ans[j]; } ids=1; for(int i=2;i<=n;++i) if(ans[i]>ans[ids]) ids=i; } int update(int k,int x) { --T[x].sum; if(T[x].l==T[x].r) return T[x].l; if(T[2*x].sum>=k) return update(k,2*x); else return update(k-T[2*x].sum,2*x+1); } int main() { int i,k,mod; while(scanf("%d%d",&n,&k)==2){ ini(); for(int i=1;i<=n;++i) scanf("%s%d",child[i].name,&child[i].v); build(1,n,1); mod=T[1].sum; int pos=0; child[0].v=0; n=ids; while(n--){ if(child[pos].v>0) k=((k+child[pos].v-2)%mod+mod)%mod+1; else k=((k+child[pos].v-1)%mod+mod)%mod+1; pos=update(k,1); mod=T[1].sum; } printf("%s %d\n",child[pos].name,ans[ids]); } }