欢迎来到我的个人主页，Have a good time! ヾ(≧▽≦*)o

于 2018/4/21，终于借助 Hexo 和 Coding 的页面托管服务将个人主页搭建完毕。

于 2019/1/28，更新主题并换用 Netlify 托管。

P.S. 如果有谁想一起建个人主页的，可以通过”关于”联系我一起探讨，顺便交换一下友链蛤

最近折腾了一下 Arch Linux，写一篇安装教程纪念一下。

环境为 HP Notebook x86_64，UEFI。

前言

最近发现网络流只会板子不会模型转换，于是来做网络流 24 题。

本文代码以 LibreOJ 上的数据为准，Luogu 的题面可能稍有不同。

本文不定时更新。 （有可能永久咕咕咕）

前言

作为 Windows 用户，常羡慕 Linux 用户高端大气的终端。

其实，Windows 自带的 PowerShell 也十分的强大。

但是过于简陋的界面不知道劝退了多少用户，于是让我们来美化一下 PowerShell 吧。

以下教程环境均为 PowerShell 5.x。

首先我们要知道这道题的原型是「NOI2014」起床困难综合症。

总是有出题人喜欢把序列上用线段树解决的题目出到树上，让选手强行写个树链剖分或树分治或某种动态树数据结构。

序列问题转化为树上问题，很容易想到树链剖分，直接上板子。

我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$，于是根据取模的性质，我们可以把原式两边同乘九再加一、原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$，发现这是个 BSGS 的标准式子，由于$m$保证为质数，所以也不必用拓展 BSGS。

作为一道英文题，我们先解释一下题意：

给你一棵树和它的一个 BFS 序，让你判断这个 BFS 序是否是一个从节点 1 开始的合法 BFS 序。

接下来我们进入正题。

第一眼看到这题时，大部分人都会想到，既然是树，那么它一定是一层一层地向下 BFS。

也就是说，BFS 序中越后出现的节点，它树上的深度肯定是大于它前面的节点的。

于是照这个思想打完后，发现 Wrong Answer 了。

这道题第一眼像是合并果子，我们考虑贪心。

我们先选择一种贪心策略：每次选当前最大的两个数合并，直到只剩最后一件物品。

接下来我们证明一下为什么这样是对的：

我们先想一想合并果子，那道题的贪心策略与这道题相反，每次选最小的两个数合并。考虑它为什么是对的——我们发现越先选的数对结果的贡献越大，为了使结果尽可能小，肯定是越小的先选越好。

作为一道英文题，我们先解释一下题意：

给你一个长度为 $n$ 的 01 串，其中可能至少有 $t_{i}$ 个 1，问最后你给出一个 01 串可能和其匹配的最大长度。

接下来我们进入正题。

第一眼看见觉得是水题，对于每个$t_{i}$枚举应该全 0 还是全 1，但是这显然可以找出反例来。

由题意得一个点对的联合权值是它们的点权相乘，而 2 个点形成点对的条件是距离为 2。

于是我们可以通过枚举这 2 个节点的公共点来算出以这个点为中心的权值和。

但是先枚举中心点再枚举其相邻的节点时间复杂度达到了$O(n^3)$，我们不能承受。

经过观察发现，对于特定的点，它都要乘上除自己以外的所有点权，再相加。然后我们就可以先处理出点权和，统计答案的时候把自己减去即可。