Home

二叉树打印模板

该代码仅作为赛时模板使用,为了方便调试信息,以反转区间为例。 #include <iomanip> #include <iostream> #include <vector> using namespace std; const int N = 1e5 + 10; struct Node { int val; int son[2], par; int sz; int tag; void init(int v, int p) { val = v; par = p; son[0] = son[1] = 0; sz = 1; tag = 0; } } T...

Read more

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...

Read more

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]...

Read more

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 =...

Read more

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...

Read more

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; ...

Read more

树上启发式合并(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]; } 复杂度分析 可以参考之前发布的 重链剖分 在重链剖分的时间...

Read more

重链剖分

前置知识 线段树 (树链剖分的主要依托) LCA (树链剖分可以解决的一个问题 | 可以边学变了解) DFS序 图 基本概念 如图所示, 这是一张随机的树。 我们以任一结点作为子树的根,那么对于这个树而言,其结点数量最多的子树的根,我们称之为 重子树。 例如图中的树来说。对于以 9 号结点为根的子树来说,我们结点最多的子树是以 3 作为根的子树。 对于重子树而言,其根我们称之为 重儿子。 我们将根不断的和重儿子形成的链,我们称之为 重链。 相对不是重的,我们则称之为 轻 有了这个我们就可以看图中的例子了。 我们从 6 号结点出发,我们的重儿子是 9 ,9 的重儿子是 2, 2 的重儿子是 5,因此我们就形成了 [6 ,9 ,2 ,5] 这样的...

Read more

This is my site

welcome!