洛谷P5247 动态图完全连通性 LCT解法

jerry3128 和 zghtyarecrenj 大佬都讲得很好，但是漏了一些细节。这里简单补充一点。 Holm-de Lichtenberg-Thorup 算法的原始论文：https://u.cs.biu.ac.il/~rodittl/p723-holm.pdf 算法的简化描述如下。 给边分层， ...
2021-11-20

luogu P4332 [SHOI2014]三叉神经树 LCT

将节点的值定义为其输入中1的个数。观察发现，每次修改的都是一条链上的值：如果是将某个节点的值从1改成0，那么就是要将这个节点到其祖先中离该节点最近的值非2的节点的值全部减一，如果是将某个节点的值从0改成1，那么就是要将这个节点到其祖先中离该节点最近的值非1的节点的值全部加1。 所以维护splay表示 ...
2021-11-18

rust用BufReader加速stdin读取

BufReader官方文档：https://doc.rust-lang.org/stable/std/io/struct.BufReader.html use std::io::{self, BufRead, BufReader}; let mut cin = BufReader::new(io: ...
2021-11-17

Hexo插入图片

有两种方案，一种是把图片弄到图床上，一种是把图片直接放到博客所在的网站上，然后做一个站内引用。这里主要介绍后者。 先在_config.yml里把post_asset_folder设置成true，这样在建立文件时，Hexo会自动建立一个与文章同名的文件夹；以前的文章也可以自己手动创建同名文件夹。其实也 ...
2021-11-16

Hexo tree主题让文章的URL中不含目录

默认设置中，文章的URL的格式是域名/20xx/xx/xx/目录/子目录1/子目录2/文章名，这样的坏处是修改文章目录的时候，文章的URL会变，如果这个URL已经分享给别人的话，别人就会发现这是一个死链。 要让文章的URL中不含目录，只需要将_config.yml里的permalink从:year/ ...
2021-11-16

Hexo支持Latex风格的公式编辑

¶ 方案一（推荐）：hexo-filter-mathjax + hexo-renderer-pandoc hexo-filter-mathjax官方教程：https://github.com/next-theme/hexo-filter-mathjax hexo-renderer-pandoc官方教 ...
2021-11-16

luogu P5388 最终幻想 母函数

yamengxi大佬写了一个优美的公式，但是没有给出证明。时隔两年，本蒟蒻终于可以帮大佬补个证明了。 假设答案是，那么根据c__z__a的题解，可以得到以下递推表达式： 下面用母函数来求的通项。设 那么有 时，有 所以 的第项是，的第项是，所以的第项是，所以的第项是 所以的第项是 ...
2021-11-15

algorithm2e无限循环

\documentclass{article} \usepackage{algorithm2e} \begin{document} \thispagestyle{empty} \SetKwFor{Loop}{Loop}{}{EndLoop} \begin{algorithm} \Loop{} ...
2021-11-14

最大流算法复杂度分析

¶ Ford-Fulkerson算法(1956) 非常简单，直接在残量网络上dfs找到一条增广路，然后更新残差图，不断重复，直到找不到增广路。然后得到的就是最大流。 如果所有的边的容量都是0到U的整数，那显然最大流最大是nU。每次增广都至少使得总流量增加1，所以最多有nU次增广。找增广路的复杂度是， ...
2021-11-11

LCT感性理解

LCT是用来维护有根树森林的，要支持以下操作。 make-tree(v)：让节点v单独变成一个有根树。 link(v, w)：把v挂在w上。 cut(v, w)：让v不再是w的子节点。 find-root(v)：找到v所在的树的根。 find-root(v)的时候，如果直接用原来的有根树，那就要 ...
2021-11-10
1…2627282930…66