OI资源分享

AFO了,做点贡献好了。分享部分算法模板和做过的题目: 退役后遗产,各大网站的题目源程序+Word题解+(资料?),约1000道题目。

阅读更多
Internet Protocols & SecuritySlides

从高斯消元到"QGXZ分解"

学习线性代数心血来潮代码一波。

本文将简单介绍矩阵利用高斯消元完成的各种操作和科技,并用C++不使用任何第三方库手写一个封装有矩阵类型和多种操作的库

主要内容包括: 矩阵的基本运算,矩阵的转置(transpose),高斯消元,矩阵的echelon form和reduced echelon form,矩阵的迹(trace),矩阵的秩(rank),矩阵的逆(inverse),矩阵的行列式(determinant),高斯消元解线性方程组,线性方程组的通解,LU分解,PLU分解,以及由于我孤陋寡闻并没有查到的、大佬@GXZlegend传授的”GXZ分解”和”QGXZ分解”。

这里代码的实现更多采用了类似于”函数式编程”的模式,因此实现过程并没有很在意常数,常数可能比较大,使用时请谨慎。

反正我现在不搞OI了,暂时不用关心常数了,啦啦啦!

UPD 2019.10.25: 结尾处GXZ大佬本尊补充了另一种实现方式的”QGXZ分解”。更加OI,封装性相对较低,适合简便、快速地使用。

UPD 2019.10.27: 这种方法类似于LDU分解,两者形式上似乎不完全一样。

阅读更多
量子计算与Microsoft Q#入门笔记

量子计算了解一下~

本文将在没有量子力学基础基本不涉及量子力学前提下(例如我太菜了搞不懂布洛赫球面),仅介绍量子计算需要了解的相关知识,并使用Microsof Q#语言完成比赛Microsoft Q# Coding Contest - Summer 2018 - Warmup.

本文非常入门(我太菜了.jpg),有错误也欢迎大佬指正。

阅读更多
深度神经网络实战: MNIST手写数字识别

此前,已经成功实现了只使用C++而不使用第三方库,来实现一个深度神经网络来解决多分类逻辑回归问题。可以见C++实现深度神经网络解决多分类逻辑回归问题

如今考虑一点更实战化的改进和应用尝试: 神经网络入门问题——手写数字识别。使用的数字当然是来自经典的MNIST数据集(Mixed National Institute of Standards and Technology database)了。

阅读更多
【趣题】圆内任取四点在同一半圆内概率

dalao室友突然提出一个他看到的有趣的问题: 在一个圆内均匀随机取$4$个点,落在同一个半圆内的概率(半圆圆心与原来的圆相同)。

首先因为均匀随机点也是均匀随机圆周角,所以实际上是问: 在一个圆周上均匀随机取$4$个点,在同一个半圆弧上的概率。

一般化地,我考虑随机取$n$个点的情况,本文将讨论$n \le 4$并推广到任意$n$。本文将以”大学数学”和”小学数学”两条思路进行。

阅读更多
Ukkonen算法与后缀树构造后缀数组

本文介绍了Ukkonen算法构造后缀树、如何用后缀数组构造后缀数组从而得到一个$O(n)$构造后缀数组的算法(不考虑字符集大小),并与其他优秀的后缀数组算法进行了速度比较。

食用本文前建议对后缀数组(SA)和后缀树(ST)有基本了解。

阅读更多
求后缀数组的SAM与SA-IS方法

填一个OI期间一直想学但是没有学的坑: SA-IS求后缀数组。

众所周知后缀数组有$O(n \log n)$的倍增方法以及$O(n)$的DC3方法。而本文将会简单介绍倍增方法并详细讲解黑科技: $O(n)$的SAM方法以及SA-IS方法。

食用本文前建议对后缀数组(SA)和后缀自动机(SAM)有基本了解。

阅读更多
Number TheorySlides

Data StructuresSlides