Pistachio's Blog

Later equals never.

linux常用命令

SCP上传下载1.从服务器拉取文件夹到本地scp -r root@xx.xxx.x.xx:文件所在路径 /home/Document 2.从本地上传文件到服务器scp -r /home/Document root@xx.xxx.x.xx:/home/default 3.rsync文件压缩tar -xvf file.tar tar -xzvf file.tar.gz tar -xjvf f......

Posted by Liao on 2019-09-12

Bellman Ford

1.定义 Bellman-Ford 算法是一种用于计算带权有向图中单(一个)源(顶点)最短路径的问题（单源指的是只有一个起点）：给定一个起点，求它到所有结点的最短路径。Bellman-Ford 算法能适应一般的情况（即存在负权边的情况），V*E<10^7。 Bellman-Ford 算法采用动态规划进行设计，时间复杂度 O(V*E)，其中 V 为顶点数量，E 为边的数量......

Posted by Liao on 2019-09-04

欧拉函数

1. 欧拉函数对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目。例如φ(8)=4，因为1,3,5,7均和8互质。对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1) 欧拉函数公式$$φ(x) = x \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times …..\times (1......

Posted by Liao on 2019-09-03

快速幂

快速幂模板 12345678910111213long long fastpow(long long x,long long n){ int base = x; int res = 1; while(n) { if(n&1) res = (res%mod * base%mod)%mod; b......

Posted by Liao on 2019-09-02

BFS

1. 定义树的BFS：从根节点开始，从左到右，从上到下进行的层次遍历；图的BFS：从根节点出发，找与该结点相邻的所有结点，如此类推，一层层遍历。图没有根结点，就得找一个点作为根节点。例如是A，则找与A相连距离1条边的结点，有B、C；再找与A距离2条边的结点有D、E；最后与A距离为3的结点有F。故BFS的遍历顺序为：ABCDEF 注意，取的点不同，有不同的遍历结......

Posted by Liao on 2019-08-31

并查集

一. 定义并查集 (Disjoint set) 是一种树型数据结构，用于处理一些不相交集合的合并及查询问题，或者检查图上是否存在环。 Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union：将两个子集合并成同一个集合。性质：同一个集合的任意两个顶点相连会形成环二. 分析int find(int x):通过递归查找元素所在的根节点。 void unio......

Posted by Liao on 2019-08-28

DFS

1. 定义深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。由于在不同节点上选择可以很多种，因此DFS的结果不唯一。通常使用递归or栈来实现DFS。 2.过程DFS的过程类似于栈的结构：后进先出，从根节点开始，把处理过的节点弹出栈，把出栈元素的邻接点放入栈......

Posted by Liao on 2019-08-24

STL之map

一定义C++中map提供的是一种键值对容器，里面的数据都是成对出现的。每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值。 map的底层实现时红黑树，查询的时间复杂度时log(n) 1map<type,type> mymap; 二声明1#include<map> 三插入操作1.通过inset插入 1234......

Posted by Liao on 2019-08-16

STL之set集合

一定义 set A; set中的元素已排好序 set中的元素不重复二用法 A.insert(item); A.earse(item); //删除元素item A.clear(); //清空set A.empty(); A.size() A.find(k); A.lower_bound(k) ......

Posted by Liao on 2019-08-15

优先队列

优先队列一. 定义优先队列不再遵循先入先出的原则，而是分为两种情况：最大优先队列，无论入队顺序，当前最大的元素优先出队。最小优先队列，无论入队顺序，当前最小的元素优先出队。因此可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。优先队列的入队和出队的时间复杂度和二叉堆结点上浮下沉的一样，都是O(logn)，n为队列元素个数 priorit......

Posted by Liao on 2019-08-14