UVa 1452 - Jump

#思维 #递推 #DP #约瑟夫问题
Published on 2016-02-07

题目地址

描述

有 n(n≤500000)n(n\le500000) 个人顺时针排成一个圆圈，依次顺时针标号 1−n1 - n。现在从 11 开始，每隔 k(k≤500000)k(k\le500000) 个人退出一个，问最后三个退出的人分别是谁？

样例输入

3
10 2
13 10
30000 54321

样例输出

1 9 5
1 11 2
10775 17638 23432

分析

之前 UVa 1394 - And Then There Was One 的进化版，强烈建议先看我那题的题解 UVa 1394 - And Then There Was One。
如果我们知道 n−1n - 1 规模问题中最后三个人的标号，那么我们同样能够通过重标号法知道 nn 规模问题中最后三个人的标号。问题在于怎么求初始值。如果只要求最后一个人的标号，很简单初始值 f[1]=0f[1] = 0，但是现在要算三个人，怎么办呢？很好办。（以下标号全部从 00 开始）。
手算，先给出递推定义：
f[i][0]f[i][0]：一共 ii 个人，倒数第二个人被删除的人的编号。
f[i][1]f[i][1]：一共 ii 个人，倒数第一个人被删除的人的编号。
f[i][2]f[i][2]：一共 ii 个人，最后一个被删除的人的编号。
为了方便，定义一下函数。mod(i,j)mod(i, j) 的作用是让标号 ii 到 [0,j)[0, j) 这个区间（可能有负数的麻烦），mod(i,j)=((i%j)+j)%jmod(i, j) = ((i\;\%\;j) + j)\;\%\;j。
那么我们很容易可以算出 33 个人的时候第一个被删除的人的标号为 f[3][0]=mod(k%3−1,3)f[3][0] = mod(k\;\%\;3 - 1, 3)。再次利用重标号法，算出第二个被删除的人的标号 f[3][1]=mod(f[0]+1+mod(k%2−1,2),3)f[3][1] = mod(f[0] + 1 + mod(k\;\%\;2 - 1, 2), 3)，最后一个人就是 f[i][2]=3−f[i][0]−f[i][1]f[i][2] = 3 - f[i][0] - f[i][1]。
然后与 UVa 1394 一样，递推并滚动数组。最后答案要转化到 [1,n][1, n] 这个范围，所以不要忘记 +1+1！

代码

//  Created by Sengxian on 2/7/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1452 约瑟夫变形 + 递推
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

int f[3], n, k;
//f[i][0] i 个人，倒数第二个人被删除的人的编号
//f[i][1] i 个人，倒数第一个人被删除的人的编号
//f[i][2] i 个人，最后一个被删除的人的编号
//从 0 开始

inline int mod(int x, int k) {
    return ((x % k) + k) % k;
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt(), k = ReadInt();
        //手算出 f[3][x]
        f[0] = mod(k % 3 - 1, 3);
        f[1] = mod(f[0] + 1 + mod(k % 2 - 1, 2), 3);
        f[2] = 3 - f[0] - f[1];
        for(int i = 4; i <= n; ++i)
            for(int j = 0; j < 3; ++j)
                f[j] = (f[j] + k) % i;
        printf("%d %d %d\n", f[0] + 1, f[1] + 1, f[2] + 1);
    }    
    return 0;
}
UVa 1351 - String Compression