项目链接: https://github.com/woshiluo/server_uptime

1 为什么会有这个项目

NovaOJ 的服务器在乌市一中的内网，笔者身为 Oier，不可避免的有去内地培训的情况出现，无法保证及时得知内网的情况

然而市面上绝大多数服务监控通常都支持公网（至少我是只找到了公网的按钮）

轮子好像是有的，但是我 Python 功底薄弱，迫于要搞 Oi，没有时间学习新语言

那就造新轮子吧！

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 算法