线段树学习笔记

概述

假设要从数组arr[0 ... n - 1]查找某个数组某段区间的最小值，其中数组大小固定，但是数组中的元素可以随时更新。一个简单的解法是遍历数组区间寻找最小值，时间复杂度是$O(n)$，额外空间复杂度$O(1)$，当数据量特别大，查询操作很频繁时，耗时可能不能够满足要求。

SPFA学习笔记

介绍

SPFA(Shortest Path Faster Algorithm)就是队列优化的Bellman-Ford，时间复杂度声称可以优化到$O(km)$，实际很容易卡到最坏的情况$O(nm)$，可以处理负权边，判定负权环。建议除非有负权边，否则不要用SPFA。

Dijkstra学习笔记

介绍

这个算法适用于非负权图中求单源最短路（一个顶点到其他所有顶点的最短路），有着稳定优秀的时间复杂度，暴力Dij时间复杂度为$O(n^2)$，堆优后为$O(mlogn)$。事实上$m$和$n^2$是同阶的，不过一般情况下$m$远小于$n^2$，这种图被称为稀疏图；而$m$相对较大的图则被称为稠密图，这种情况下暴力Dij可能要比堆优Dij更优。

线性代数学习笔记(2)

行列式

定义

线性变换对区域面积产生缩放的比例被称为这个变换的行列式(Determinant) 。记为：$\rm{det}(\begin{bmatrix} a & b \\ c & d \end{bmatrix})$

Floyd 学习笔记

最短路

性质

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。

对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过$n$ ，边数不会超过 $n - 1$ 。

（以上引自OI-Wikii）

Kruskal 学习笔记

最小生成树

在无向图中，连通且无环的图称为树(Tree)。给定无向图$G=(V,E)$，连接$G$中所有点，且边集是$E$的子集的树称为$G$的生成树(Spanning Tree)，而权值最小的生成树称为最小生成树(Minimal Spanning Tree , MST)。s

OI中的花样排序方法

排序算法多种多样 ，性质也大多不同。

选择排序

时间复杂度：$O(n^2)$ ，不稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13

void selectionSort(int* a,int n){  //选择排序
	for(int i = 1;i < n;i++){ //最后一位不用判断
		int ith = i; //ith记录当前位置后最小数的位置
		for(int j = i + 1;j <= n;j++){
			if(a[j] < a[ith])
			ith = j; //循环寻找当前位置后最小的数
		}
		int t = a[i];
		a[i] = a[ith];
		a[ith] = t;  //将第i个小的数与位置为i的数互换
	}

}

线性代数(Linear Algebra)学习笔记

向量(Vectors)

在空间中，向量可以表示为一个有方向有长短的箭头。（数学中的向量为自由向量，是没有起点的。在线性代数中，通常使向量的起点为原点，此图以二维为例）

Java学习笔记-1

受Minecraft Java版的影响，一直想学Java。最近终于开始着手学习，在博客里记录下来学习历程。

安装编程环境

在官网下载安装jdk，配置环境变量，安装eclipse，汉化eclipse。

今天是十二月的第一天，NOIP普及组复赛已经过去了20天……

NOIP2018复赛游记

Day -1

晚上到家，开始复习dp（然而T3还是没做出来…），还是不会写。再次动用物理课代表特权，不写物理作业来复习竞赛。（顺便让朋友送我两个面包awa，防止在赛场上饿）