Who Gets the Most Candies?

Link: Who Gets the Most Candies?

Description

N children are sitting in a circle to play a game.

The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (−A)-th child to the right.

The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?

Input

There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 500,000) and K (1 ≤ K ≤ N) on the first line. The next N lines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within ) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.
Output

Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.

Sample Input

4 2
Tom 2
Jack 4
Mary -1
Sam 1
Sample Output

Sam 3

Problem solving

这道题的意思是有一圈孩子围成一个圈坐着，每个孩子都有一个value，从第k个孩子开始，将这个孩子删除，然后将这个孩子的的value所指的孩子也删除。直到删除完所有孩子。求第几个被删除的孩子的最大，x是孩子被删的次序，代表的是x的因子数。
这个问题我们可以分成两部分考虑
一：因为删除孩子的次序一定是，所以我们可以先找出来这个范围里面因子个数最多的那个数。似乎暴力会TLE，所以这里会用到一个关于素数的概念。高合成数（有人也叫做？反素数），因为每个数都可以进行质因子分解，所以我们根据质因子的不同搭配可以求出用因子个数递增的一个序列。高合成数的意思就是对于一个高合成数x，比它小的任何数的因子数都小于等于它。所以我们只要找到最接近n的那个高合成数即可。高合成数我们可以打表得到。以上是网上的版本。下面是我自己的理解因为每个数都可以质因子分解为，所以相当于对于每个高合成数，小于它的数的因子数一定小于他，大于它小于第一个比它大的高合成数区间内的数因子数也小于它。
二：找到高合成数x——因子数最多的数，就是我们要删除x次，这就成了约瑟夫环问题的变形了。但是直接模拟会TLE。我们可以用线段树实现，这个思路就不再多说了，跟POJ - 2828 Buy Tickets基本一样。关于下一个孩子的指向可以参考这篇博客说的十分清晰：https://blog.csdn.net/wyxeainn/article/details/76095860

Code

对于poj的G++和C++的区别真的是无力吐槽了（应该还是怪我太菜、

#include<iostream>
#include<string>
using namespace std;
const int maxn = 5e5+10;
int hn[] = {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 pn[] = {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 node{
    int val;
    char name[20];
}p[maxn];
int tree[maxn<<2];
void build(int l,int r,int rt){
    if(l==r){
        tree[rt]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
int query(int l,int r,int val,int rt){
    if(l==r){
        tree[rt]=0;
        return l;
    }
    int mid=(l+r)>>1,ans;
    if(val<=tree[rt<<1])    ans=query(l,mid,val,rt<<1);
    else ans=query(mid+1,r,val-tree[rt<<1],rt<<1|1);

    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    return ans;        
}
int main()
{
    ios::sync_with_stdio(0);
    int n,k;
    while(cin>>n>>k){
        for(int i=1;i<=n;i++){
            cin>>p[i].name>>p[i].val;
        }
        build(1,n,1);
        int pos=0,ans;
        while(hn[pos]<=n)    pos++;
        pos--;
        int mid=hn[pos];
        for(int i=0;i<mid;i++){
            ans=query(1,n,k,1);
            if(!tree[1])    break;
            if(p[ans].val>0) k = ((k-1+p[ans].val)%tree[1]+tree[1]-1)%tree[1]+1;
            else k = ((k-1+p[ans].val)%tree[1]+tree[1])%tree[1]+1;
        }    
        cout<<p[ans].name<<" "<<pn[pos]<<endl;
    }
    return 0;
}
赏