T1 锻造 Forging

1 记录

考场上的时候总觉得题目非常的奇妙

因为一直循环下去不就完了吗?

直到后来我的同桌给我指点，原来把 DP 式子当方程解可以了

还是太菜啊

T1 Attack

1 记录

考场上时懵的，这是个啥？为什么没有部分分？

弃了

Kruskal 重构树

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

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

这就是 Kruskal 重构树

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

• 没有 边权
• 保证是一个堆
  • 大根堆还是小根堆要看 原来 生成的是最小还是最大生成树
  • 因为我们保证边权的单调性，故后期新建节点的点权也是单调的，故新树是一个堆

1 最小生成树

1.1 生成树

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

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

1.2 最小生成树

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

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

1.3 求解算法

• Kruskal 算法
• Prim 算法

可重组合

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

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

证明

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

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

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

即