Woshiluo's Notebook

Prufer序列入门 — P2290 [HNOI2004]树的计数

2019年6月2日2019年6月2日 by woshiluo

0 前置知识点

排列组合
高精度 / 分解质因数

1 Prufer 序列

对于一个带编号的无根树，其 Prufer 序列按以下过程处理

选取所有节点中度数最小编号最小的一个节点
输出其相邻的编号
回到 1 ，直到只剩两个节点为止

每个 Prufer 序列，都对应唯一的一个带编号的无根树

可重组合与不相邻组合

2019年6月2日2019年6月2日 by woshiluo

可重组合

从 ${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 从入门到卸载客户端

2019年5月31日2019年6月7日 by woshiluo

0 说在之前

RSS 一说起这个词语，绝大多数人想到的都是 10 年以前，一行行字母，没有任何样式的网页，跟现今比起来，几乎没有任何的优势

故此我们总是觉得，RSS 已经成为了时代的眼泪，但是 RSS 的核心便是流，信息流，这和当下的媒体传播方式并无二，故只要运用得当，RSS 并不过气

Atom 上手指北

2019年5月26日2019年6月7日 by woshiluo

0 缘起

在 Luogu 日报上看到一篇 Atom小清新上手指南，经过了一番适应与调教，感觉十分优秀

不过多数这种自定义性极高的软件，通常都需要很多插件与一些配置，特写此文，留作自用

若能帮助到有需要的人，那是最好的

CTS&APIO2019游记

2019年5月18日2019年7月2日 by woshiluo

自闭了，自闭选手不配拥有游记

Luogu P2607 [ZJOI2008]骑士

2019年5月9日2019年5月9日 by woshiluo

题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单，给你一张图，然后图中不能选最大相邻点，最后最大的选中的点的权值

很容易想到没有上司的舞会这种树形 DP 题目，但是显然，这，并不是一棵树

根据题目可得，每一个人只会有一条出边，即，这张图中，一张节点个数为 $n$ 的联通块，会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边，删掉后就是树了

设这条边为 $u – v$ 的边，则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ，当反向边即可

SA 后缀数组入门 — Luogu P3809 【模板】后缀排序

2019年5月8日2019年5月8日 by woshiluo

题目链接: https://www.luogu.org/problemnew/show/P3809

后缀数组

后缀数组用于解决各种玄学字符串问题，准确来说，它是一种思想

基于后缀数组有很多好玩毒瘤的东西

目前已知的求后缀数组的方法有

倍增法 (本博客所讲述) — $O(n \log(n))$
DC3 — $O(n)$
- DC3 虽然从复杂度分析的角度而言比倍增快，但配合各种常数问题，在信息学竞赛中反而容易被卡……
SA – IS 算法 — $O(n)$
- 可以参考这篇 Luogu 日报: https://www.luogu.org/blog/ShadowassIIXVIIIIV/on-hou-zhui-shuo-zu-sa-is-suan-fa

因为我太菜了，所以我就讲倍增求法