Poj 2886 Who Gets the Most Candi…
梁丘权
题目描述详见：
http://poj.org/problem?id=2886
本题的解法是：线段树
只是当我们删除元素的时候，我们要去推算下一个元素所在的位置。然后直接通过线段树的查找就可了。
比如节点里面记录的内容是，左子树中还剩下的元素有多少个，如果我们推算出来了下一个要删除的元素的位置(注：不是编号，是删除元素之后的位置)，那么我们通过线段树很快就能查找(线段树求逆序数的思想是一样的)。
详见代码：
#include<stdio.h>
#include<string.h>
#define MAXN 500005
struct node
{
int begin,end,mid;
int num;//标记左树上面还有多少个元素
}st[MAXN<<2];
struct data
{
char name[20];
int va;
}ar[MAXN];
int ans[MAXN],flag[MAXN],num[MAXN];
int n,Max,id,k,sum;
void init()//打表取出F(p)
{
memset(flag,0,sizeof(flag));
int total=0,i,j;
for(i=2;i*i<MAXN;i++)
{
if(flag[i])
continue;
for(j=i;j*i<MAXN;j++)
{
flag[i*j]=1;
}
num[total++]=i;
}
for(;i<MAXN;i++)
{
if(flag[i])
continue;
num[total++]=i;
}
int sum,pre,t;
for(i=2;i<MAXN;i++)
{
ans[i]=1;
pre=1;
t=i;
j=0;
while(j<total && flag[t] && num[j]<=t)//flag[t]是优化
{
while(t%num[j]==0)
{
pre+=1;
t/=num[j];
}
j+=1;
ans[i]*=pre;
pre=1;
}
if(t!=1)
ans[i]*=(pre+1);
}
ans[1]=1;
}
void BuildTree(int index,int begin,int end)
{
st[index].begin=begin;st[index].end=end;
st[index].mid=(begin+end)>>1;
if(begin<end)
{
BuildTree(index<<1,begin,st[index].mid);
BuildTree(index<<1 | 1,st[index].mid+1,end);
st[index].num=st[index].mid-begin+1;
}
else
{
scanf("%s%d",ar[end].name,&ar[end].va);
}
}
void get(int index,int x,int y)//查询并找出该元素左右元素有多少个
{
if(st[index].begin==st[index].end)
{
if(ans[y]>Max)
{
Max=ans[y];
id=st[index].end;
strcpy(ar[0].name,ar[id].name);
}
k=ar[st[index].end].va;
return;
}
if(x<=st[index].num)
{
st[index].num-=1;
get(index<<1,x,y);
}
else
{
x-=st[index].num;
sum+=st[index].num;
get(index<<1 | 1,x,y);
}
}
void make()
{
Max=0;
BuildTree(1,1,n);//按编号建立线段树
int t=n,T=0,Left,Right;
while(t--)
{
T+=1;
sum=0;
get(1,k,T);
Left=sum;//找出删除元素之后左右个有多少个元素
Right=t-sum;
if(t==0)
break;
if(k>0)
{
k-=1;
k%=t;
k+=1;
if(k>Right)
{
k-=Right;
}
else
{
k+=Left;
}
}
else
{
k*=-1;
k-=1;
k%=t;
k+=1;
if(k<=Left)
{
k=Left-k;
k+=1;
}
else
{
k=k-Left;
k=Right-k;
k+=Left;
k+=1;
}
}
}
printf("%s %d\n",ar[0].name,Max);
}
int main()
{
init();
while(scanf("%d%d",&n,&k)==2)
{
make();
}
return 0;
}
跑出来的时间是3000+ms,找F(p)那如果优化一点的话，时间效率应该更好。
类似资料：