Splay 区间翻转（文艺平衡树） Splay树 区间翻转 操作 将数组的下标存到树中, 题目给出逆转的区间下标,那么在树中操作下标 利用子树都是存的是数组中连续的一段,(类似线段树) 翻转区间[l,r] 在二叉查找树中对 数组区间翻转 只需要 更改子树中每一个节点左右的左右子树 如何将整个区间(搬离到根节点附近去) ? 利用$Splay$的性质: rotate后中序遍历保持不变 将$l-1$节点通过$Spl 2019-11-26 算法 区间翻转
笛卡尔树 笛卡尔树一种二叉树,每个节点由 键值二元组 (k,w) 组成 性质 数列中每个元素对应树中某个唯一节点,树节点也对应于数列中某个唯一元素 中序遍历笛卡尔树得到原数列 任意树节点的左子树中的节点对应的数组元素下标小于该节点对应数组元素下标 同理, 右子树中的节点对应的数组元素下标大于该节点对应数组的元素下标 由于具有堆的性质, 任意节点对应的数值 大于or小于 左or右子树内任意节点对 2019-11-24 算法
POJ 2887 块状链表 块状链表练手POJ 2887 查询且需要插入 第一个字符串长度不超过 1000000 分成 $\sqrt(1000000) = 1000$个块 忘记初始化, 注意插入的位置，和题目要求的位置 每次记得维护插入或者删除后 接触块 的大小防止退化 1234567891011121314151617181920212223242526272829303132333435363738394 2019-11-24 算法
块状链表 块状链表 原理很好理解,实现要注意细节 转载博客 图示 数组来模拟链表 注意 块的编号和块中数组的下标 belong[]保证编号不重复 例题 Luogu 本文编辑器 belong[]的作用其实相当于记录块的编号 当块 (消失or合并) 时,下一次生成的块就用上一次消失块的编号,首次初始化为不同的就行了 避免块状链表退化,在删除或者插入后维护2端的块，根据块的大小来决定是 合并还 2019-11-21 算法
Luogu P2057 最小割 熟练一下 Luogu P2057问题转化为最小割建图 同意睡觉和反对睡觉恰好为2部分, 同意睡觉的点和$S$部分的源点连边, 同理, 反对睡觉的点和$T$部分的汇点连边, 边权都为1 朋友之间连边 因为都可以违背自己的意愿, 所以建双向边且边权为1 最后每个人只有一个决定(每个点都只能属于一个部分),为了使得冲突最小,,割掉最少的边将图分成2部分,即求最小割 123456789101 2019-11-18 算法 最小割 建图
Dinic算法 (优化) Dinic 算法(优化)前言: (个人而言) dfs_test()是 我以前学然后写Dinic中的dfs用来增广 新的dfs()速度比原来快很多 判断 向下增广返回的流是否为0 返回的流不为0代表增广成功 维护边后直接回溯 原来的dfs_test处于一个点时 : 只要所有出边遍历结束才回溯, 优化 当前弧优化 : 原来的dfs都是从每个点的第一条边开始遍历,导致已 2019-11-18 算法 最大流 最小割
最小割 最小割定义 这篇文章解释的挺好! 割 : 点的划分方式, 将图中的所有点划分成2个集合,源点s,汇点t, $s\in S,t \in T$. 割的容量 ： 表示所有从S到T的边的容量之和,$c(S,T) = \Sigma_{u \in S,v \in T}c(u,v)$ 最小割问题: 求一个割的方法使得割的容量最小 最大流 = 最小割 求最小割和最大流可以看做是一个问题 最小割 2019-11-18 算法 最小割
Floyd求最小环 Floyd求最小环原理: 当第三层循环到点k时, 所有点之间的最短路只通过[1,k)更新, 记$dis_{u,v}$是从u到v且仅经过编号在区间$[1,k)$中的点的最短路。 最小环至少要有3个顶点, 最小环通过一条最短路和枚举一个点的2条边来更新 $ans=min(ans,dis_{u,v}+g[u][k]+g[k][v])$ 算法的疑问? 如果g[u][k]+g[k][v]改为di 2019-11-17 算法 最小环
虚拟内存-2级分页表原理 虚拟内存中的分页 每个进程都有一个页表, 每个进程可以占据大量的虚存空间 概念： 页表项 : 页表中的每个项记录了每个页对应的页框号 不带单位默认为字节Byte 问题 假设进程的虚存空间为$2GB=2^{31}$，若使用$2^9 = 512$个字节的页,那么进程需要$2^{31}/2^9 = 2^{22}$个页表项. 导致进程加载到内存时,创建的页表占用的内存空间太大 2019-11-07 操作系统 虚拟内存 2级分页表 地址转换
死锁和饥饿-哲学家就餐问题 哲学家就餐问题 背景: 假设5位哲学家住在一起(可以推广到n),每天生活就是思考和吃饭,每位哲学家需要2把叉子来吃意大利面. 就餐安排: 一张圆桌,5个板凳,5个盘子,5把叉子,每个想吃饭的哲学家做到椅子上,使用盘子2侧的叉子来吃面条, 问题: 设计算法 保证互斥(2位哲学家不能使用相邻的叉子),同时还要避免死锁(每个哲学家都在等待叉子,且占用了叉子)和饥饿 信号量解决方案 规定 2019-11-05 操作系统 死锁 饥饿