N 个小孩围成一圈,他们被顺时针编号为 1 到 N。每个小孩手中有一个卡片,上面有一个非 0 的数字,游戏从第 K 个小孩开始,他告诉其他小孩他卡片上的数字并离开这个圈,他卡片上的数字 A 表明了下一个离开的小孩,如果 A 是大于 0 的,则下个离开的是左手边第 A 个,如果是小于 0 的,则是右手边的第 -A 个小孩。游戏将直到所有小孩都离开,在游戏中,第 p 个离开的小孩将得到 F(p) 个糖果,F(p) 是 p 的约数的个数,问谁将得到最多的糖果。输出最幸运的小孩的名字和他可以得到的糖果。
//以上的翻译是从网上找的
首先呢,第P个小孩将得到P的约数个糖果,这就要引入一个数学名词,反素数,反素数的性质就是,比他小的数的约数个数都没他多,那么我们只要在1到n的范围内找到最大的反素数就能知道最多的糖果数,这个其实用反证法就能证明,假设p是1到n内的最大反素数,那么,如果在p到n内还有数的约数比p多,那么显然p就不能算是最大的反素数了,所以我们就先把50万以内的反素数提前打表,他们的约数也提前打好表,这样的话,就不用所有人都出来后才得出最终结果了。
假设p是1到n内最大的反素数,我们只需模拟p次这个出队过程了,然后有一个需要注意的地方是,下一个人的位置怎么求,这里面有一种是相对位置,还有一种是最初位置,很显然,由于数据量太大,不能通过简单的模拟来实现最初位置和相对位置的转化,这里面,能直接求出来的是相对位置,假设一个人的位置是k,手上卡片的数字是+m,那么下一个人的位置应该是p+m,但是由于他的出队,这个相对位置就要减1了,是p+m-1,但是如果一个人的卡片是-m,此时他的退出就对下一个人的相对位置没有影响了,因为下一个人的位置应该是p-m,在这个人之前,就没有影响了。然后需要注意的是可能会出现负数和0,这就要适当的处理一下了。
然后就是相对位置与最初位置的转换,这里用到了线段树,线段树所附加的信息是该区间还有多少人,每踢掉一个人,区间值变化一次,然后就相当于一个动态的队列了,中间踢掉某个人,整个序列的长度减1,每个人的位置发生了变化,然后再踢相对位置为p的人,只要从头数到第p个人,踢掉就行了。线段树的话,我们先从叶子节点看,踢掉一个人,就相当于这个叶子节点的值就变成0了,然后从1到n,数叶子节点为1的个数,到p的时候把踢掉该位置的人就行了,这样就好理解点了,然后根据点更新到段就能实现快速的插入了。
分享到:
相关推荐
北大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代码