POJ 2886: Who Gets the Most Candies?

POJ 2886: Who Gets the Most Candies?

题意

约瑟夫环问题(Josephus Problem)(固定下一个踢出位置)，这道题下一个踢出位置由当前踢出人决定。

$N$ 个人围成一圈，编号从 $1\sim N$，每个当前踢出的人能决定下一个踢出的人在相对于他的第几个位置，开始时踢出人在位置 $K$ 上。

设小于等于 $N$ 的最大的反素数为 $q$，求出第 $q$ 次踢出的人的位置。

数据范围：$1\leqslant N\leqslant 5\times 10^5, 1\leqslant K\leqslant N$。

思路

先求出小于等于 $N$ 的最大的反素数，求法见 反素数。

用线段树维护当前还剩余的人，有一个人就记为1(即计数线段树)。

通过线段树，能log级求出来当前从左到右第rk位的人的id。

那么下一步就是如何快速求出下一个踢出的人相对于第一个人是第几个：

这个问题最初是Josephus Problem是可以用递推线性求解的，这个问题可以类似思考，

考虑当前剩余人数和顺时针枚举还是逆时针枚举顺序这些条件，就可以确定下来下一次踢出的人的相对rk值。

点击显/隐代码

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define ull unsigned long long
#define db double
//#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define pb push_back
#define mkp make_pair
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const db PI = acos(-1);
const int N = 5e5 + 10;
int n, m, mxfct, num;
int prim[6] = {2, 3, 5, 7, 11, 13};
void dfs(int now, int limit, int fct, int x) {
	if (fct > mxfct || (fct == mxfct && x < num)) {
		mxfct = fct;
		num = x;
	}
	if (now >= 6) return;
	for (int i = 1; i <= limit; i++) {
		x *= prim[now];
		if (x > n) return;
		dfs(now+1, i, fct*(i+1), x);
	}
}
struct SEG {
	struct Node {
		int l, r, sum;
	}t[N<<2];
	void pushup(int p) {
		t[p].sum = t[ls].sum + t[rs].sum;
	}
	void build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		t[p].sum = 0;
		if (l == r) {
			t[p].sum = 1;
			return;
		}
		int mid = (l+r) >> 1;
		build(ls, l, mid);
		build(rs, mid+1, r);
		pushup(p);
	}
	int update(int p, int rk) {
		if (t[p].l == t[p].r) {
			t[p].sum = 0;
			return t[p].l;
		}
		int ret = 0;
		if (t[ls].sum < rk) ret = update(rs, rk - t[ls].sum);
		else ret = update(ls, rk);
		pushup(p);
		return ret;
	}
}seg;
char name[N][15];
int a[N];
signed main() {
#ifdef _DEBUG
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif
	while (~scanf("%d %d", &n, &m)) {
		num = mxfct = 0;
		dfs(0, 100, 1, 1); //这里求反素数的方法就是直接暴力枚举了，其实没有大根堆做法优秀。
		for (int i = 1; i <= n; i++) {
			scanf("%s %d", name[i], &a[i]);
		}
		seg.build(1, 1, n);
		int last = 0;
		for (int i = 1; i <= num; i++) {
			last = seg.update(1, m);
			int tmp = a[last] > 0 ? 2 : 1;
			if (n == i) m = 1;
			else m = ((m-tmp+a[last]) % (n-i) + (n-i)) % (n-i) + 1;
			//cout << last << ' ' << m << '\n';
		}
		printf("%s %d", name[last], mxfct);
	}
	return 0;
}