约瑟夫问题
约瑟夫问题
用线段树历经千辛万苦终于做出来了，(;´༎ຶД༎ຶ )。结果上网一找貌似有个\(O(n)\)的递推写法
线段树
题目来源：Code[VS]
题目是经典的约瑟夫问题，但是数据比原题大了许多，若直接模拟的话一定会超时，所以我们需要用其他方法优化。
我们知道，模拟的时间复杂度为$ O(nm) $,第一个n为n次游戏，没有优化的空间，所以我们要从m下手。m应为从当前结点向右找到第m个结点，对于每个结点我们都需判断其是否被取过，所以较慢。所以我们可以记录一下某个区间内还存在多少个结点，因为游戏的过程中还要更改结点，所以用线段树再合适不过了。
于是我们建立一棵树，将其分为以下几个模块： 1
2
3
4
5
6
7
8
9
| struct SegmentTree{
trueint a[MAXN];
int num[MAXN];
truevoid Build();
truevoid Del();
truevoid Update();
truevoid Main();
};
|
其中，Build(),Del()与Main()都较易实现，唯一需要慎重考虑的即为Update()函数。
以下，我们对Upate()所需实现的功能从普遍到特殊进行简单的分析(设我们剩余需跳过的长度为last):
- 用
Update(i,m)表示从i开始走m步(不包括i).
- (刚进入
Update(i,m)时)当前为一个普通的叶结点时，我们需要向父节点搜素，搜至当前 结点i使得num[i]为小于m的最大值.
- 当前结点已搜至跟结点时，我们只需执行
Update(0，last%num[1]),等价于已经多次跑遍整个环。
- 当前结点不为叶结点时，若右兄弟存在，则跳至右兄弟，否则跳至父节点的右兄弟，以此类推.
- 若当前结点及其父节点等不存在右兄弟(即它们一直都是右子树),则
Upate(0,last),即结束此圈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include <cstdio>
#include <algorithm>
using namespace std;
struct SegmentTree
{
trueint a[5000000];
trueint num[5000000];
truevoid Build(int i,int n,int l)
{
truetruenum[i] = n;
truetrueif (n==1)
truetrue{
truetruetruea[i] = l;
truetruetruereturn;
truetrue}
truetruea[i] = 0;
truetrueBuild(i*2,n/2,l);
truetrueBuild(i*2+1,(n+1)/2,l+n/2);
true}
truebool Check(int i)
{
truetrueint x = i;
truetruewhile (x%2==1 && x!=1)
truetruetruex /= 2;
truetruereturn x==1?true:false;
true}
truevoid Del(int x)
{
truetruefor (int i = x; i>=1; i/=2)
truetruetruenum[i] --;
true}
trueint Update(int x,int m)
{
truetrueint last = m;
truetrueint i;
truetrueif (x==0)
truetruetruefor (x=1; !a[x]; x*=2);
truetrue
truetruefor (i=x; num[i/2]<=m && i!=1 &&(i%2==0 || num[i]==num[i/2]); i/=2);
truetrue
truetruewhile (1)
truetrue{
truetruetrue
truetruetrueif (num[i]>last)
truetruetruetruei = i*2;
truetruetrueelse if (num[i]==last){
truetruetruetrue
truetruetruetruewhile (!a[i])
truetruetruetruetruei = num[i*2+1]?i*2+1:i*2;
truetruetruetruereturn i;
truetruetrue}else{
truetruetruetruelast -= num[i];
truetruetruetrue
truetruetruetrueif (Check(i)) return Update(0,last);
truetruetruetrueif (i%2==0) i++;
truetruetruetrueelse i = i/2 + 1;
truetruetrue}
truetrue}
truetruereturn i;
true}
truevoid Main(int n,int m)
{
truetrueBuild(1,n,1);
true
true
true
truetrueint x = 0;
truetruefor (int i =1; i<=n; i++)
truetrue{
truetruetruex = Update(x,m);
truetruetrueDel(x);
truetruetrueprintf("%d ",a[x]);
truetrue}
true}
}Tree;
int main()
{
trueint n,m;
truescanf("%d%d",&n,&m);
trueTree.Main(n,m);
}
|
递归解法
链接