皮蛋秀柚秋

笔记

读书笔记(2) 题解(1)

/ 注册

全部文章 / 笔记（共30篇）

素数判定

求2~m范围内所有素数。常规方法：复杂度O(n*sqrt(n)) 枚举2~m之间的每个数k for(int i=2;i<=sqrt(k);++i){ if(k%i==0) return false; } return true;素数筛法：O(nlogn) vector<int&...

2020-06-06

0 669

RMQ算法

RMQ RMQ(range min/max query)区间最值查询算法。经典场景：给定一个数组A[1...N]，有N个数字。查询区间[l,r]，求该区间的最大/最小值。常规方法是对[l,r]进行遍历，复杂度O(n)。当查询次数K巨大时，性能会很差。RMQ算法需要nlogn时间进行预处理，之后以O(...

RMQ

2020-05-24

0 735

树状数组

lowbit运算 lowbit(x) = x&(-x)取x的二进制表示最右边的1和它右边的所有0.结果一定是2的次幂。例如：定义树状数组C仍是一个数组，与前缀和数组sum类似，它是一个用来记录和的数组，只不过它存放的不是前i个整数之和，而是在i号位之前(含i号位)lowbit(i)个整...

树状数组

2020-05-23

0 708

离散化

离散化操作两个使用到的函数： C++ unique去重函数使用方法：unique (首地址，尾地址);功能：去除相邻的重复元素（只保留一个），并把重复的元素放在最后；unique 返回去重后的尾地址； lower_bound() 函数，在前闭后开区间进行二分查找lower_bound() 是返...

线段树

2020-05-07

0 574

线段树

概念假设有编号从1到n的n个点，每个点都存了一些信息，用[L,R]表示下标从L到R的这些点。线段树的用处就是，对编号连续的一些点进行修改或者统计操作，修改和统计的复杂度都是O(log(n)).线段树的原理，就是，将[1,n]分解成若干特定的子区间(数量不超过4*n),然后，将每个区间[L,R]都分...

线段树

2020-05-06

0 956

数组的最大m子段和

给定由n个整数（可能为负）组成的序列a1、a2、a3...,an, 以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和最大。注：有些题目要求非负数答案，当m子段最大和是负数时，取最大值为0. 思路：二维dp,dp[i][j]表示必须以数组的第j个数结尾构成的i个子段的最大值。转...

dp

2020-05-04

0 1238

最小生成树(MST)

最小生成树及其性质最小生成树是在一个给定的无向图中求一棵树T，使得这棵树拥有图G中的所有顶点，且所有的边均是来自图G中的边，并且满足整棵树的边权之和最小。性质：最小生成树是树，因此其边数等于顶点数减一，且树内没有环；对于一个给定的图，最小生成树可以不唯一，但其边权之和一定是唯一的；由于最小生成...

MST

2020-03-11

0 1244

最短路径算法

单源最短路径 Dijkstra算法 Dijkstra算法的策略是：假设顶点集为V，设置集合S存放已被访问的顶点，然后执行下面两个步骤n次：（n为顶点数目）每次从集合V-S中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合S。之后，令顶点u作为中介点，优化起点s与所有从u能到达且...

最短路径

2020-03-11

0 859

蓄水池采样算法

问题描述采样问题经常会涉及到，简单地，有如下形式： 1.从1000000份调查报告中抽1000份进行统计 2.从一本很厚的电话簿中抽1000人进行姓氏统计 3.从Google搜索"AI"的结果中抽100个进行分析分析：问题1我们很容易想到生成1至1000000的随机数，抽取...

蓄水池抽样

2020-01-22

0 1363

堆

堆的定义及性质堆是一棵完全二叉树，以大顶堆为例，每个节点的值不小于其左右孩子节点。用数组实现堆，下标为i的节点其左右孩子节点的小标为2i和2i+1。相关操作建堆：从最后一个有孩子的节点开始，逆序枚举，每个节点向下调整插入元素：将新增元素插入堆尾，向上调整删除（堆顶）元素：将最后一个元素覆盖...

堆

2020-01-10

0 807