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

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

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

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

前言

最近发现网络流只会板子不会模型转换，于是来做网络流 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)$，我们不能承受。

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

很容易看出这是宽度优先搜索，因为要求步数最少，且每个操作代价相同。

我们可以按操作类别分 6 种情况扩展，如果搜到最终状态就跳出 BFS（搜索顺序可以随意，因为 spj 已经配置好了，不像数据修改前要有特定的顺序）。

记得标记已经出现过的情况，不然会 TLE/MLE；