T1 锻造 Forging
1 记录
考场上的时候总觉得题目非常的奇妙
因为一直循环下去不就完了吗?
直到后来我的同桌给我指点,原来把 DP 式子当方程解可以了
还是太菜啊
Continue reading “中山纪念中学 Day 4 2019.08.04 解题报告 & 题解”「Jump up HIGH!!」
考场上的时候总觉得题目非常的奇妙
因为一直循环下去不就完了吗?
直到后来我的同桌给我指点,原来把 DP 式子当方程解可以了
还是太菜啊
Continue reading “中山纪念中学 Day 4 2019.08.04 解题报告 & 题解”在 Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中,介绍了 Kruskal 算法是如何生成最小生成树的
如果将两个联通块联通的不是边而是点呢?
这就是 Kruskal 重构树
具体来说就是,我们原来是通过一条边将两个联通块相连接的,现在我们新建立一个点,将这两个联通块的根节点连接到这个点上,原来的边权就是这个新建节点的点权,这样执行下来,我们会得到一棵新的树,这个树有以下两个特征
无向图 $G$ 的生成树,就是具有图 $G$ 的所有顶点,但是边数最小的联通子图
更加详细的定义: Wikipedia – 生成树
带权联通无向图的总权值最小的生成树
更加详细的定义: Wikipedia – 最小生成树
这个题目很像 Luogu P2290
但是问题在于,这个里面具有不确定的度数
经过简单的思考,我们可以得出以下式子
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!} \times (n – cnt) ^{n – sum – 2}
$$
其中
对于一个带编号的无根树,其 Prufer 序列按以下过程处理
每个 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
$$
RSS
一说起这个词语,绝大多数人想到的都是 10 年以前,一行行字母,没有任何样式的网页,跟现今比起来,几乎没有任何的优势
故此我们总是觉得,RSS 已经成为了时代的眼泪,但是 RSS 的核心便是流,信息流,这和当下的媒体传播方式并无二,故只要运用得当,RSS 并不过气
Continue reading “RSS 从入门到卸载客户端”在 Luogu 日报上看到一篇 Atom小清新上手指南 ,经过了一番适应与调教,感觉十分优秀
不过多数这种自定义性极高的软件,通常都需要很多插件与一些配置,特写此文,留作自用
若能帮助到有需要的人,那是最好的
Continue reading “Atom 上手指北”自闭了,自闭选手不配拥有游记