#差分约束 ##模型 将不等式条件化为： x1-x2<=v1 x2-x3<=v2 … xi-xj<=vk 求取xi-xj最大值，最小值，或判断该不等式组解的存在性 ##做法 对每个x建点 对xi-xj<=vk,建立xj->xi有向边，边权为vk 求max{xi-xj}:xj->xi最短路 求min{xi-xj}:xj->xi最长路 求该差分约束系统

平衡树——Treap&Splay 平衡树学习总结 2016-12-29 概述 朴素的BST有时会退化成一条链，从而使二分查找的效率大大降低，为了防止这种情况的发生,平衡树应运而生。 顾名思义，平衡树的各个子树的深度应该相等或者相似。 两种基本操作：左旋&右旋 zig()&zag() 保证平衡树仍然满足BST的性质，但能够调换节点在树中的

DancingLinksX|精确覆盖&重复覆盖 ​ 本文介绍DLX及其在精确覆盖和重复覆盖问题中的应用。 在DLX之前先了解精确覆盖和重复覆盖。 精确覆盖 给出一个仅有0、1的矩阵，选择其中的一些行使得这些行组成的集合中每一列都有且仅有一个1，求方案的存在性及具体方案。 重复覆盖 给出一个仅有0、1的矩阵

最小生成树 无向图：Prim&Kruskal Prim 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 //Prim #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> using namespace std; template<typename T>

数论 最大公因数GCD 推荐阅读 辗转相除法 略。 Stein 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 //Stein gcd(a,b) { if(a==b) { gcd=a; return; } if(a为偶数b为奇数)//一定没有2因子 gcd=gcd(a/2,b); if(a为奇数b为偶数)//同上 gcd=gcd(a,b/2); if(a,b均为偶数) gcd=2*gcd(a/2,b/2);//一定有2因子 if(a,b均为奇数) { if(a<b) gcd=gcd(b,a); gcd=gcd(a-b,b); } } 斐波那契数列

矩阵 概念 定义 矩形的数组 特殊矩阵 零矩阵：所有元素均为0的矩阵 单位矩阵（E或I）：对角线元素为1，其他元素为0的矩阵（A*E=A） 方阵：列数与行数相等的矩阵 对称矩阵：转置矩阵与原矩阵相同的矩阵 在编程求解有关矩阵的题目时，可以使用下面的模板： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 template<typename T&

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 //希尔排序 template<typename T> void Swap(T& a,T& b){T t=a;a=b;b=t;} template<typename T> void shellSort(T* ary,int l,int r)//默认为<,r为超尾 { int len=(r-l); for(int k=len/2;k>=1;--k) for(int i=l+k-1;i<=r;++i) for(int j=i;j-k>=l&&ary[j]<ary[j-k];j-=k) Swap(ary[j],ary[j-k]); } template<typename T> void shellSort(T* ary,int l,int r,bool comp(const T& a,const T& b))//r为超尾 { int len=(r-l); for(int k=len/2;k>=1;--k) for(int i=l+k-1;i<=r;++i) for(int j=i;j-k>=l&&comp(ary[j],ary[j-k]);j-=k) Swap(ary[j],ary[j-k]); }

RMQ问题与ST表 ST表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 /* ST表 */ #include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; template<typename T> T Max(const T& a,const T& b){return a>b?a:b;} template<typename T> void read(T& w) { char r;int f=1; for(r=getchar();(r<48||r>57)&&r!='-';r=getchar()); if(r=='-')r=getchar(),f=-1; for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48; w*=f; } const int maxn=int(1e5+3); const int maxm=int(1e6+3); int n,m; int f[maxn][20]; int a[maxn]; void input() { read(n),read(m); for(int i=1;i<=n;++i) { read(a[i]);

在幕布中查看（密码：LAN） 计算机结构与原理 冯诺依曼架构 组成 存储器、运算器、控制器、输入设备、输出设备 存储程序 将程序与数据一起存储、处理 硬件 CPU 组成 运算器 控制器 寄存器 参数 字长 一次处理数据的能力 32位CPU 64位CPU 主频 MIPS 指令集 复杂指令集（CISC） 精简指令集（RISC） 高速缓存 寻址单元=2^n 制造工

在幕布中查看（密码：LAN） 计算机科学家 帕斯卡【法】 机械计算机：加法器 莱布尼茨【徳】 乘法器 巴贝奇【英】 分析机 阿达·洛芙莱斯【英】 首个程序员 女 图灵【英】 同性恋 死于自杀 2013年被赦免 图灵机 停机问题 通用图灵机 二战中破译密码 人工智能之父 《机器能思考吗》 图灵测试 图灵奖 计算机界的诺贝尔奖 香农【美】 信息理论、信