洛谷做题笔记
洛谷做题的笔记，只打算给自己看所以描述语言非常简单混乱。
题单：一个动态更新的洛谷综合题单 – Studying Father’s blog
代码备份：bebinca/algorithm-practice: Part2.2开始 (github.com)
下划线代表可以再做一次，加粗是相关知识点。
P1177 sorting 快速排序 nlogn
mid=arr[(i+j)/2]
中间元素mid作为key，i++找第一个大于等于mid的，j–找第一个小于等于mid的，如果i<=j则交换，继续操作直到i>j停止，对两边做quicksort
P1309 瑞士轮
赢的score+1，输的score不变，所以win和lose是两个有序数组，对其做mergesort即可，复杂度R*N
P1908 逆序对
mergesort求逆序对
树状数组【待更新
P1024 一元三次方程组求解
每个解之间间隔>=1，所以[i, i+1)内最多一个解，枚举i并对每个区间内做二分求解即可
中间出过一次MLE，原因是对保留两位小数结果相同的判定太松了。因为四舍五入算法：正数+0 ...
ML白板推导系列笔记
不断更新中
课程地址：【机器学习】【白板推导系列】【合集 1～23】_哔哩哔哩_bilibili
Introduction Frequentists vs Bayesians
Data： X=(x1,…,xN)N∗pTX = (x_1, \dots, x_N)^T_{N*p}X=(x1,…,xN)N∗pT
X服从概率模型 X∼p(x∣θ)X \sim p(x|\theta)X∼p(x∣θ)
频率派
θ\thetaθ 是未知的常量，X是随机变量，常用MLE极大似然估计：
θMLE=argmaxθlogP(X∣θ)\theta_{MLE}=\substack{argmax\\ \theta} log P(X|\theta)θMLE=argmaxθlogP(X∣θ)， logP(X∣θ)log P(X|\theta)logP(X∣θ)一般记为L(θ)L(\theta)L(θ)
此处log是为了方便计算，如果不log的话P等于每个独立同分布的xix_ixi的连乘，加上log符号只要求和即可
贝叶斯派
认为参数θ\thetaθ也是一个随机变量，服从概率分布θ∼p(θ)\theta \ ...
论文笔记Sequence Synopsis-vast17
Sequence Synopsis: Optimize Visual Summary of Temporal Event Data
暑假夏令营复现的论文，看的时候做的笔记。
前置知识
MDL principle
最小描述长度，需要保存的数据长度(比特数) 等于这些实例数据进行编码压缩后的长度加上保存模型所需的数据长度，将该数据长度称为总描述长度。
event sequence analysis
数据是多个时间戳或有序事件的系列。事件序列分析是指在进行系统故障和安全分析时，从各种假设始发事件开始，根据设计，按照逻辑顺序分析其系统部件和运行人员可能的动作及其后果，直至最终安全状态或事故状态的一系列事件。
内容
background
领域：事件序列的可视化
那么什么是事件序列？可以理解为有时序性的事件的串。比如一个事件可以理解为谁在什么时间做了什么事情，事件序列的数据就是把事件按照时间等顺序排列下来。
比如车辆的行车记录，每个事件发生了什么动作或者故障，就可以记录下来，分析这个数据，typical fault development paths can be identi ...
计算机视觉复习
引言
格式塔法则Gestalt law
接近原则proximity：接近、临近的物品认作一个整体
相似原则similarity：相似的物体感知成同一组的部分
共同命运原则common fate：将以相同的速度和（或）方向运动的物体感知成一个组
对称原则symmetry：互相对称的元素容易被感知为统一的组
连续性原则contimuity：若图形的某些部分可以被看作连接在一起的，则这些部分很可能被认为是一个整体
封闭/闭合原则closure：把不完整的没有闭合的个体看成是一个整体的形状
Marr视觉表示框架的三个阶段
第一阶段 (Primal Sketch)：将输入的原始图像进行处理，抽取图像中诸如角点、边缘、纹理、线条、边界等基本特征， 这些特征的集合称为基元图；
第二阶段 (2.5D Sketch)：指在以观测者为中心的坐标系中， 由输入图像和基元图恢复场景可见部分的深度、法线方向、 轮廓等，这些信息包含了深度信息，但不是真正的物体三维表示，因此被称为二维半图；
第三阶段 (3D Model)：在以物体为中心的坐标系中，由输入图像、基元图、二维半图来恢复、表示和识别三维物体。 ...
OS期末复习
OS复习
期末复习前的知识整理，个人使用。
01 Introduction
OS是资源分配者，是控制程序。总是在运行的程序指kernel。
bootstrap program：在power-up或者reboot的时候加载，是固件。初始化系统，load kernel开始执行。
CPU和device controller通过bus连到shared memory；竞争memory cycle
IO可以和CPU并发执行，每个device controller有一个local buffer。CPU通过buffer和memory互传数据；IO的数据从device到buffer。device controller通过interrupt通知CPU它完成了操作。
interrupt通过interrupt vector传输到相应的interrupt服务程序（service routine）。interrupt vector含有所有服务程序的地址。当别的interrupt正在处理的时候，incoming interrupts会被disabled。Interrupt architectur ...
AOR8 博弈
算法博弈论
稳定婚姻匹配问题
有 NNN 位男生和 NNN 位女生，每个男生都对 NNN 个女生的喜欢程度做了排序，每个女生都对 NNN 个男生的喜欢程度做了排序，现在需要确定一个稳定的约会状态（匹配）。
若存在两对匹配 A=(u,v)A=(u,v)A=(u,v)，B=(p,q)B=(p,q)B=(p,q) ，满足男生 uuu 比起女生 vvv 更喜欢女生 qqq，且女生 qqq 比起男生 ppp 更喜欢男生 uuu，那么我们称这组方案是不稳定的。
想法一：Local Change
Local change: 若两个人互相都觉得对方比自己当前的伴侣更好，就让这两个人成为一对，被甩的那两个人组成一对，重复逐步改进，直到消除所有的拆分对。
这个算法是不行的，可以构造例子陷入循环。Local Change每次是找到一个拆分对就换，而不是找到一个最合适的拆分对再换。
Gale–Shapley 算法
首先选择一个单身男生，他会按照他的喜欢程度对一个还没有表白过的女生表白。
如果女生此时处于单身状态，则他们两人将进入约会状态。
如果女生已经有匹配对象，会将他与当前对象做比较。如果她更喜欢 ...
AOR7 Online问题
在线算法
问题概述
在线算法：信息一个一个给出，决策不可以逆转。
问题模型
对于online实例 I={σ1,…,σn}I = \{\sigma_1, \dots, \sigma_n\}I={σ1,…,σn}，有算法输出 O={y1,…,yn}O = \{y_1, \dots, y_n\}O={y1,…,yn}。
竞争比：设AAA是一个online算法，OPTOPTOPT是最优的offline算法（提前知道了所有信息）。则对于最小化问题，如果存在一个常数 β\betaβ，对任意 III，满足A(I)≤c∗OPT(I)+βA(I) \leq c * OPT(I) + \betaA(I)≤c∗OPT(I)+β，则称 ccc 的下确界为竞争比。
对于online问题的研究可以考虑以下方面：
Semi Online：可以知道一部分信息，过去做的决策可以进行有限度的更改
Online with Advice：可以知道一部分信息
Online with Imperfect Information：有建议可以参考，但不保证是对的
在信息相对准确时，接近离线算法，信息相对不准时，接近在线算 ...
AOR6 装箱问题
装箱问题
First-Fit算法
引入
渐进比： 算法A如果对于任意的实例 III ，存在一个常数kkk，满足A(I)≤αOPT(I)+kA(I) \leq \alpha OPT(I) + kA(I)≤αOPT(I)+k，称 α\alphaα 的下确界为A的渐近比。与近似比相比，渐进比后面多了一个常数kkk。
一维装箱问题： 给定 nnn 个物品，体积在(0,1](0,1](0,1]之间，求最少需要多少个体积为 111 的箱子可以装下。
两个箱子能否装下所有物品是NPC问题；装箱问题不存在近似比小于32\frac{3}{2}23的多项式近似算法（unless P=NP）。这两条可以推嘛？
传统的装箱算法有Next Fit，First Fit，Best Fit，Harmonic Fit等，尽管近似比没有什么乐观的结果，我们本节可以关注一下它们的渐进比。
Next Fit (NL)
Next Fit：如果现在这个箱子能装下，就把物品放进去；否则关闭它，并打开一个新的箱子来放物品。
线性时间算法，NL(I)≤2OPT(I)−1NL(I) \leq 2 OPT(I) - 1NL(I)≤ ...
AOR5 斯坦纳树、旅行商问题
斯坦纳树、旅行商问题
本节轮到我们这组做lecture notes，提交上去的是用latex处理的整理结果。这里我把自己的笔记基本更新成和lecture notes一致了，内容更少一些，个别表达有所不同。
斯坦纳树问题
斯坦纳树问题：给定G=(V,E), C:E→R+G=(V,E), \ C:E \rightarrow R^{+}G=(V,E), C:E→R+，其中CCC满足三角不等式。对于点集S⊆VS \subseteq VS⊆V，求GGG的连通子图G′=(S′,E′), S⊆S′G'=(S', E'), \ S \subseteq S'G′=(S′,E′), S⊆S′，使得SSS中的点彼此联通，并且选中的边权和最小。显然，最优解的G′G'G′必定是一棵树，我们记作斯坦纳树，S′∖SS' \setminus SS′∖S中的点记作斯坦纳点。
斯坦纳树问题的求解是一个NP-Hard问题。在本节中，我们重点关注该问题的近似算法，同时为了简单起见，我们仅讨论完全图上的斯坦纳树。
欧氏平面上的斯坦纳树
欧氏平面上的斯坦纳树：给定平面上 ...
AOR4 贪心算法、独立系统、拟阵
贪心算法、独立系统、拟阵
基本概念
独立系统与独立集
独立系统： 对于集合系统 (E,F)(E, \mathscr{F})(E,F) ，其中 EEE 是有限基本元素集合，F∈2E\mathscr{F} \in 2^EF∈2E，若满足：
(M1) ∅∈F\empty \in \mathscr{F}∅∈F
(M2) 若 Y⊆X∈FY \subseteq X \in \mathscr{F}Y⊆X∈F，则 Y∈FY \in \mathscr{F}Y∈F。（包含的封闭性）
则 (E,F)(E, \mathscr{F})(E,F) 是一个独立系统。
独立集：F\mathscr{F}F 中的元素称为独立集。
F\mathscr{F}F 可以看作某种规则，F\mathscr{F}F 中的元素就是满足规则的集合。比如定义规则 F={T⊆E,∣T∣≤K}\mathscr{F} = \{T\subseteq E, |T| \le K\}F={T⊆E,∣T∣≤K}，(E,F)(E, \mathscr{F})(E,F) 就是一个符合定义的独立系统，独立集就是模不大于 KKK 的子集。
基、相 ...