Linge_Zzzz's Boker

定义 我们先来定义什么是闭合子图。 通俗地讲，在一个有向图中，我们选择一些点作为一个点集。若这个点集中任何一个点所能到达的所有点都在这个点集中，我们称这个点集是一个闭合子图。 例如，在上图中，$\{5\},\{2,3,4,5\},\{1,2,3,4,5\}$ 都是这个图的闭合子图。而 $\{2,4,5\}$ 则不是，因为 $3$ 可以到达 $4$，而 $4$ 不在这个点集中。 现在，每个点有一个点权 $w_i$，$w_i$ 可以是负数，我们要选择一个最大权闭合子图 $S$ 来最大化 $\sum_{u\in S}w_u$，即选择一个点权和最大的闭合子图。 建模方法 我们考虑把它转化成网络流中的最小割来解决。 具体地，建立超级源点 $S$ 和超级汇点 $T$。 对于原图中的边，我们保留，并把其容量设为 $\inf$。 对于每个原图中的点 $u$：若 $w_u>0$ 则从 $S$ 向 $u$ 连一条容量为 $w_u$ 的边。若 $w_u<0$ 则从 $u$ 向 $T$ 连一条容量为 $-w_u$ 的边。若 $w_u=0$，我们不管他。（也可以管，但是容量为 $0$ 就相 ...

定义 我们现在有一个长为 $n$ 的字符串 $s$，我们定义这个字符串的后缀 $i$ 表示 $s[i,n]$。 现在，我们要对 $s$ 所产生的 $n$ 个后缀进行排序，得到第 $i$ 个后缀是第几名，我们记其为 $rk_i$。同时，我们还能得到第 $i$ 名的是哪个后缀，记为 $sa_i$。 如何求 SA 暴力 我们有一种极其暴力的做法，把这 $n$ 个后缀存下来，再排序。总共有 $O(n\log n)$ 次比较，每次比较最坏 $O(n)$，则复杂度是 $O(n^2\log n)$，遥遥落后。 倍增法 我们换一种思路：每次计算长度为 $w$ 的所有子串的排名，这样就可以通过合并排名来统计答案，为此，我们修改一下定义： 假设当前考虑的子串长度为 $w$，对于在结尾不足 $w$ 位的子串，我们给它补上当前字符集中最小的字符（实现中是值 $0$）。这样，我们就一共有 $n$ 个长为 $w$ 的子串了。 $rk_i$ 表示 $s[i,i+w-1]$ 在这 $n$ 个长为 $w$ 的子串中的排名。$sa_i$ 类似。 我们从 $w=1$ 的情况开始考虑。此时显然我们可以轻而易举地计算出 $rk ...

简介 如题，是一个可以便捷生成图论中各种图的工具。 下载 & 安装 链接 自己选适合自己操作系统的版本。 安装以 Windows 为例，其实也没什么要注意的点，把 “Add Graphviz to the system PATH” 中的任意一个勾上就行了。 命令行试试 dot -V，如果有输出说明安装成功，没输出检查一下勾没勾上上述选项。 配置 以 VSCode 为例。 插件搜索 Graphviz，安装 Graphviz Interactive Preview 和 Graphviz (dot) language support for V。 前者是用于实时生成预览图，后者提供语法高亮。 教程 Graphviz 源文件的扩展名是 .dot。所以我们在 VSCode 中新建一个 .dot 文件。你会发现右上角有一个小图标，点开它，就有了预览界面。 先试着写一点简单的图： 123digraph { A -> B} 其中，digraph 定义了一个有向图，这个有向图里有 A 和 B 两个结点，其中 A 向 B 连了一条有向边。 12345digraph ...

定义 约定记号 $s[l,r]$ 代表从 $l$ 到 $r$ 的子串。 $\pi$ 函数 对于一个字符串 $s$，它的 $\pi$ 函数是它的前缀和后缀相等的最长长度。 $$ \pi=\max_{s[1,i]=s[n-i+1,n]} i $$ 进一步，我们定义 $\pi_i$ 是字符串前 $i$ 个字符组成的子串的 $\pi$ 函数值。特别的，定义 $\pi_1 =0$。 下面我们考虑如何求出 $\pi$ 数组。 对于 $\pi_1=0$ 是确定的，考虑递推。 假设我们当前求出了 $\pi_1,\pi_2,\cdots,\pi_i$ 要求出 $\pi_{i+1}$。 有一个特殊情况，如果 $s[\pi_i+1]=s[i+1]$，那么 $pi_{i+1}=\pi_i+1$。 根据 $\pi$ 函数定义，$s[1,\pi_i]=s[i-\pi_i+1,i]$，那么如果 $s[\pi_i+1]=s[i+1]$，就有了 $s[1,\pi_i+1]=s[i-\pi_i+1,i+1]$，进而有 $\pi_{i+1}=\pi_i+1$。 下面考虑当 $s[i+1]\ne s[\pi_i+1]$ 时的 ...

前情提要CSP关于 CSP 没什么好说的，A 切了，B 35pts 暴力之后跑路。 C 一看，第一次遇见大模拟，有点害怕，草草写了个 15pts 性质分跑路了，然后一直在做 D 题。 总之就是很飞舞，D 题暴力挂了，C 挂了 10 pts，最后只有 140 分。 压线 6 级勾，有点惊喜但不多，可以参加 NOIP。 NOIPA 切了，B 看了之后有点害怕，以为是什么 Tarjan 图论题。 因为我 Tarjan 学得不好所以打了个部分分草草了事 我为什么没看见暴力分？我为什么没看见暴力分？我为什么没看见暴力分？ C 题更害怕，做了个特殊性质。 我为什么没看见暴力分？我为什么没看见暴力分？我为什么没看见暴力分？ D 题，是个 DP，感觉很可做诶，写了个 $O(n^2)$ DP，后面不会优化了，跑路。 最后只有 146 分，大失败，这也是为什么我在这之后的比赛基本不想正解，只打部分分。 Day -3是一个省选模拟赛。 上来看 A，什么抽象题面，转去看 B，发现有 59 分是送的，赶紧写了。 读了 A，暴力思维难度较大，于是看 C，发现有 21 分是送的，赶紧写了。 后面就是 A 和 C 交 ...

这是一个自我介绍

This is a testing article. $$ 若a,b>0，则 a+b \ge 2\sqrt{ab} $$