HDU 5860 Death Sequence(递推)

题目链接http://acm.split.hdu.edu.cn/showproblem.php?pid=5860

Description

Input

Output

Sample Input

1

7 2 7

1

2

3

4

5

6

7

Sample Output

1

3

5

7

2

6

4

题意：

题解：

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3001000;

int dp[maxn],num[maxn],add[maxn],ans[maxn];

int n,k,q;

void init()

{

    int temp = n;

    int acl = 0;

    add[0] = 0;     //add[i]前i轮kill几个;

    while (temp){

        acl++;

        add[acl]  = add[acl-1] + (temp-1)/k+1;

        temp -= (temp-1)/k+1;

    }

    for (int i = 0; i < n; i++){

        if (i%k == 0){

            dp[i] = 0;

            num[i] = i/k+1;

        }else {

            dp[i] = dp[i-i/k-1] + 1;

            num[i] = num[i-i/k-1];

        }

    }

    for (int i = 0; i < n; i++){

        ans[add[dp[i]]+num[i]] = i;

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while (t--){

        scanf("%d %d %d",&n,&k,&q);

        init();

        int cha;

        while (q--){

            scanf("%d",&cha);

            printf("%d\n",ans[cha]+1);

        }

    }

    return 0;

}