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;
//Higher 64 bit
ULL H; //Lower 64 bit
ULL L; default;
_uint128() =
_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;
}
operator += (const _uint128 &rhs){
_uint128& if(AddEqULL(L, rhs.L))
++H;
H += rhs.H;return *this;
}operator + (const _uint128& rhs) const{
_uint128 this;
_uint128 ans = *
ans += rhs;return ans;
}
operator -= (const _uint128& rhs) {
_uint128& if (SubEqULL(L, rhs.L))
--H;
H -= rhs.H;return *this;
}operator - (const _uint128& rhs) const {
_uint128 auto tmp = *this;
return tmp -= rhs;
}
operator = (UINT rhs){
_uint128&
L = rhs;0;
H = return *this;
}
operator *= (UINT rhs){
_uint128&
ULL tmp = (L & ML32) * rhs;
L = (L & MH32) | (tmp & ML32);32U;
tmp >>= bool of = AddEqULL(tmp, (L >> 32U) * rhs);
32U);
L = (L & ML32) | ((tmp & ML32) << 32U;
tmp >>= if(of){
++tmp;
}
of = AddEqULL(tmp, (H & ML32) * rhs);
H = (H & MH32) | (tmp & ML32);32U;
tmp >>= if(of){
++tmp;
}32U) * rhs);
AddEqULL(tmp, (H >> 32U);
H = (H & ML32) | ((tmp & ML32) << return *this;
}operator * (UINT rhs) const{
_uint128 this;
_uint128 ans = *
ans *= rhs;return ans;
}operator - () const{
_uint128
_uint128 ans(~H, ~L);1;
ans += (_uint128)return ans;
}
_uint128& DivEqMod(ULL& rem, UINT x){
rem = H % x;
H /= x;32U;
rem <<= 32U;
rem += L >> 32U);
L = (L & ML32) | ((rem / x) <<
rem %= x;32U;
rem <<=
rem += L & ML32;
L = (L & MH32) | (rem / x);
rem %= x;return *this;
}operator /= (UINT x) {
_uint128&
ULL rem;
DivEqMod(rem, x);return *this;
}operator / (UINT x) const {
_uint128 auto tmp = *this;
return tmp /= x;
}operator <<= (UINT x){
_uint128&
H <<= x;64U-x));
H |= (L >> (
L <<= x;return *this;
}operator << (UINT x){
_uint128 this;
_uint128 ans = *
ans <<= x;return ans;
}
};
//typedef LL _uint128;
int main() {
#ifndef ONLINE_JUDGE
"in.in", "r", stdin);
freopen("out.out", "w", stdout);
freopen(#endif
int T;
false);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(
cin >> T;for (int Ti = 1; Ti <= T; ++Ti) {
//m is the length of a step, query the k_th man.
LL n, m, k;
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
} 1;
LL i = n - k + 1) % i;
ans = (m-for (++i; i <= n; ++i) {
ans = (ans + m) % i;
}
}"Case #" << Ti << ": " << ans + 1 << endl;
cout <<
}
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
"in.in", "r", stdin);
freopen("out.out", "w", stdout);
freopen(#endif
int T;
false);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(
cin >> T;for (int Ti = 1; Ti <= T; ++Ti) {
//m is the length of a step, query the k_th man.
LL n, m, k;
LL ans;
cin >> n >> k >> m;if (m <= k) {
if (1 == m) {
1;
ans = k-else {
} 1;
LL i = n - k + 1) % i;
ans = (m-while (i < n) {
2) / (m - 1));
LL c = min(n - i, (i - ans + m -
ans += m * c;
i += c;
ans %= i;
}
}else { //k < m
} 1;
LL i = n - k + 1) % i;
ans = (m-for (++i; i <= n; ++i) {
ans = (ans + m) % i;
}
}"Case #" << Ti << ": " << ans + 1 << endl;
cout <<
}
return 0;
}