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，防止在赛场上饿）

NOIP2018初赛游记

前言

写下这篇文章时，我发现我已经两个月没更新博客了…

正文

早晨醒来吃完饭，把洛谷夏令营的初赛课程又看了一遍(感觉之前白学了),复习了下组合数。毕竟是第一次参加NOIP，略微有些紧张（tj应该…不难吧）。