泪痕@一语成谶
辗转当作浮生妖,流离惊似尘世鬼
Splay 初步 Splay 初步
2019.6.19 编入精选文章。 前言 平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了
2018.12.19
从树套树浅析常用结构的特性 从树套树浅析常用结构的特性
摘要 2019.6.18 编入精选文章 作者严正声名:本文比较沙雕。 另外,本文并不是 “树套树入门” 的文章,而是一篇议论性文章。议论性文章是指可能内容较受争议。 在我写这文章的时侯,输入法:蜀涛数,树桃树,树套数…… emm 就是没有树
2019.06.17
后缀数组 后缀数组
摘要 后缀数组由 Manber & Myers 在 1990 年首先提出《Suffix arrays: a new method for on-line string searches》,用以替代后缀树,并且改进了存储空间的需求。
2018.10.01
AC 自动机 ·Automaton AC 自动机 ·Automaton
摘要 之前洛谷日报上发了一篇《强势图解 AC 自动机》,现在复习一下,重新整理思路 2019.6.16:编入精选文章 前言声明:代码部分的字符串都以 1 为起点 另外,有小伙伴问我 GIF 图片是怎么生成的。在此我以个人名誉担保—— 这
2018.10.01
容斥原理入门 容斥原理入门
摘要 啃论文系列~ 考容斥原理本身的题不多,容斥原理常用于某个算法部分的求值。 2019.6.16 编入精选文章。 入门 某班有 a 歌人擅长唱歌,b 个人擅长画画,c 个人既擅长唱歌也擅长画画,问有多少人至少有一种擅长? 发挥你聪明的大
2019.04.25
博弈论 博弈论
摘要 博奕论,一门高深的学问。 2019.6.15 编入精选文章。 dls 讲博弈论:“你掉线,我随意” 博弈的分类博弈大体分为平等博弈和不平等博弈。平等博弈指双方的决策集等价,不平等博弈则指双方决策集不等价。 常见的平等博弈则则是 I
2018.12.13
网络流入门之费用流 网络流入门之费用流
摘要 之前写的《网络流初步》内容太多,因此单独分一个费用流出来。本文的内容可能涉及到《网络流入门之最大流》的内容,建议先食用后者。 2019.6.15 编入精选文章 费用流给定一个网络 ,每条边除了有容量限制 $c(u,
2019.05.03
最短路应用 最短路应用
摘要 本文接上文 最短路算法,为大家介绍最短路的常见应用。 将原来打的各种题目的零散文章汇总,编入精选文章。 负环与差分约束一个看起来不像最短路的最短路应用。给出一组差分约束,问是否有解。差分约束是形容
2019.06.15
最短路算法 最短路算法
摘要 复习一下模板 2019.6.4:编入精选文章 图的最短路,指的是在一个加权图 G 中某两点相距的最短路程的长度(有时要求记录路径)。 严格地说,最短路分有向与无向两种。有向的最短路强调起点和终点的区别,而无向的最短路则只需要连接两点
2018.12.05
网络流入门之最大流 网络流入门之最大流
摘要 网络流是强有力的图论算法之一,其算法本身不难,但是所解决的问题却千变万化。简而言之,网络流的难点在于建模。本文则注重讲解网络流的最大流算法。 2019.6.14:收编精选文章。 网络网络是指一个有向图 . 每条边
2018.12.21
博客转型计划 博客转型计划
摘要 再小的星星也有光芒 没错!你现在看到的是 Sshwy 大菜鸡的一个计划! 心的起始每个人都是有故事的,也是有追求的。在 OI 这条路上,学习知识的时侯大多数人估计直接奔 OIWIKI 了,包括我。那么,为什么我要写这个博客?并不是单
2019.06.14
Hexo 博客搭建 + Github 配置 + 域名配置 Hexo 博客搭建 + Github 配置 + 域名配置
摘要 Hexo 作为一款轻量级的静态博客博客框架,本身访问的速度很快,官网的主题也很多,美观又高效。然而在配置的过程中仍有一些棘手的地方,例如 Git 的使用,SSH 秘钥的生成,插件的使用等。本文将从一个相对细致的角度介绍 Hexo 搭建
2018.10.06
[NOIP2012] 开车旅行 [NOIP2012] 开车旅行
摘要 倍增优化 DP 小 A 和小 B 决定旅行,城市从 1 到 N 编号,编号较小的城市在编号较大的城市的西边,各个城市的海拔高度互不相同,记城市 i 的海拔高度为 ,城市 i 和城市 j 之间的距离 $d[i,j]=|H_
2019.06.13
DP 小汇 DP 小汇
SRM 679 FiringEmployees 有一个 n 个点的树, 每个点有点权 (点权可能为负), 求包含点 1 的最大权连通子图 (的权值和)。 入门树形 DP, 表示以 i 为根的子树 $su
2018.10.05
[BZOJ2219] 数论之神 [BZOJ2219] 数论之神
摘要 啃课件的时侯遇到的,先放个题解,至于代码的话先咕着 多组数据( 1. . X 在范围 [0, 2K] 内 的 X 的个数. 即求同余方程 $x^a\equiv b\b
2019.06.08
斜率优化 DP 入门 斜率优化 DP 入门
前言本蒟蒻的第一道斜率优化 DP 前后卡了 3 小时…… 海星 有时候好不容易推出一个 DP 的式子,结果发现数据范围太大? 单调队列无法优化? 那就考虑斜率优化吧 [APIO2014] 序列分割 你正在玩一个关于长度为 的非负整
2019.01.15
数位动态规划 数位动态规划
概述数位 DP 的基本思想就是按位 DP,对数字的每一位做 DP。 数位 DP 常用于求解区间内满足条件的数的计数问题。 数位 DP 的一个重要特征是多维度。事实上由于在数位 DP 的过程中有若干限制条件,使得问题的维度较多,因此相比普通
2018.11.16
原根与模算术 原根与模算术
摘要 啃课件的时侯遇到的数论题,于是来填坑 阶与原根如果 (a,m)=1,记 x 为最小的正整数使得 . 那么 x 称为 的阶。记为 。 可以把阶理解为模意
2019.06.08
[Luogu2022] 有趣的数 [Luogu2022] 有趣的数
摘要 题意:Q(N,K) 表示把 1-N 按字典序从小到大排列后 K 的排名。给出 K,M,最小化 N,且 Q(N,K)=M. 无解输出 0。 一道思路很清奇的题。首先可以想到这些结论: 关于 i 单调递增(非严格)
2019.06.08
就《菊与刀》浅谈二战时期日本国民的性格 就《菊与刀》浅谈二战时期日本国民的性格
摘要 语文作业之读书报告…… I 前言谈到日本,想必每个人都有截然不同的看法。我知道我在本文所提到的观点必然是有人反对的。不过也并非不可,毕竟它正是如此矛盾。 我们知道在二战时期,日本法西斯发动了以侵华为主的战争。而这个时期国民党与共产党
2019.05.11
2 / 9