Dawn-K's Blog

「From ashes to the empire」

「CodeNote」 数论初探

数论初探 简单的数论问题 质数 埃氏筛 1 2 3 4 5 6 7 8 9 10 11 12 13 const int N = 100000 + 5; bool prime[N]; void init(){ // 近似线性,复杂度O(nloglogn),也已经很小了 for(int i = 2; i < N; i ++) prime[i] = true...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 数据结构

数据结构 划分树 参考博客-十年换你一句好久不见 结构 划分树是基于线段树的一种数据结构，主要用于快速求出(log(n)时间的时间复杂度内))序列区间的第K大/小值 划分树主要分为两部分:建树和查询 建树 如图所示,划分树本质上是线段树加模拟快速排序. 首先我们先创建一个数组sorted[],用以保存原数组排序后的结果.和toleft[],用以记录当前节点及之前节...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 数位dp

数位dp 数位dp是一种模板性很强的,但又比较灵活的动态规划类型 其主要由两种实现方式,一种是预处理,一种是记忆化搜索.前者比较复杂,而且不直观,故我们在此仅讨论第二种情况 一般来说,此算法主要由两部分组成,一个solve()函数,一个dfs()函数.solve(n)主要是用于给出从[1,n]之间符合题目要求的数的个数/和/费用等,故求[m,n]之间符合的个数一般是由solve(n)-...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 并查集进阶

并查集进阶 绪论 我本来以为并查集是一种很简单的数据结构,但是实在是被kuangbin的专题虐的死去活来,故在此总结一下 并查集目前有三部分: 普通并查集,带权并查集,种类并查集 普通并查集 并查集有三种基本操作,初始化(?),搜索,合并 对于普通并查集，我们只关心两个问题(或者是实现两个功能)，即 判断两个元素是否在一个集合中 将两个不在同一集合的元素放在一个集合中...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 差分与前缀和

差分与前缀和 绪论 差分与前缀是两个相反的过程,其中差分旨在以递推的形式记录数组元素,前缀和是以求和的方式灵活地面对区间询问 区间加常数 给定一个序列𝑎(初值全为0)。有很多次操作，每个操作形如： l r k 意为将𝑎[𝑙,𝑟]中的每个值加上𝑘 最后输出整个数组。 复杂度要求O(𝑛).允许离线 这个有朴素的算法,就是老老实实一点点加,但是面对大量数据,就显得力不...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 卡特兰数

[组合数学]卡特兰数 [TOC] 卡特兰数是在复习数据结构时遇到的一个问题。 问题描述 最初的问题是这样： 有n个元素按a1,a2,a3…an的次序依次进栈(容量无穷)，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 这个问题在数量少的情况下可以进行模拟，但是仔细思索这是一个组合数学的问题。 递归写法 首先，我们设f（n）=序列个数为n的出栈序列种数。...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 单调栈与单调队列

单调栈&单调队列 介绍 单调栈和单调队列是两种很简单,但是很强大的数据结构.一般不会直接出裸题,常常作为优化手段使用.(多见于dp) 单调队列实际上是升级版的单调栈. 单调栈 单调栈可以在O(n)时间复杂度下完成以下操作 对于给定的a[ ]数组,在O(n)时间内生成数组 L[ ],其中L[i]表示a[i] 左边/右边 第一个 小于/大于 a[i]的元素的下标(常记录...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 区间第k大

区间第K大 天地正玲珑,殡葬了飞虫 问题描述 几乎所有高级数据结构都可以求区间第K大(同理还有区间第K小),在此列出几种方法. 主席树 这个应该是性价比较高的,能够在线求静态的,树状数组套主席树能够离线求待修改的.时间复杂度O(nlogn) ,空间复杂度O(nlogn) .

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 分层最短路

分层最短路 介绍 分层图最短路在最短路的基础上,增加了一个条件:可将 k 条边的权值变为 0. 分析 这种问题我们可以想到一种做法: 如图,我们构建一个多层的图,其中每一层都是和题目中给的图相同.(图中假设k==1)上面的层表示不将任何边的权值变为0,而下面的这一层表示使用了这个机会后的状态. 也就是0号节点可以不使用机会,转移到2号节点,也可以使用机会转移到7号(其...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 二叉树递归应用

二叉树递归应用 此文档主要是用来记录二叉树的一些递归操作. [TOC] 结构 1 2 3 4 5 typedef struct node { // 二叉树节点结构 char data; struct node *lchild; struct node *rchild; } *Bitree; 建树 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

Posted by Dawn-K's Blog on August 6, 2019

FEATURED TAGS
CodeNote Web开发 软件工程 SpringBoot 互联网架构 垃圾回收的算法和实现 设计模式 android DAO 数据库 Python Vue Linux Unity VSCode学习 操作系统 版本控制 C++ View Java Kotlin Missing-Semester
ABOUT ME

Dawnk | 计算机本科生 | 退役ACMer | Vocaloid 爱好者

FRIENDS