Splay 模板
Splay 数组实现模板
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Node {
int son[2], p;
int sz, cnt;
int val;
void init(int v, int par) {
val = v, p = par;
sz = 1;
cnt = 1;
son[0] = son[1] = 0;
}
} Tree[N];
int root = 0;
// Splay
void update_size(int p) {
Tree[p].sz = Tree...
2022 牛客多校第四场题解
D - Jobs (Easy Version)
有 $n(n \le 10)$ 个公司,每个公司有 $k$ 个职位。每个职位都有三维[a , b , c]的要求,现在有 $q$ 名求职者,每个求职者的三维必须大于等于需要的职位的三维才可以被采纳。
求问,每个求职者最多可以收到几家公司的 offer。
由于本人的能力有限,只给出 Easy Version 的解。
在这个问题中,我们发现题目的突破口是在 [a , b , c] 的范围,他们最大的值仅有 400, 因此我们不妨通过设置 need[i][a][b] 来表示这样的值,在公司 $i$ ,能力值为 $a$ , $b$ 且可以被公司接纳的情况下,的情况下,$c$ 的最小值。
然后对于一个公司而言,我们可以得到 need[i]...
Treap 模板
此篇仅仅作为模板使用,以 普通平衡树 为例题完成。
旋转Treap | 指针实现
#include <ctime>
#include <iostream>
#include <random>
using namespace std;
signed gen() {
static mt19937 mt(time(0));
static int cnt = 0;
cnt++;
if (cnt == 1e5) {
cnt = 0;
mt.seed(time(0));
}
return mt();
}
struct Treap {
public:
Treap() { root =...
2022 牛客多校第二场题解(D)
D - Link with Game Glitch
题目简单的翻译过来就可以是,给定一个有向图,每条边都有边权,每次走过这条边就需要将手里的值乘上一个数。给定一个数字 $w$ ,并将每条边的权乘上 $w$ ,求问最大的 $w$ 使得这个图不存在可以走到 $+\infty $ 。
首先,我们很容易想到二分的思路。
具体过程详见下面代码。
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
vector<pair<int, double>> E[N];
long double value[N];
bool vis[N];
i...
2022 牛客多校第一场题解(ACDGIJ)
A - Villages: Landlines
题意简述,给出一些区间,求取最多添加多长的区间使得这些区间合并。
非常简单,按题意模拟即可。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> v(n);
for (auto &[x, y] : v) {
int m, r;
cin >> m >> r;
...
树上启发式合并(DSU on Tree)
算法发明者的第一题
OI Wiki
简单的介绍
什么是启发式合并?
启发式合并,是一种基于 直觉 的奇特算法。
通常来说,我们需要按 秩 合并,这个秩可以有两种意思,一个是集合大小,一个是树的高度。
我们总是将秩小的那个合并到大的那个中,这样的话,我们就可以以一种较为简洁的方式将树,尽量的往 扁 的方向合并。
假如以并查集为例,我们通常可以这样子合并。
void merge(int x,int y) {
x = find(x) , y = find(y);
if(sz[x] < sz[y]) swap(x , y);
fa[y] = x;
sz[x] += sz[y];
}
复杂度分析
可以参考之前发布的 重链剖分
在重链剖分的时间...
55 post articles, 7 pages.