HDU5643 King’s Game(约瑟夫环)

题目链接

题意:变形的约瑟夫环,最初为每个人编号1到n,第i次删去报号为i的人,然后从它的下一个人开始重新从1开始报号,问最终剩下第几号人?

HDU2925相似,同样是从后往前递推,改变下m的值即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int f[5005];
int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    while(t--){
        int n;
        scanf("%d", &n);
        f[1] = 0;
        int m = n-1;
        for(int i = 2; i <= n; i++){
            f[i] = (f[i-1]+m)%i;
            m--;
        }
        cout << f[n]+1 << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 约瑟夫环