On the way

单源最短路径问题

关于图的单源最短路径的C++ 实现,以POJ 2387:Til the Cows Come Home 为例AC。 Bellman-Ford算法 采用动态规划思想的解法。要求没有负圈,如果有负圈的话就没有解了。 对所有边进行松弛操作,共V−1次,其中 V 是图节点的数量。时间复杂度O(VE)。V和E分别是节点和边的数量。 另外可以用SPFA算法进行优化,因为松弛操作必定只会发生在最短路径前...

凸包算法

定义 凸包是包所有点的最小的凸状集合 葛立恒(Graham)扫描法 以逆时针/左转的方式穿过凸包 选择y轴坐标最小的点(最低点)作为p点,即扫描的起始点,会发现从p点到其他每个点的向量的极角值递增。 难点: 如何找到最低点?对y坐标排序 如何根据极角大小排序,以及如何比较这些点? 如何判断两点间是否是逆时针旋转? 计算凸包的主要部分就是排序。有一个好的排序...

并查集

coursera课程笔记 解决算法的一个步骤: 问题建模,找到解决算法(可以使暴力解)。 时间复杂度?空间复杂度?原因?(可以考虑用空间换时间,用时间换空间) 优化 注意边界条件(空值,极大/小值) 关于并查集 - 维基百科 主要有两个操作: Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union:将两个子集合并成同一个集...

C++ struct 和 class的区别

struct是C原有的,C++为了兼容C而支持了struct。什么时候该用struct或者class没有明确的界限。 语法角度的区别: 默认继承权限不同。class是private,struct是public。 成员的默认访问权限不同。class是private,struct是public。 struct不能作为模板参数,class可以。(这个有点不懂,为啥那个map的自...

C++随机数

通过简单的C库函数rand来生成随机数,此函数生成均匀分布的伪随机数,每个随机数的范围在0和一个系统相关的最大值(至少为32767)之间(最大值是多少?INT_MAX?) 首先初始化随机数种子,使程序每次运行时生成不同的随机序列。 因为rand() 的范围是0~max,所以通过取余的方式来获取需要的范围内的随机数 srand(time(NULL)); rand() % 100; 其他:...

范围最小值问题

范围最小值问题(Range Minimum Query, RMQ)。给定一个数组A[1, n],求A[i,j]的最小值。 这里假定数组A的元素不会变化(如果变化,用线段树)。 范围最值查询-维基百科 Sparse-Table(ST)算法 预处理时间O(nlogn),查询O(1)。 令 表示从开始,长度为的一段元素中的最小值。 利用动态规划,状态转移方程是:。 注意。故d数组的元素个数...

C++ IO 库

《C++ primer》th5 学习笔记 第8章 基本IO库设施: istream: 输入操作。 ostream: 输出操作。 cin:一个istream对象,从标准输入读数据。 cout:一个ostream对象,向标准输出写数据。 cerr: osstream对象,用于输出程序错误消息。 >> 运算符: 从一个istream对象读输入数据。 &l...

C++位运算

设置bit int mask = 1 << x; number |= mask; 确定想将某一位设置为1,只需要将mask的对应位设置为1,然后位或运算。所以,以上代码会设置number的右数第x位为1(x从0开始)。 清除bit number &= ~(1 << x); 确定想将某一位设置为0,需要mask的对应位置为0,其他位置为1,然后位与运算。那...

二叉索引树(树状数组)

内容参考 《算法竞赛入门经典-训练指南》 二叉索引树(Binary Indexed Tree, BIT),俗称树状数组,又以发明者命名为Fenwick树。现多用于高效计算数列的前缀和,区间和。 树状数组-维基百科。 应用 给定一个n个元素的数组 ,设计一个查询操作Query(i, j) = 。 如何做?如果用前缀和的思想,计算,那么 Query(i, j) = ,单次查询时间为O(1),...

泛型算法

《C++ primer》th5 学习笔记 第10章 概述 泛型算法是一些经典算法的公共接口,可适用于多种容器,大多数定义在algorithm头文件,另外在numeric头文件定义了一组数值泛型算法。这些算法运行于迭代器之上。 初识泛型算法 只读算法 accumulate(),前两个参数指定需要求和的范围,第三个参数决定使用的加法运算符和返回值类型。 如下的代码则是分别对整数和字...