2019CSP-S1游记

Day-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,防止在赛场上饿)

阅读全文 »