CodeForces 100285C CVS

可持久化栈?

Codeforces 100285C CVS

题目描述

你需要设计一种数据结构,需要支持以下操作:

  • learn x y ,表示 x 号选手学会了技能 y,技能不重复
  • rollback x ,表示撤销 x 号选手学习的最新技能
  • relearn x ,表示将 x 号选手的最近遗忘的技能捡起来了,保证有知识点可以遗忘
  • clone x ,表示将 x 号选手复制一份,克隆人是最后一个,题目保证克隆人不会遗忘 x 号选手学过的知识点
  • check x ,表示询问 x 号选手的最新技能

题解

用到了可持久化的思想。。

我们对于每一个人,建立一个栈表示他的所有技能(学过的技能放在 fir 中,忘记的技能放在 forget 里面,实际上是利用栈实现的)

注意到题目保证的条件,我们就可以将克隆人的栈直接从原来的栈克隆过去了。

假设原来长这样,1’ 是 1 的复制品:

before

然后,我们让 1’ 选手学习 skill3,图就变成了

now

通过图片,我们发现直接复制头指针是可以完成题目要求

(也算是间接实现了可持久化了吧)

AC Code

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
#include <bits/stdc++.h>
#else
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#endif
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
const int MOD = 1e9 + 7;
const int maxn = 1000009;
const int maxm = 300009;
const ll inf = 1e18;
const double pi = acos(-1.0);
const double eps = 1e-6;
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
template <class T>
inline bool scan_d(T & ret)
{
char c;
int sgn;
if(c = getchar(), c == EOF)return false;
while(c != '-' && (c < '0' || c > '9'))c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while(c = getchar(), c >= '0' && c <= '9')
ret = ret * 10 + (c - '0');
ret *= sgn;
return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
scan_d(ret);
scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
if(ch = getchar(), ch == EOF)return false;
while(ch == ' ' || ch == '\n')ch = getchar();
return true;
}
template <class T>
inline void out_number(T x)
{
if(x < 0)
{
putchar('-');
out_number(- x);
return ;
}
if(x > 9)out_number(x / 10);
putchar(x % 10 + '0');
}
struct knowledge
{
int val, next;
}know[maxn];
struct student
{
int fir, forget;
}student[maxn];
int q, m, n, now, x, y;
char type[20];
inline void learn(int x, int y)
{
know[++ now].val = y;
know[now].next = student[x].fir;
student[x].fir = now;
}
inline void rollback(int x)
{
int p = student[x].fir;
know[++ now].val = know[p].val;
student[x].fir = know[p].next;
know[now].next = student[x].forget;
student[x].forget = now;
}
inline void relearn(int x)
{
int p = student[x].forget;
know[++ now].val = know[p].val;
student[x].forget = know[p].next;
know[now].next = student[x].fir;
student[x].fir = now;
}
inline void clone(int x)
{
++ n;
student[n] = student[x];
}
inline int check(int x)
{
return ! student[x].fir ? -1 : know[student[x].fir].val;
}
int main()
{
scanf("%d %d", &q, &m);
n = now = 1;
RESET(student);
RESET(know);
while(q --)
{
scanf(" %s", type);
switch(type[3])
{
case 'r': //learn
scanf("%d %d", &x, &y);
learn(x, y);
break;
case 'l': //rollback
scanf("%d", &x);
rollback(x);
break;
case 'e': //relearn
scanf("%d", &x);
relearn(x);
break;
case 'n': //clone
scanf("%d", &x);
clone(x);
break;
case 'c': //check
scanf("%d", &x);
if((y = check(x)) == -1) puts("basic");
else printf("%d\n", y);
break;
default:
puts(type);
assert(false);
}
}
return 0;
}
/*
9 10
learn 1 5
learn 1 7
rollback 1
check 1
clone 1
relearn 2
check 2
rollback 1
check 1
*/
/*
14 10
learn 1 1
learn 1 3
rollback 1
rollback 1
clone 1
learn 1 2
relearn 2
check 2
relearn 2
check 2
rollback 2
check 2
rollback 2
check 2
*/
文章目录
  1. 1. Codeforces 100285C CVS
    1. 1.1. 题目描述
    2. 1.2. 题解
    3. 1.3. AC Code
{{ live2d() }}