http://poj.org/problem?id=2886
恩，分糖果，快乐的童年啊！
题目意思大概n个小孩围成一个圈，每个小孩手里有张卡片，记录着一个数字。开始从第k个孩子，该孩子离开圈子，然后告诉别人他手里的数字，接下来便从位于该孩子的位置加上孩子手中的数字的孩子开始，直到所有的孩子都离开了圈子，游戏便结束。每个跳出圈子的孩子都能得到一定的糖果，数目是他跳出圈子的顺序数的因子数之和。 例如第6个跳出的孩子能得到(1,2,3,6)四个糖果。
这个游戏，其实和猴子选大王是一样的！只要注意好求解相对位置即可，所谓相对位置，例如：
a,b,c,d四个人，a对应1，b对应2，c对应3，d对应4.但是当b不在以后，c便相对的为2，d也相对的为3.
然后利用线段树，轻松解决！
这里关键是学习了一下反素数表。
反素数：
对于任何正整数x，其约数的个数记做g(x)。例如g(1)=1，g(6)=4。
如果某个正整数x满足：对于任意i(0 < i < x)，都有g(i) < g(x)，则称x为反素数。
而反素数表就是对应上面反素数所建立的一张表，这张表好处多多，例如给你一个n，你便可以轻松的找出1~~n范围内，谁的因子数之和最多！
给出个简单的打表方法
View Code #include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int dp[600001];
int main()
{
int i,j;
freopen("D:\\in.txt","w",stdout);
memset(dp,0,sizeof(dp));
for(i=1;i<=500000;i++)
{
for(j=1;j<=500000;j++)
{
if(i*j<=600000)
dp[i*j]++;
}
}
int max=0;
for(i=2;i<=600000;i++)
{
if(dp[i]>max)
{
max=dp[i];
cout<<i<<",";
}
}
cout<<endl<<endl;
max=0;
for(i=2;i<=600000;i++)
{
if(dp[i]>max)
{
max=dp[i];
cout<<dp[i]<<",";
}
}
return 0;
}
这是一个效率很低的程序，只是为了这道题打表而已。
接下来模拟猴子选大王就是了，当给定一个n的时候，先找出1~~n内因子数之和最大的那个数，因子数之和便是candy的答案，假设那个数是m，那么模拟到第m个人的时候，那个人便也是答案！
View Code #include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int max_turn[40]={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 max_candy[40]={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};
struct child
{
char name[10];
int pos;
};
child num[500001];
int n,k,pos;
struct node
{
int l;
int r;
int left;
};
node tree[2500000];
void build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].left=r-l+1;
if(l==r)
return;
int mid=(l+r)/2;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
}
void updata(int i,int w)
{
if(tree[i].l==tree[i].r)
{
tree[i].left--;
pos=tree[i].l; //记录目前的实际位置
return;
}
if(tree[2*i].left>=w)
updata(2*i,w);
else if(tree[2*i+1].left>=w-tree[2*i].left)
updata(2*i+1,w-tree[2*i].left);
tree[i].left=tree[2*i].left+tree[2*i+1].left;
}
int main()
{
int i,turn,&mod=tree[1].left,candy;
freopen("D:\\in.txt","r",stdin);
while(scanf("%d%d",&n,&k)==2)
{
build(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%s %d",num[i].name,&num[i].pos);
}
i=0;
while(max_turn[i]<=n) //寻找最大的n'
i++;
i--;
candy=max_candy[i]; //记录最多的糖果
turn=max_turn[i]; //第max_turn[i]出来的人将得到最多的糖果
pos=0;
num[0].pos=0;
for(i=0;i<turn;i++)
{
if(num[pos].pos>0) //求解相对剩余位置
{
k=((k+num[pos].pos-1)%mod+mod)%mod;
if(k==0)
k=mod;
}
else
{
k=((k+num[pos].pos)%mod+mod)%mod;
if(k==0)
k=mod;
}
updata(1,k);
}
printf("%s %d\n",num[pos].name,candy);
}
return 0;
}
