2018沈阳现场赛K题题解约瑟夫问题

阅读量: searchstar 2019-07-08 16:10:38

Categories： Tags：

vjudge链接：https://vjudge.net/problem/Gym-101955K

题目大意：给定初始人数n，步长m，求第k个被弹出的人的编号。

这题有一个非常重要的条件，那就是sum(min(m, k)) <= 2e6

因此我们可以分情况讨论。下面假设编号从0开始。
1. k < m
此时k最大为2e6。因此我们可以使用一个O(k)的方法求出答案。
设f(n, k)为初始为n个人时第k个被弹出的人。第一个被弹出的人编号显然为(m-1) % n，从下一个人开始从0开始重新编号，问题变成了求f(n-1, k-1)，假设其已知，那么再把结果的坐标转换回来即可。表达式为f(n, k) = (f(n-1, k-1) + m) % n。由于k < n，因此用它求解复杂度为O(k)。
2. m <= k
此时m最大为2e6，因此我们可以使用一个O(m)的方法求出答案。
看了大佬的博客之后豁然开朗：
maskray.me/blog/2013-08-27-josephus-problem-two-log-n-solutions
这里我用自己的语言复述一下。
设第p次报数的人为y，假设这次报数y没有被弹出，那么p % m < m-1，设下次y报数是第q次报数。显然第0到p-1次报数总共有a = floor(p / m)个人被弹出，所以第p次报数之后总共有n - a个人，所以q = p + n - a。第k个被弹出去的人被弹出时显然是第(k-1) * m + m-1次报数。如果我们能用q来推出p，那么就可以一直往前推，直到p < n，这就是这个人的编号。
整理一下，目前已知条件只有三个：
p % m < m-1
q = p + n - a
a = floor(p / m)
我们先尝试引入模数来消掉向下取整。设p = a * m + b
则已知条件转化为：
p = a * m + b (1)
b < m-1 (2)
q = p + n - a (3)
把(1)代入(3)，得q = (m-1)a + n + b
即 q - n = (m-1) a + b， b < m-1
显然就有a = floor((q - n) / (m - 1))
这样我们就用q表示了a。
将其代入(3)中，得
p = q - n + floor((q - n) / (m - 1))
通过之前提到的策略，从(k-1) * m + m-1向前推便可以推出答案。
式子第二项在递推过程中显然是指数减小的，因此不影响复杂度。所以推到答案大约需要
((k-1)*m + m-1) / n
次迭代。由于k < n，所以复杂度为O(m) //（我不知道为什么上面的链接里的文章里说复杂度是O(log n)）

但是存在一个问题，那就是这题需要初始化为(k-1) * m + m-1，会爆long long，要用__int128，但是这题除了gym外目前只找到hdu能交：
acm.hdu.edu.cn/showproblem.php?pid=6458
但是gym和hdu都是windows评测机，不能用__int128，而手写的_uint128 TLE了，因此这题我没有用这个方法过掉。但是由于现场赛是用linux评测机，所以在现场赛这题应该能用这个方法过。
TLE代码：

#include <iostream>

using namespace std;

#define DEBUG 0
#define ONLINE_JUDGE

typedef long long LL;

typedef unsigned long long ULL;
typedef unsigned int UINT;
bool AddEqULL(ULL& lhs, ULL rhs){
    static const ULL HighBit = 1ULL << 63U;
    bool both = (lhs & HighBit) && (rhs & HighBit);
    bool one = (lhs & HighBit) || (rhs & HighBit);
    lhs += rhs;
    return both || (one && !(lhs & HighBit));
}
bool SubEqULL(ULL& lhs, ULL rhs) {
	bool ans = lhs < rhs;
	lhs -= rhs;
	return ans;
}
struct _uint128{
    static const ULL ML32 = 0xffffffffULL;	//mask low32
    static const ULL MH32 = 0xffffffff00000000ULL;
    ULL H;  //Higher 64 bit
    ULL L;  //Lower 64 bit
    _uint128() = default;
    _uint128(UINT x){
        *this = x;
    }
    _uint128(ULL _H, ULL _L){
        H = _H;
        L = _L;
    }

    explicit operator bool(){
        return L || H;
    }
	explicit operator ULL() {
		return L;
	}
    bool operator < (const _uint128 &rhs) const{
        return H != rhs.H ? H < rhs.H : L < rhs.L;
    }

    _uint128& operator += (const _uint128 &rhs){
        if(AddEqULL(L, rhs.L))
            ++H;
        H += rhs.H;
        return *this;
    }
    _uint128 operator + (const _uint128& rhs) const{
        _uint128 ans = *this;
        ans += rhs;
        return ans;
    }

	_uint128& operator -= (const _uint128& rhs) {
		if (SubEqULL(L, rhs.L))
			--H;
		H -= rhs.H;
		return *this;
	}
	_uint128 operator - (const _uint128& rhs) const {
		auto tmp = *this;
		return tmp -= rhs;
	}

    _uint128& operator = (UINT rhs){
        L = rhs;
        H = 0;
        return *this;
    }

    _uint128& operator *= (UINT rhs){
        ULL tmp = (L & ML32) * rhs;
        L = (L & MH32) | (tmp & ML32);
        tmp >>= 32U;
        bool of = AddEqULL(tmp, (L >> 32U) * rhs);
        L = (L & ML32) | ((tmp & ML32) << 32U);
        tmp >>= 32U;
        if(of){
            ++tmp;
        }
        of = AddEqULL(tmp, (H & ML32) * rhs);
        H = (H & MH32) | (tmp & ML32);
        tmp >>= 32U;
        if(of){
            ++tmp;
        }
        AddEqULL(tmp, (H >> 32U) * rhs);
        H = (H & ML32) | ((tmp & ML32) << 32U);
        return *this;
    }
    _uint128 operator * (UINT rhs) const{
        _uint128 ans = *this;
        ans *= rhs;
        return ans;
    }
    _uint128 operator - () const{
        _uint128 ans(~H, ~L);
        ans += (_uint128)1;
        return ans;
    }
    _uint128& DivEqMod(ULL& rem, UINT x){
        rem = H % x;
        H /= x;
        rem <<= 32U;
        rem += L >> 32U;
        L = (L & ML32) | ((rem / x) << 32U);
        rem %= x;
        rem <<= 32U;
        rem += L & ML32;
        L = (L & MH32) | (rem / x);
        rem %= x;
        return *this;
    }
	_uint128& operator /= (UINT x) {
		ULL rem;
		DivEqMod(rem, x);
		return *this;
	}
	_uint128 operator / (UINT x) const {
		auto tmp = *this;
		return tmp /= x;
	}
    _uint128& operator <<= (UINT x){
        H <<= x;
        H |= (L >> (64U-x));
        L <<= x;
        return *this;
    }
    _uint128 operator << (UINT x){
        _uint128 ans = *this;
        ans <<= x;
        return ans;
    }
};

//typedef LL _uint128;

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	int T;

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	for (int Ti = 1; Ti <= T; ++Ti) {
		LL n, m, k;	//m is the length of a step, query the k_th man.
		LL ans;

		cin >> n >> k >> m;
		if (m <= k) {
			_uint128 q;
			for (q = (_uint128)(k-1) * m + (m - 1); !(q < n); q = (q - n + (q - n) / (m - 1)));
			ans = (ULL)q;
		} else {	//k < m
			LL i = n - k + 1;
			ans = (m-1) % i;
			for (++i; i <= n; ++i) {
				ans = (ans + m) % i;
			}
		}
		cout << "Case #" << Ti << ": " << ans + 1 << endl; 
	}

	return 0;
}

另外有一个比较巧妙的方法，不需要用到__int128。我就是用这个方法过掉的这题。
大佬博客：https://www.cnblogs.com/LJHAHA/p/10854951.html
我的代码：

#include <iostream>

using namespace std;

#define DEBUG 0
#define ONLINE_JUDGE

typedef long long LL;

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	int T;

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	for (int Ti = 1; Ti <= T; ++Ti) {
		LL n, m, k;	//m is the length of a step, query the k_th man.
		LL ans;

		cin >> n >> k >> m;
		if (m <= k) {
			if (1 == m) {
				ans = k-1;
			} else {
				LL i = n - k + 1;
				ans = (m-1) % i;
				while (i < n) {
					LL c = min(n - i, (i - ans + m - 2) / (m - 1));
					ans += m * c;
					i += c;
					ans %= i;
				}
			}
		} else {	//k < m
			LL i = n - k + 1;
			ans = (m-1) % i;
			for (++i; i <= n; ++i) {
				ans = (ans + m) % i;
			}
		}
		cout << "Case #" << Ti << ": " << ans + 1 << endl; 
	}

	return 0;
}

codeforces 1184 C2 曼哈顿距离转切比雪夫距离，矩形覆盖最大点数转最大前缀

2017多校北航F题群论

2018沈阳现场赛K题题解 约瑟夫问题

2018沈阳现场赛K题题解约瑟夫问题