个人觉得从一个位置下一个位置是关键,然后用树状数组就简单了。
之前举例子推推导公式时只用一个参数,一直凑不出来,后来用两个参数,一个是这列数中原来的位置,另一个是前一个位置的人跳出后,下一个人的前面和自己一共的人数。我用d表示前一个参数,k表示后一个参数。
这一题还学到反素数,真是很有用的东西。
反素数打表就行,然后线段树+二分, 还有我改得最多的main()函数:
int aa[37]= {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,500001};
//所有数可能的因子数(包括1和本身).
int bb[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};
// 与上面每一个数对应,第一个出现因子数是aa数组的数的数
int main()
{
int i,j,g,gg,d,m;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(tree,0,sizeof(tree));
for(i=1;i<=n;i++)
{
add(i,1);
c[i]=0;
}
for(i=1;i<=n;i++)
{
scanf("%s%d",s[i].a,&s[i].num);
}
for(i=0;i<37;i++)
{
if(aa[i]>n)
{
g=aa[i-1];
gg=bb[i-1];
break;
}
}
k = b(k);
add(k,-1);
m = n-1;
c[k]=1;
d=k;
for(j=2;j<=g;j++)
{
if(s[d].num>0)
{
k = ((k-1+s[d].num)%m+m)%m;
}
else
{
k = (((k+s[d].num)%m+m)%m+m)%m;
}
if(k==0)k=m;
m=m-1;
d = b(k);
add(d,-1);
}
printf("%s %d\n",s[d].a,gg);
}
}
分享到:
相关推荐
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
北大POJ1163-The Triangle
poj 3174 Alignment of the Planets.md
poj 4006 Genghis Khan the Conqueror.md
poj 1611 The Suspects 代码 并查集的应用
北大POJ1004-Financial Management 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
POJ3273 Monthly Expense题解 题目分析: 给出N个数,要求你合并连续的数,使其合并在满足不差过M个合并后的集合的时候,不超过M个集合的和的最大值最小。
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
北大POJ2965-The Pilots Brothers' refrigerator 解题报告+AC代码