2016-10-10

HDU 5860 Death Sequence【约瑟夫环变形】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5860

题意：

有$n$个人站成一排，从第$1$号开始，每隔$k$个人就杀死一人，进行完一遍后，重新从头开始，直到全部杀死。$q$个询问，每个询问一个$x$，回答出第$x$个被杀死的人的编号。
数据范围：$n \le 3000000 , q \le 1000000, k \ge 1 , x \le n$

分析：

约瑟夫环的基本思想就是递推，将编号改为下标从$0$开始后，考虑某一个元素其在当前轮与上一轮的编号关系。
对于这道题，从第一轮开始，假设编号为$i$，若$i \% k = 0$，那么其在该轮被杀死，否则其将留在下一轮，新编号为$i - i / k - 1$
对于每个元素我们分别记录其在第几轮死亡以及在该轮中是第几个死的，
若$i \% k = 0$, 第一轮，第$i-i/k-1$个死亡
若$i \% k != 0$，第$i-i/k-1$所在轮的下一轮，与$i-i/k-1$相同
这样从头扫一遍即可，处理出来后$O(1)$查询。

代码：

/*************************************************************************
    > File Name: 5860.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/10 13:07:20
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 3e6 + 5;
typedef pair<int, int> p;
p a[maxn];
int b[maxn];
int ans[maxn];
int main (void)
{
	int T;scanf("%d", &T);
	while(T--){
		int n, k, q;scanf("%d%d%d", &n, &k, &q);
		memset(b, 0, sizeof(b));
		for(int i = 0; i < n; ++i){
			if(i % k == 0){
				a[i].first = 1;
				a[i].second = i / k + 1;
			}else{
				a[i].first = a[i - i / k - 1].first + 1;
				a[i].second = a[i - i / k - 1].second;
			}
			b[a[i].first]++;
		}
		for(int i = 1; b[i]; ++i){
			b[i] += b[i - 1];
		}
		for(int i = 0; i < n; ++i){
			int tmp = b[a[i].first - 1] + a[i].second;
			ans[tmp] = i + 1;
		}
		int x;
		while(q--){
			scanf("%d", &x);
			printf("%d\n", ans[x]);
		}
	}
	return 0;
}