约瑟夫问题：
有n个人，编号为1~n，从第一个人开始报数，从1开始报，报到m的人会死掉，然后从第m+1个人开始，重复以上过程。在死了n-1个人后，问最后一个人的编号是？
暴力
题目传送门
暴力都想不到就真是让人折服了。
暴力的话大模拟即可，不是重点，贴份代码就算了。
#include <cstdio>
int n,k;
struct node{
int x;
node *next;
node(int c):x(c),next(NULL){}
};
node *first=NULL;
int main()
{
scanf("%d %d",&n,&k);
node *last=new node(1);
first=last;
for(int i=2;i<=n;i++)
last->next=new node(i),last=last->next;
last->next=first;
for(int i=1;i<=n;i++)
{
for(int j=1;j<k;j++)
last=first,first=first->next;
printf("%d ",first->x);
last->next=first->next;
first=first->next;
}
}
进阶
题目传送门
这是进阶版的约瑟夫问题。
显然
O
(
n
k
)
O(nk)
O(nk) 的暴力无法满足我们的需要，所以我们要用更加优秀的做法。
发现这题和前一题有一个区别——不需要输出每次谁死了，也就是说，我们只关心最后谁活了下来。
为了方便，我们设一开始的
n
n
n 个人的编号为
0
0
0 ~
n
−
1
n-1
n−1。
那么把第
k
k
k 个人干死之后（注意，第
k
k
k 个人的编号应该是
k
−
1
k-1
k−1），队伍变成了：
k
,
k
+
1
,
k
+
2
,
⋯
 
,
n
−
2
,
n
−
1
,
0
,
1
,
⋯
k,k+1,k+2,\cdots,n-2,n-1,0,1,\cdots
k,k+1,k+2,⋯,n−2,n−1,0,1,⋯
然后会从第
k
k
k 个人那里重复上面的过程。那么不妨将他们重新编号，使每个人的编号都减去
k
k
k，那么编号变成：
0
,
1
,
2
,
⋯
 
,
n
−
3
,
n
−
2
0,1,2,\cdots,n-3,n-2
0,1,2,⋯,n−3,n−2
那么现在就变成了一个
n
−
1
n-1
n−1 阶的约瑟夫问题，假设我们知道
n
−
1
n-1
n−1 阶约瑟夫问题的解（也就是最后谁会活下来），那么将这个解——即活下来的人的编号——
+
k
+k
+k，就可以得到
n
n
n 阶约瑟夫问题的解了。
那么
n
−
1
n-1
n−1 阶约瑟夫问题的解从哪里知道呢？从
n
−
2
n-2
n−2 阶约瑟夫问题的解那里得到。于是就得到了一个
O
(
n
)
O(n)
O(n) 的递推做法。
得到答案之后，还要
+
1
+1
+1，因为我们是从
0
0
0 开始编号的，然而题目要求从
1
1
1 开始编号。
从
0
0
0 开始编号是为了方便取模运算。
代码如下：
#include <cstdio>
int n,k;
int main()
{
scanf("%d %d",&n,&k);
int ans=0;
for(int i=1;i<=n;i++)
ans=(ans+k)%i;
printf("%d",ans+1);
}
再进阶
题目传送门
发现这题的
n
n
n 变得巨大，
O
(
n
)
O(n)
O(n) 的优秀递推都会凉凉。
但是这题的
k
k
k 特别小，只有
1000
1000
1000，这就是这题的突破口了。
假如像上面一样枚举
i
i
i 的话，发现
i
i
i 大起来之后，很多时候
a
n
s
+
k
ans+k
ans+k 之后依然小于
i
i
i，也就是说，此时对
i
i
i 取模跟没取模的值是一样的，就是不需要进行取模，也就是说，每次可以直接加若干个
k
k
k，然后再对此时的
i
i
i 进行取模。
那么怎么知道每次要加多少个
k
k
k 呢？仔细想想，其实这就是一个追击问题：
a
n
s
ans
ans 每次加
k
k
k，
i
i
i 每次加
1
1
1，问多少次之后
a
n
s
≥
i
ans\geq i
ans≥i。
那么这个就是一个简单的追击问题，然后模拟即可，这样的话程序就跑的飞快了。
代码如下：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ll long long
ll n,k;
int main()
{
scanf("%lld %lld",&n,&k);
ll i=1,ans=0,p;
//本来i应该从0开始，但是0需要特判掉，懒得打特判，于是从1开始
while(i<n)
{
p=(i-ans)/(k-1)+((i-ans)%(k-1)!=0);//距离 除以 速度的差 得到 时间
//但是因为这里是整除，所以如果(i-ans)不是(k-1)的倍数的话，还需要多走一次，这个想想就能明白
if(i+p>n)p=n-i;//要判断是否大于n
ans+=p*k;//ans走
i+=p;//i走
ans%=i;//取模
}
printf("%lld",ans+1);//别忘了+1
}
