Kruskal 重构树入门 – 「NOI 2018」 归程

Kruskal 重构树

Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中,介绍了 Kruskal 算法是如何生成最小生成树的

如果将两个联通块联通的不是边而是点呢?

这就是 Kruskal 重构树

具体来说就是,我们原来是通过一条边将两个联通块相连接的,现在我们新建立一个点,将这两个联通块的根节点连接到这个点上,原来的边权就是这个新建节点的点权,这样执行下来,我们会得到一棵新的树,这个树有以下两个特征

  • 没有 边权
  • 保证是一个堆
    • 大根堆还是小根堆要看 原来 生成的是最小还是最大生成树
    • 因为我们保证边权的单调性,故后期新建节点的点权也是单调的,故新树是一个堆
继续阅读“Kruskal 重构树入门 – 「NOI 2018」 归程”

Kruskal 最小/大生成树 — Luogu P1967 货车运输

1 最小生成树

1.1 生成树

无向图 $G$ 的生成树,就是具有图 $G$ 的所有顶点,但是边数最小的联通子图

更加详细的定义: Wikipedia – 生成树

1.2 最小生成树

带权联通无向图的总权值最小的生成树

更加详细的定义: Wikipedia – 最小生成树

1.3 求解算法

  • Kruskal 算法
  • Prim 算法
继续阅读“Kruskal 最小/大生成树 — Luogu P1967 货车运输”

Luogu P2624 [HNOI2008]明明的烦恼

题目链接: https://www.luogu.org/problemnew/show/P2624

0 前置技能

1 推式子时间

这个题目很像 Luogu P2290

但是问题在于,这个里面具有不确定的度数

经过简单的思考,我们可以得出以下式子
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!} \times (n – cnt) ^{n – sum – 2}
$$
其中

  • $sum$ 为已知总度数
  • $cnt$ 为已知点数
继续阅读“Luogu P2624 [HNOI2008]明明的烦恼”

Prufer序列 入门 — P2290 [HNOI2004]树的计数

0 前置知识点

1 Prufer 序列

对于一个带编号的无根树,其 Prufer 序列按以下过程处理

  1. 选取所有节点中度数最小编号最小的一个节点
  2. 输出其相邻的编号
  3. 回到 1 ,直到只剩两个节点为止

每个 Prufer 序列,都对应唯一的一个带编号的无根树

继续阅读“Prufer序列 入门 — P2290 [HNOI2004]树的计数”

可重组合与不相邻组合

可重组合

从 ${1, 2, 3 \cdots, n – 1, n}$ 中选出 $m$ 个元素,可以重复,有多少个不同的组合?

答案 $C_{n + m – 1}^{m}$

证明

显然,问题可以转换为 $m$ 个球放入 $n$ 个盒子,可以放无数个或者不放

即插入 $n – 1$ 个隔板,然后求全排列 $(m + n – 1)!$

但是隔板和球的顺序是无效的所以除去 $m! \times (n-1)!$


$$
\frac{(m + n – 1)!}{m! \times (n – 1)!} = C_{n + m -1}^m
$$

继续阅读“可重组合与不相邻组合”

RSS 从入门到卸载客户端

0 说在之前

RSS 一说起这个词语,绝大多数人想到的都是 10 年以前,一行行字母,没有任何样式的网页,跟现今比起来,几乎没有任何的优势

故此我们总是觉得,RSS 已经成为了时代的眼泪,但是 RSS 的核心便是流,信息流,这和当下的媒体传播方式并无二,故只要运用得当,RSS 并不过气

继续阅读“RSS 从入门到卸载客户端”

Luogu P2607 [ZJOI2008]骑士

题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单,给你一张图,然后图中不能选最大相邻点,最后最大的选中的点的权值

很容易想到 没有上司的舞会 这种树形 DP 题目,但是显然,这,并不是一棵树

根据题目可得,每一个人只会有一条出边,即,这张图中,一张节点个数为 $n$ 的联通块,会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边,删掉后就是树了

设这条边为 $u – v$ 的边,则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ,当反向边即可

继续阅读“Luogu P2607 [ZJOI2008]骑士”

SA 后缀数组入门 — Luogu P3809 【模板】后缀排序

题目链接: https://www.luogu.org/problemnew/show/P3809

后缀数组

后缀数组用于解决各种玄学字符串问题,准确来说,它是一种思想

基于后缀数组有很多好玩毒瘤的东西

目前已知的求后缀数组的方法有

因为我太菜了,所以我就讲倍增求法

继续阅读“SA 后缀数组入门 — Luogu P3809 【模板】后缀排序”