2023年07月19日

332

阅读

程序设计

左偏树 左偏树简介左偏树是一种可并堆，也叫左偏堆、左倾堆、左氏堆，是一种树，具有堆的性质，可以实现快速合并。左偏树不是二叉搜索树，不是平衡树，因为它不满足中序有序性，无法进行二分搜索，因此不可以快速查找...

2023年07月19日

297

阅读

程序设计

线段树扩展：权值线段树 前言先前博客中写过“线段树”这一篇文章，而这一次是一种具有新的含义的线段树：权值线段树。权值线段树简介定义权值线段树和普通线段树的形态类似，但是含义不同。普通线段树的节点通常存储该区间的最值或者...

2023年07月19日

294

阅读

程序设计

平衡二叉树 二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。Tre...

2023年07月19日

265

阅读

程序设计

可持久化线段树 可持久化线段树简介基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。优点解释每次插入操作最多创建的...

2023年07月19日

288

阅读

程序设计

二叉堆 二叉堆简介二叉堆是一种基础数据结构，对于其他数据结构来说，支持的操作有限，也就插入，查询，删除这一类。二叉堆的结构从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存在一个权值。堆...

2023年07月19日

264

阅读

程序设计

讲义-线段树 [alart]学习线段树，你需要先完成树、数组、分治思想、递归的学习（可以说是学习成本极低了）[\alart]引入线段树是一个用途极为广泛的数据结构，在提高组及以上的比赛中经常看到它的身影。现在...

2023年07月19日

4.2k

阅读

程序设计

三分法 导入学习三分法之前，大家应该都学会了二分法，二分法就是求解一个单调函数的零点，通俗一点，就是求解单调递增或递减序列的一个值，常用于二分查找（当然，你可以使用lower_bound或者upper_...

2023年07月19日

279

阅读

程序设计

高阶差分 高阶差分简介记 $\Delta f(x)=f(x+1)−f(x)$。称 $\Delta f(x)$ 为 $f(x)$ 的一阶差分。同理：记 $\Delta^n f(x)=\Delta^{n−1}...

2023年07月19日

281

阅读

程序设计

差分 差分性质差分可以理解为前缀和的逆运算。这种策略的定义是令差分应用简单差分差分数组可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作...

2023年07月19日

289

阅读

程序设计

P4391 [BOI2009]Radio Transmission 无线传输 题解 题目传送门题目题目描述给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。输入格式第一行一个整数 $...

2023年07月19日

274

阅读

程序设计

KMP算法 KMP算法简介算法来源Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vau...

2023年07月19日

283

阅读

程序设计

P1349 广义斐波那契数列 题解 题目传送门题目题目描述广义的斐波那契数列是指形如 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 的数列。 今给定数列的两系数 $p$ 和 $q$，以及数列的最...

2023年07月19日

304

阅读

程序设计

P1613 跑路 题解 传送门题目理解与强调给定一个有向图，共有 $n$ 个点和 $m$ 条边，存在自环的情况，每条边的长度都为 $1$ 。与一般题目不同的是，每走一步会走过 $2^k$ 个单位长度（ $k$ 为任意自...

2023年07月19日

290

阅读

程序设计

P8482 「HGOI-1」Number 题解 题目传送门「HGOI-1」Number题目背景$\text{bh1234666}$ 正在学习乘法！题目描述$\text{bh1234666}$ 有一定数量的数字 $0 \sim 9$，现在他想让...

2023年07月19日

360

阅读

程序设计

简单数列 Catalan数（卡特兰数）实际问题有 $2n$ 个人排成一行进入剧场。入场费 $5$ 元。其中只有 $n$ 个人有一张 $5$ 元钞票，另外 $n$ 人只有 $10$ 元钞票，剧院无其它钞票，...

2023年07月19日

303

阅读

程序设计

矩阵 矩阵构建一个$m$行$n$列（记为$m\times n$）的矩阵用二维数组$matrix$存储，$matrix_{i,j}$表示第$i$行第$j$列元素的值。在学习矩阵快速幂之前，你需要先学习快...

2023年07月19日

261

阅读

程序设计

区间动态规划 简介区间动态规划本质上是线性动态规划的一种，但是其独特的思想自称体系，所以被单独提出来成为区间动态规划。区间动态规划是以区间长度作为DP的阶段，以区间的左右端点作为状态的维度，一个状态通常由被它...

2023年07月19日

269

阅读

程序设计

线段树 线段树简介主要作用：线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。时间复杂度：每一次查询、修改：基本形态...

2023年07月17日

1.8k

阅读

默认分类

数论 整除定义设$a,b \in \mathbb{Z}$，如果存在$q \in \mathbb{Z}$，使得$b=aq$，那么就可以说$b$可以被$a$整除，记作$a \mid b$，且称$b$是$a...

2023年07月16日

459

阅读

默认分类

Typecho优秀主题Cuteen5的美化方案 Cuteen主题简介如您所想，如你所愿，Cuteen5系列正式来袭！与其他系列相比，取其精华去其糟粕，短代码功能非常好用，5系列在4系列基础上新增了任务列表功能短代码，均集成在了后台编辑器当中🎨...