水题记录(十)

题目名称 地精部落 单旋
标签 动态规划 LCT
来源 BZOJ 1925 Luogu 3721

BZOJ 1925

题意

求长度为 $n$ 的抖动排列个数

题解

自行体会,不会就打表

1 2 4 10 32 122 544 2770 …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 10;
int f[2][maxn][2], n, p;
inline int mod(int x) {
if (x >= p) x -= p; return x;
}
int main() {
scanf("%d%d", &n, &p);
f[0][1][0] = f[0][2][1] = 1;
for (int i = 3; i <= n; i++) {
for (int k = 1; k <= i; k++)
f[i & 1][k][1] = mod(f[i & 1][k - 1][1] + f[i & 1 ^ 1][k - 1][0]);
for (int k = i; k >= 1; k--)
f[i & 1][k][0] = mod(f[i & 1][k + 1][0] + f[i & 1 ^ 1][k][1]);
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans = mod(ans + mod(f[n & 1][i][0] + f[n & 1][i][1]));
printf("%d\n", ans);
}

Luogu 3721

题意

H国是一个热爱写代码的国家,那里的人们很小去学校学习写各种各样的数据结构。伸展树(splay)是一种数据结构,因为代码好写,功能多,效率高,掌握这种数据结构成为了H国的必修技能。有一天,邪恶的“卡”带着他的邪恶的“常数”来企图毁灭H国。“卡”给H国的人洗脑说,splay如果写成单旋的,将会更快。“卡”称“单旋splay”为“spaly”。虽说他说的很没道理,但还是有H国的人相信了,小H就是其中之一,spaly马上成为他的信仰。而H国的国王,自然不允许这样的风气蔓延,国王构造了一组数据,数据由m(不超过10^5)个操作构成,他知道这样的数据肯定打垮spaly,但是国王还有很多很多其他的事情要做,所以统计每个操作

所需要的实际代价的任务就交给你啦。数据中的操作分为5种:

  • 插入操作:向当前非空spaly中插入一个关键码为key的新孤立节点。插入方法为,先让key和根比较,如果key比根小,则往左子树走,否则往右子树走,如此反复,直到某个时刻,key比当前子树根x小,而x的左子树为空,那就让key成为x的左孩子;或者key比当前子树根x大,而x的右子树为空,那就让key成为x的右孩子。该操作的代价为:插入后,key的深度。特别地,若树为空,则直接让新节点成为一个单个节点的树。(各节点关键码互不相等。对于“深度”的解释见末尾对spaly的描述。)
  • 单旋最小值:将spaly中关键码最小的元素xmin单旋到根。操作代价为:单旋前xmin的深度。(对于单旋操作的解释见末尾对spaly的描述。)
  • 单旋最大值:将spaly中关键码最大的元素xmax单旋到根。操作代价为:单旋前xmax的深度。
  • 单旋删除最小值:先执行2号操作,然后把根删除。由于2号操作之后,根没有左子树,所以直接切断根和右子树的联系即可。(具体见样例解释)。操作代价同2号操作。
  • 单旋删除最大值:先执行3号操作,然后把根删除。操作代价同3号操作。

    对于不是H国的人,你可能需要了解一些spaly的知识,才能完成国王的任务:

    spaly是一棵二叉树,满足对于任意一个节点x,它如果有左孩子lx,那么lx的关键码小于x的关键码。如果有右孩子rx,那么rx的关键码大于x的关键码。
    一个节点在spaly的深度定义为:从根节点到该节点的路径上一共有多少个节点(包括自己)。 单旋操作是对于一棵树上的节点x来说的。一开始,设f为x在树上的父亲。如果x为f的左孩子,那么执行zig(x)操作(如上图中,左边的树经过zig(x)变为了右边的树),否则执行zag(x)操作(在上图中,将右边的树经过zag(f)就变成了左边的树)。每当执行一次zig(x)或者zag(x),x的深度减小1,如此反复,直到x为根。总之,单旋x就是通过反复执行zig和zag将x变为根。

    题解

    用lct维护每个节点的深度,由于操作都只对最大值最小值进行,对树的结构影响不大,模拟即可
    对于插入操作,一定是插入到val的前驱或者后继的下面,那么用一个set维护前驱后继即可

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
#include <bits/stdc++.h>
using namespace std;
set<pair<int,int> >St;
namespace lct {
#define nl NULL
const int maxn = 1e5 + 10;
struct node {
node *father, *son[2];
int value, _size; bool rev;
node(int val = 0) {
value = val; _size = 1; rev = false;
father = son[0] = son[1] = nl;
}
int size() {
return this == nl ? 0 : _size;
}
bool who() {
return father->son[1] == this;
}
bool is_root() {
if (!father) return true;
return father->son[0] != this && father->son[1] != this;
}
void reverse() {
rev ^= 1; swap(son[0], son[1]);
}
void maintain() {
_size = son[0]->size() + 1 + son[1]->size();
}
void pushdown_once() {
if (!rev) return; rev = false;
if (son[0]) son[0]->reverse();
if (son[1]) son[1]->reverse();
}
void pushdown() {
if (!is_root()) father->pushdown(); pushdown_once();
}
void rotate() {
node *f = father, *g = f->father;
bool a = who(), b = !a;
f->son[a] = son[b];
if (son[b])
son[b]->father = f;
son[b] = f;
father = g;
if (!f->is_root())
g->son[f->who()] = this;
f->father = this;
f->maintain(); maintain();
}
void splay() {
for (pushdown(); !is_root(); rotate())
if (!father->is_root())
if (who() ^ father->who()) rotate();
else father->rotate();
}
void access() {
for (node *y = nl, *x = this; x; y = x, x = x->father)
x->splay(), x->son[1] = y, x->maintain();
}
void make_root() {
access(); splay(); reverse();
}
node *root() {
access(); splay();
for (node *x = this; ; x = x->son[0])
if (!x->son[0]) return x;
}
}*T[maxn]; int nodeCnt, root;
int fa[maxn], son[maxn][2];
void link(int x, int y) {
T[x]->make_root(); T[x]->father = T[y];
}
void cut(int x, int y) {
T[x]->make_root(); T[y]->access(); T[y]->splay();
T[x]->father = T[y]->son[0] = nl; T[y]->maintain();
}
int deep(int x) {
T[root]->make_root();
T[x]->access();
return T[root]->size();
}
int insert(int val) {
T[++nodeCnt] = new node(val);
pair<int,int> now = make_pair(val, nodeCnt);
if (!St.size()) {
root = nodeCnt;
St.insert(now);
return 1;
}
set<pair<int,int> >::iterator it = St.lower_bound(now);
if (it == St.begin()) {
int id = it->second;
link(nodeCnt, id);
fa[nodeCnt] = id;
son[id][0] = nodeCnt;
}
else if (it == St.end()) {
int id = (--it)->second;
link(nodeCnt, id);
fa[nodeCnt] = id;
son[id][1] = nodeCnt;
}
else {
set<pair<int,int> >::iterator succ = it, pre = --it;
int lp = pre->second, rp = succ->second;
if (deep(lp) > deep(rp))
link(nodeCnt, lp), fa[nodeCnt] = lp, son[lp][1] = nodeCnt;
else
link(nodeCnt, rp), fa[nodeCnt] = rp, son[rp][0] = nodeCnt;
}
St.insert(now);
return deep(nodeCnt);
}
int splaymin() {
int t = St.begin()->second;
int ans = deep(t);
if (root == t) return ans;
int f = fa[t], g = root, s = son[t][1];
if (f) son[f][0] = s;
if (s) fa[s] = f;
fa[t] = 0;
root = t;
if (g != t) fa[g] = t;
if (g != t) son[t][1] = g;
if (f) cut(t, f);
if (s) cut(t, s);
if (s) link(s, f);
if (g != t) link(g, t);
return ans;
}
int splaymax() {
int t = (--St.end())->second;
int ans = deep(t);
if (root == t) return ans;
int f = fa[t], g = root, s = son[t][0];
if (f) son[f][1] = s;
if (s) fa[s] = f;
fa[t] = 0;
root = t;
if (g != t) fa[g] = t;
if (g != t) son[t][0] = g;
if (f) cut(t, f);
if (s) cut(t, s);
if (s) link(s, f);
if (g != t) link(g, t);
return ans;
}
int deletemin() {
int t = St.begin()->second;
int ans = splaymin();
root = son[t][1];
if (root) fa[root] = 0;
if (root) cut(t, root);
St.erase(St.begin());
return ans;
}
int deletemax() {
int t = (--St.end())->second;
int ans = splaymax();
root = son[t][0];
if (root) fa[root] = 0;
if (root) cut(t, root);
St.erase(--St.end());
return ans;
}
}
using namespace lct;
int main() {
int n, ans; scanf("%d", &n);
while (n--) {
int x, y; scanf("%d", &x);
if (x == 1) scanf("%d", &y), ans = insert(y);
else if (x == 2) ans = splaymin();
else if (x == 3) ans = splaymax();
else if (x == 4) ans = deletemin();
else if (x == 5) ans = deletemax();
printf("%d\n", ans);
}
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2018 Anoxiacxy All Rights Reserved.

UV : | PV :