本文主要是介绍poj2886 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树题目，思路不难，关键是F(p)，很难想清楚是神马，表示看了别人的题意解析才知道神马意思。反素数这玩意果断决定打表了，以后比赛随时带着这玩意得了。另外注意的是，反素数的因子个数不是连续变化的，有可能依次增加好几个因子，这点特别注意下。
其他就是依次剔除人了，知道人物当前位置和当前人物长度可轻易推出下次出列的人物位置，依次将人物出列直到答案的值。
代码：
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>using namespace std;#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
const int N=555555;
int sum[N*4];
string name[N*4];
int card[N*4];
int sss[100]={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,665280,720720};
int b[37]={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,1314521};
int n,K,c,n1;void pushup(int rt)
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}void build(int l,int r,int rt)
{if (l==r){sum[rt]=1;cin>>name[rt];scanf("%d",&card[rt]);return ;}delf;build(lson);build(rson);pushup(rt);return ;
}void update(int k,int l,int r,int rt)
{//cout<<l<<" "<<r<<" "<<c<<" "<<n1<<endl;if (l==r){sum[rt]=0;n1--;c--;//cout<<name[rt]<<endl;if (c==0)cout<<name[rt]<<" ";else{if (card[rt]>0)K=K+card[rt]-1;elseK=K+card[rt];while (K<0)K=K+n1;K=K%n1;if (K==0)K=n1;}return ;}delf;if (sum[rt<<1]>=k)update(k,lson);elseupdate(k-sum[rt<<1],rson);pushup(rt);return ;
}int main()
{while (scanf("%d%d",&n,&K)!=EOF){build(1,n,1);c=0;while (sss[c]<=n)c++;int ans=b[c-1];c=sss[c-1];//cout<<c<<endl;n1=n;while (c>0){update(K,1,n,1);//cout<<"AAAAA "<<K<<endl;}cout<<ans<<endl;}
}这篇关于poj2886 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
