HDU5860 Death Sequence

2016多校, HDU, 递推

　　2016 Multi-University Training Contest 10

　　题意：n个人报数，每一轮报数(i*k+1)的人淘汰，到队列末尾后剩余人员进行新一轮报数，直至全员淘汰。给定m次查询，求第j个出队者的序号。 - 原题链接

　　类约瑟夫问题，但是不成环。
　　本题种当前总人数为n，编号1-n，则本轮i%k==1的人淘汰，淘汰总人数为(n+k-1)/k。剩下的人从1开始重编号，重复上一轮的过程。设i为第f[i]轮第g[i]个出局，则有以下递推关系式：

1
2
f[i]=(i%k==1) ? 1 : f[i-(i+k-1)/k]+1;
g[i]=(i%k==1) ? (i+k-1)/k : g[i-(i+k-1)/k];

　　预处理出前j轮淘汰的总人数cnt[j]，则i的出队序号为cnt[f[i]-1]+g[i]。 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=3*1e6 + 10;
int T, n, m, k;
int tot, cnt[maxn], f[maxn], g[maxn], ans[maxn];
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &k, &m);
        tot=0;
        memset(cnt, 0, sizeof cnt);
        for(int tmp=n; tmp; tmp-=cnt[tot]-cnt[tot-1])
        {
            cnt[++tot]=(tmp+k-1)/k;
            cnt[tot]+=cnt[tot-1];
        }
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);
        for(int i=1; i<=n; i++)
        {
            f[i]=(i%k==1) ? 1 : f[i-(i+k-1)/k]+1;
            g[i]=(i%k==1) ? (i+k-1)/k : g[i-(i+k-1)/k];
            ans[cnt[f[i]-1]+g[i]]=i;
        }
        for(int i=1, x; i<=m; i++)
        {
            scanf("%d", &x);
            printf("%d\n", ans[x]);
        }
    }
    return 0;
}