738
POJ 2886 單點更新
題意：n個小孩圍一圈，他們手上卡片的數字代表下一個要出去的孩子，第K個孩子出去得到糖的數量是k的約數，輸出得到糖最多的那個孩子的姓名和糖數。
首先要求反素數，也就是約數最多的，打表就行。然後線段樹節點存放這個區間有多少個孩子還沒走。然後模擬這個過程求出第P個孩子。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 500005
int RPrime[]= //反素數
{
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 fact[]= //反素數約數個數
{
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 node[maxn<<2];
struct child
{
char name[15];
int num;
} data[maxn];
void build(int rt,int l,int r)
{
node[rt]=r-l+1;
if(l==r)
{
node[rt]=1;
return;
}
int mid=(r+l)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
int updata(int rt,int l,int r,int k)
{
node[rt]--;
if(l==r)
{
return l;
}
int mid=(l+r)>>1;
if(k<=node[rt<<1])
return updata(rt<<1,l,mid,k);
else
return updata(rt<<1|1,mid+1,r,k-node[rt<<1]);
}
int main()
{
int n,k,p;
while(~scanf("%d%d",&n,&k))
{
for(int i=1; i<=n; i++)
scanf("%s%d",data[i].name,&data[i].num);
for(int i=0; RPrime[i]<=n; i++) p=i;
build(1,1,n);
for(int i=1; i<RPrime[p]; i++)
{
int luck=updata(1,1,n,k),mod=node[1];
if(data[luck].num>0)
k=((k+data[luck].num-2)%mod+mod)%mod+1;
else k=((k+data[luck].num-1)%mod+mod)%mod+1;
}
printf("%s %d\n",data[updata(1,1,n,k)].name,fact[p]);
}
return 0;
}
最後更新：2017-04-03 18:52:05