Problem Description

In order to remember history, King plans to play losephus problem in the parade gap.He calls n(1≤n≤5000) soldiers,
counterclockwise in a circle, in label 1,2,3...n.

The first round, the first person with label 1 counts
off, and the man who report number 1 is
out.

The second round, the next person of the person who is out in the last round counts off, and the man who report number 2 is
out.

The third round, the next person of the person who is out in the last round counts off, and the person who report number 3 is
out.

The N - 1 round, the next person of the person who is out in the last round counts off, and the person who report number n−1 is
out.

And the last man is survivor. Do you know the label of the survivor?

 

Input

The first line contains a number T(0<T≤5000),
the number of the testcases.

For each test case, there are only one line, containing one integer n,
representing the number of players.

 

Output

Output exactly T lines.
For each test case, print the label of the survivor.

 

Sample Input

 

Sample Output

 

题意：n个人排成一圈，每回合杀死一个人，杀死后从那个人的下一个人开始数数，第i个回合数到i的那个人被杀死，问最后剩下的人的编号是多少。

思路：这题和约瑟夫环有点像，我们设f[n]为总人数为n时，按照题目中的规则杀，最后剩下来的人的编号是多少。我们每次杀死一个人后就重新编号，那么f[1]=0,即当最后只剩下一个人时，他经过重新编号后新的编号为0，那么在上一轮，他的编号为t=(0+n-1)%2,倒数第二轮他的编号为(t+n-2)%3,这样可以依次类推到f[n]，就是答案了，所以这题只要用O(n^2)的复杂度初始化一下就行了。

           这种方法有个缺陷，就是不能知道每一次杀死的人的编号是什么，如果要知道每一次杀死的人的编号，我们可以用线段树做。我们在线段树上对于每一段维护其剩余的空位数，那么我们每次计算这一次杀死的人是线段树总区间的第几个人，这样就可以知道每次的编号是多少了，如果这题用线段树，为了防超时，可以打个表。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<bitset>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef long double ldb;

#define inf 99999999

#define pi acos(-1.0)

#define maxn 6006

int a[maxn];

void init()

{

    int i,j;

    a[1]=1;

    for(i=2;i<=5000;i++){

        int num=0;

        //for(j=i-1;j>=1;j--){

        for(j=1;j<=i;j++){

            num=(num+i-j+1)%j;

        }

        a[i]=num+1;

    }

}

int main()

{

    int n,m,i,j,T;

    init();

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        printf("%d\n",a[n] );

    }

    return 0;

}

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<bitset>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef long double ldb;

#define inf 99999999

#define pi acos(-1.0)

#define maxn 5006

struct node{

    int l,r,num;

}b[4*maxn];

int n;

void build(int l,int r,int th)

{

    int mid;

    b[th].l=l;b[th].r=r;

    b[th].num=r-l+1;

    if(l==r)return;

    mid=(l+r)/2;

    build(l,mid,th*2);

    build(mid+1,r,th*2+1);

}

void update(int num,int cishu,int th)

{

    int mid;

    if(b[th].l==b[th].r){

        b[th].num=0;

        if(cishu==n)printf("%d,",b[th].l);

        return;

    }

    if(b[th*2].num>=num){

        update(num,cishu,th*2);

    }

    else{

        update(num-b[th*2].num,cishu,th*2+1 );

    }

    b[th].num=b[th*2].num+b[th*2+1].num;

}

int main()

{

    int t,m,i,j,T,k;

    freopen("o.txt","w",stdout);

    for(n=1;n<=5000;n++)

    {

        build(1,n,1);

        int p=1;

        int tot=n;

        for(k=1;k<=n;k++){

            p=(p+k-1)%tot;  //这里算这回合杀死的人的编号的空格数

            if(p==0)p=tot;

            update(p,k,1);

            if(p==tot)p=1; //这里算出这回合杀死人后，下一回合第一个数数的编号,也可以看做是下一回合站第几个空位

            tot--;   //每次总人数减1

        }

    }

}