0 前置知识点
- 排列组合
- 高精度 / 分解质因数
1 Prufer 序列
对于一个带编号的无根树,其 Prufer 序列按以下过程处理
- 选取所有节点中度数最小编号最小的一个节点
- 输出其相邻的编号
- 回到 1 ,直到只剩两个节点为止
每个 Prufer 序列,都对应唯一的一个带编号的无根树
Continue reading “Prufer序列 入门 — P2290 [HNOI2004]树的计数”「Jump up HIGH!!」
对于一个带编号的无根树,其 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 上手指北”自闭了,自闭选手不配拥有游记
题目意思非常简单,给你一张图,然后图中不能选最大相邻点,最后最大的选中的点的权值
很容易想到 没有上司的舞会 这种树形 DP 题目,但是显然,这,并不是一棵树
根据题目可得,每一个人只会有一条出边,即,这张图中,一张节点个数为 $n$ 的联通块,会有 $n$ 条边
环套树没得跑了
即每一个联通块中一定有一条边,删掉后就是树了
设这条边为 $u – v$ 的边,则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案
建双向边判环即可
至于代码中的 xor ,当反向边即可
Continue reading “Luogu P2607 [ZJOI2008]骑士”后缀数组用于解决各种玄学字符串问题,准确来说,它是一种思想
基于后缀数组有很多好玩毒瘤的东西
目前已知的求后缀数组的方法有
因为我太菜了,所以我就讲倍增求法
Continue reading “SA 后缀数组入门 — Luogu P3809 【模板】后缀排序”题目链接: https://oj.woshiluo.site/problem/2055 / https://www.luogu.org/problemnew/show/P5323
我看到题目的一瞬间
我是在学 oi 还是在学物理?
然后我仔细思考了一下,这两个镜子来回反射,您这是要求极限?
然后我仔细思考了一下
设 $f_i$ 为从 $1$ 到 $i$ 的透光率,$g_i$ 为从 $i$ 到 $1$ 的反光率
Continue reading “「BJOI2019」光线”题目链接: https://www.luogu.org/problemnew/show/P3174
这应该是我第一次没看 sol 做紫题吧……
虽然个人感觉比大多数紫题简单许多
题目本质是要求最长链的,但是要求是带每个点周围点的
我们设每个点的点权是这个点的连接点个数减 1
然后求最长链
得出来的链的长度 +2 即为答案
可以理解为因为大多数点都有一条边要连出去防止重复计算而减一
但是这样链头链尾会没算上,所以加二
Continue reading “Luogu P3174 [HAOI2009]毛毛虫”从 c0per 那边白嫖了一个蓝牙耳机(深得 LTT 真传)
但是服务器上并没有蓝牙…
这怎么可以…然后我找到了一个蓝牙适配器
蓝牙 v2.0?貌似还能用?
但是音效爆炸了
Continue reading “Debian 有关蓝牙耳机的配置”