T1 小 L 的数列
1 记录
考场上推出来了
没判 $ n < q $ 难受
Continue reading “中山纪念中学 Day 7 2019.08.07 解题报告 & 题解”基于 PHP 的站点存活监测项目 一点笔记
1 为什么会有这个项目
NovaOJ 的服务器在乌市一中的内网，笔者身为 Oier，不可避免的有去内地培训的情况出现，无法保证及时得知内网的情况
然而市面上绝大多数服务监控通常都支持公网（至少我是只找到了公网的按钮）
轮子好像是有的，但是我 Python 功底薄弱，迫于要搞 Oi，没有时间学习新语言
那就造新轮子吧！
Continue reading “基于 PHP 的站点存活监测项目 一点笔记”中山纪念中学 Day 4 2019.08.04 解题报告 & 题解
T1 锻造 Forging
1 记录
考场上的时候总觉得题目非常的奇妙
因为一直循环下去不就完了吗?
直到后来我的同桌给我指点，原来把 DP 式子当方程解可以了
还是太菜啊
Continue reading “中山纪念中学 Day 4 2019.08.04 解题报告 & 题解”Kruskal 重构树入门 – 「NOI 2018」 归程
Kruskal 重构树
在 Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中，介绍了 Kruskal 算法是如何生成最小生成树的
如果将两个联通块联通的不是边而是点呢？
这就是 Kruskal 重构树
具体来说就是，我们原来是通过一条边将两个联通块相连接的，现在我们新建立一个点，将这两个联通块的根节点连接到这个点上，原来的边权就是这个新建节点的点权，这样执行下来，我们会得到一棵新的树，这个树有以下两个特征
- 没有 边权
- 保证是一个堆
- 大根堆还是小根堆要看 原来 生成的是最小还是最大生成树
- 因为我们保证边权的单调性，故后期新建节点的点权也是单调的，故新树是一个堆
Kruskal 最小/大生成树 — Luogu P1967 货车运输
1 最小生成树
1.1 生成树
无向图 $G$ 的生成树，就是具有图 $G$ 的所有顶点，但是边数最小的联通子图
更加详细的定义: Wikipedia – 生成树
1.2 最小生成树
带权联通无向图的总权值最小的生成树
更加详细的定义: Wikipedia – 最小生成树
1.3 求解算法
- Kruskal 算法
- Prim 算法
Luogu P2624 [HNOI2008]明明的烦恼
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$ 为已知点数
Prufer序列 入门 — P2290 [HNOI2004]树的计数
0 前置知识点
- 排列组合
- 高精度 / 分解质因数
1 Prufer 序列
对于一个带编号的无根树，其 Prufer 序列按以下过程处理
- 选取所有节点中度数最小编号最小的一个节点
- 输出其相邻的编号
- 回到 1 ，直到只剩两个节点为止
每个 Prufer 序列，都对应唯一的一个带编号的无根树
Continue reading “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
$$