poj 2886 Who Gets the Most Candies? (线段树模拟加强版约瑟夫问题+反素数)

poj 2886 题目链接

题意:n个人围成一圈,每个人身上由一个数,可正可负。从第k个人开始出圈,如果第k个人身上的数是X,X>0,就左边第x个没有出圈的人出圈,否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k),f(x)表示x的因子个数。现在问谁能拿到最多的糖果,并且拿到了多少糖果。

思路:看起来好像很麻烦。。其实可以分解成两个问题。

第一个子问题就是约瑟夫问题的加强版。。。每次间隔不是定数,而取决与上一次出队的人。。。

终点是数据有5E5.。。模拟的话会炸掉。。。所以用线段树来模拟这个过程。。。

类似于那道插队的问题。。。线段树的域存的是某区间中空位置的数量。。初始为1.。。

然后每次update的时候优先查看左子树。。。

第二个子问题就是。。。到底第几个出去的人那道的糖果最多。。。。

其实也就是求1..n中。。。因子数最大的那个。。。

利用反素数表。。。每次upper_bound一下即可。。。

 

顺便再来个打反素数以及对应约数的表。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz