pearfl / blog Goto Github PK

View Code? Open in Web Editor NEW

0.0 0.0 0.0 33 KB

Used for technical summary

Java 100.00%

blog's People

Contributors

blog's Issues

win下，hadoop中mapreduce初次运行的空指针问题

1.下载winutils.exe文件
1）下载 winutils.exe，地址为：
http://social.msdn.microsoft.com/Forums/windowsazure/en-US/28a57efb-082b-424b-8d9e-731b1fe135de/please-read-if-experiencing-job-failures?forum=hdinsight
2）把这个文件放进 d:\winutil\bin
3） mapreduce的代码中添加这段，System.setProperty("hadoop.home.dir", "d:\winutil\")

2.这个空指针问题解决后，会有一个nativeIO问题，下载Native.java，在项目中创建一个包（package），名字最好取成org.apache.hadoop.io.nativeio，然后将NativeIO.java文件粘贴进去

HTTP的工作原理

HTTP的工作原理

HTTP协议采用请求/响应模型。客户端向服务器发送一个请求报文，服务器以一个状态作为响应。

以下是HTTP请求/响应的步骤：

客户端连接到 Web 服务器：HTTP 客户端与 web 服务器建立一个 TCP 连接。
客户端向服务器发起 HTTP 请求：通过已建立的 TCP 连接，客户端向服务器发送一个请求报文。
服务器接收 HTTP 请求并返回 HTTP 响应：服务器解析请求，定位请求资源，服务器将资源副本写到 TCP 连接，由客户端读取。
释放TCP连接：若 connection 模式为 close，则服务器主动关闭TCP连接，客户端被动关闭连接，释放TCP连接；若 connection 模式为 keepalive，则该连接会保持一段时间，在该时间内可以继续接收请求。
客户端浏览器解析HTML内容：客户端将服务器响应的HTML文本解析并显示。

例如，在浏览器地址栏键入URL，按下回车键后会经历以下流程：

1.浏览器向DNS服务器请求解析该URL中域名所对应的IP地址。

2.解析出IP地址后，根据该IP地址和默认端口80，同服务器建立TCP连接。

3.浏览器发出读取文件（URL中域名后面部分对应的文件）的HTTP请求，该请求报文作为TCP三次握手的第三个报文的数据发送给服务器。

4.服务器对浏览器请求做出响应，并把对应的HTML文本发送给浏览器。

5.释放TCP连接。

6.浏览器将该HTML文本并显示内容。

HDFS-API开发

Maven进行管理

<properties>
  <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
  <maven.compiler.source>1.7</maven.compiler.source>
  <maven.compiler.target>1.7</maven.compiler.target>
  <!--定义hadoop版本-->
  <hadoop.version> 2.6.0-cdh5.15.1</hadoop.version>
</properties>

<!--引入cdh的仓库-->
<repositories>
  <repository>
    <id>cloudera</id>
    <url>https://repository.cloudera.com/artifactory/cloudera-repos</url>
  </repository>
</repositories>

<dependencies>
  <!--添加hadoop依赖包-->
  <dependency>
    <groupId>org.apache.hadoop</groupId>
    <artifactId>hadoop-client</artifactId>
    <version>${hadoop.version}</version>
  </dependency>
  <!--添加junit依赖包-->
  <dependency>
    <groupId>junit</groupId>
    <artifactId>junit</artifactId>
    <version>4.11</version>
    <scope>test</scope>
  </dependency>
</dependencies>

ubuntu更改源为阿里源

1、复制源文件备份，进入目录/etc/apt下，备份sources.list文件

sources.list是包管理工具apt所用的记录软件包仓库位置的配置文件

# sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak

2、编译源列表文件

# sudo vim /etc/apt/sources.list

如果报错：sudo:vim:command not found，说明没装vim编辑器

3、查看新版本信息

# lsb_release -c

有些网上的方案不同，和更改apt安装源时用的系统不一样有关

4、将原有的内容注释掉，添加以下内容（也可以全部删除）

deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse

5、更新软件列表

# sudo apt-get update

6、更新软件包

# sudo apt-get upgrade

最短路径算法

1.$Dijkstra$算法

解决单源最短路径问题常用 Dijkstra 算法，用于计算一个顶点到其他所有顶点的最短路径。Dijkstra 算法的主要特点是以起点为中心，逐层向外扩展（这一点类似于 bfs，但是不同的是，bfs 每次扩展一个层，但是 Dijkstra 每次只会扩展一个点），每次都会取一个最近点继续扩展，直到取完所有点为止。

注意：Dijkstra 算法要求图中不能出现负权边。

①、$Dijkstra$算法流程

我们定义带权图$ G $所有顶点的集合为$ V$，接着我们再定义已确定从源点出发的最短路径的顶点集合为$ U$，初始集合 $U $为空，记从源点$ s $出发到每个顶点$ v $的距离为 $dist_v $，初始 $dist_s$=0。接着执行以下操作：

从 $V−U $中找出一个距离源点最近的顶点$v$，将$v$加入集合$ U$。
并用 $dist_v$和顶点 $v $连出的边来更新和 $v $相邻的、不在集合 $U$中的顶点的 $dist$，这一步称为松弛操作。
重复步骤 1 和 2，直到 $V=U$或找不出一个从$ s$ 出发有路径到达的顶点，算法结束。

如果最后 $V \neq U$，说明有顶点无法从源点到达；否则每个$ dist_i$表示从 $s$ 出发到顶点$ i $的最短距离。

Dijkstra 算法的时间复杂度为$ \mathcal{O}(V^2)$，其中 $V$ 表示顶点的数量。

Dijkstra 是解决无负边权的图的单源最短路问题，经常使用邻接表存储。

不优化的时间复杂度是 $O(V^2 + E)$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, fail;
    edge() {}
    edge(int _v, int _w, int _fail) {
        v = _v;
        w = _w;
        fail = _fail;
    }
} e[M << 1];
int head[N], len;
void init() {
    memset(head, -1, sizeof(head));
    len = 0;
}
void add(int u, int v, int w) {
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}
void add2(int u, int v, int w) {
    add(u, v, w);
    add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 0;
    for (int i = 0; i < n; ++i) {
        int mi = inf;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && dis[j] < mi) {
                mi = dis[u = j];
            }
        }
        if (mi == inf) {
            return;
        }
        vis[u] = true;
        for (int j = head[u]; ~j; j = e[j].fail) {
            int v = e[j].v;
            int w = e[j].w;
            if (!vis[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
            }
        }
    }
}
int main() {
    init();
    int u, v, w;
    cin >> n >> m;
    while (m--) {
        cin >> u >> v >> w;
        add2(u, v, w);
    }
    dijkstra(1);
    cout << dis[n] << endl;
    return 0;
}

②、基于小根堆优化的$Dijkstra$算法

用一个set来维护点的集合，这样的时间复杂度就优化到了 $\mathcal{O}((V+E)\log V)$，对于稀疏图的优化效果非常好

const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int w) {  // 插入带权有向边
    e[eid].v = v;
    e[eid].w = w;
    e[eid].next = p[u];
    p[u] = eid++;
}
void insert2(int u, int v, int w) {  // 插入带权双向边
    insert(u, v, w);
    insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int dist[MAX_N];  // 存储单源最短路的结果
bool vst[MAX_N];  // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
    // 初始化 dist、小根堆和集合 U
    memset(vst, 0, sizeof(vst));
    memset(dist, 0x3f, sizeof(dist));
    min_heap.insert(make_pair(0, s));
    dist[s] = 0;
    for (int i = 0; i < n; ++i) {
        if (min_heap.size() == 0) {  // 如果小根堆中没有可用顶点，说明有顶点无法从源点到达，算法结束
            return false;
        }
        // 获取堆顶元素，并将堆顶元素从堆中删除
        set<PII, less<PII> >::iterator iter = min_heap.begin();
        int v = iter->second;
        min_heap.erase(*iter);
        vst[v] = true;
        // 进行和普通 dijkstra 算法类似的松弛操作
        for (int j = p[v]; j != -1; j = e[j].next) {
            int x = e[j].v;
            if (!vst[x] && dist[v] + e[j].w < dist[x]) {
                // 先将对应的 pair 从堆中删除，再将更新后的 pair 插入堆
                min_heap.erase(make_pair(dist[x], x));
                dist[x] = dist[v] + e[j].w;
                min_heap.insert(make_pair(dist[x], x));
            }
        }
    }
    return true;  // 存储单源最短路的结果
}

③、基于优先队列优化的$Dijkstra$算法

我们在 $node $节点里面记录对应的点的最短路，然后每次更新一个点的最短路后都把这个点压入到优先队列里面（不管之前有没有被压入到队列里面），这样就一定能够保证优先队列对的性质不会改变

这个代码的时间复杂度实际上会比用真正的堆要慢一点，因为有的点可能会入队多次，但是每一条边最多导致一次入队，所以这个算法的时间复杂度为 $\mathcal{O}(E\log E)$。其中$ E $为边的数量。

const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int w) {  // 插入带权有向边
    e[eid].v = v;
    e[eid].w = w;
    e[eid].next = p[u];
    p[u] = eid++;
}
void insert2(int u, int v, int w) {  // 插入带权双向边
    insert(u, v, w);
    insert(v, u, w);
}
int dist[MAX_N];  // 存储单源最短路的结果
bool vst[MAX_N];  // 标记每个顶点是否在集合 U 中
struct node {
    int u;
  int dist;
    node(int _u, int _dist) : u(_u), dist(_dist) {}
    bool operator < (const node &x) const {
        return dist > x.dist;
    }
}; // 记录点的结构体
bool dijkstra(int s) {
    // 初始化 dist、小根堆和集合 U
    memset(vst, 0, sizeof(vst));
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<node> min_heap;
    dist[s] = 0;
    min_heap.push(node(s, 0));
    while (!min_heap.empty())
        // 获取堆顶元素，并将堆顶元素从堆中删除
        int v = min_heap.top().u;
        min_heap.pop();
        if (vst[v]) {
            continue;
        }
        vst[v] = true;
        // 进行和普通 dijkstra 算法类似的松弛操作
        for (int j = p[v]; j != -1; j = e[j].next) {
            int x = e[j].v;
            if (!vst[x] && dist[v] + e[j].w < dist[x]) {
                dist[x] = dist[v] + e[j].w;
                min_heap.push(node(x, dist[x]));
            }
        }
    }
    return true;
}

2.$SPFA$算法

SPFA（Shortest Path Faster Algorithm）算法是单源最短路径的一种算法，通常被认为是 Bellman-ford 算法的队列优化，在代码形式上接近于宽度优先搜索 BFS，是一个在实践中非常高效的单源最短路算法。

①、$SPFA$算法流程

在 $SPFA$ 算法中，使用 $d_i$表示从源点到顶点$i$的最短路，额外用一个队列来保存即将进行拓展的顶点列表，并用 $inq_i$来标识顶点$i$是不是在队列中。

1.初始队列中仅包含源点，且源点 $s$ 的 $d_s=0$。

2.取出队列头顶点 $u$，扫描从顶点 $u$ 出发的每条边，设每条边的另一端为 $v$，边$<u,v>$ 权值为 $w$，若 $d_u+w<d_v$，则

将 $d_v$修改为 $d_u+w$
若 $v$ 不在队列中，则
将 $v $入队

3.重复步骤 2 直到队列为空

最终$ d$ 数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队，则说明没有从源点到该顶点的路径。

$SPFA$ 的空间复杂度为$ \mathcal{O}(V)$。如果顶点的平均入队次数为 $k$，则 $SPFA $的时间复杂度为 $\mathcal{O}(kE)$O，对于较为随机的稀疏图，根据经验 $k$ 一般不超过 4。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;

struct edge{
    int v, w, fail;
    edge(){}
    edge(int _v, int _w, int _fail){
        v = _v;
        w = _w;
        fail = _fail;
    }
}e[M << 1];
int head[N], len;
void init(){
    memset(head, -1, sizeof(head));
    len = 0;
    
}

void add(int u, int v, int w){
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}

void add2(int u, int v, int w){
    add(u, v, w);
    add(v, u, w);
}

int n, m;
int dis[N];
bool vis[N];

void spfa(int u){
    memset(vis, false, sizeof(vis));
    vis[u] = true;
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 0;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        u = q.front();
        q.pop();
        vis[u] = false;
        for(int j = head[u];~j;j = e[j].fail){
            int v = e[j].v;
            int w = e[j].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main() {
    
    init();
    int u, v, w;
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        add2(u, v, w);
    }
    spfa(1);
    cout<<dis[n]<<endl;
    
    return 0;
}

②、$SPFA$判断负环

$Dijkstra$不能处理有负权的图，而 $SPFA$ 可以处理任意不含负环（负环是指总边权和为负数的环）的图的最短路，并能判断图中是否存在负环

但是 $SPFA $可以用来判断负环，在进行 $SPFA $时，用一个数组 $cnt_i$来标记每个顶点入队次数。如果一个顶点入队次数 $cnt_i$大于顶点总数 n，则表示该图中包含负环。一般情况下，$SPFA$ 判负环都只用在有向图上，因为在无向图上，一条负边权的边就是一个负环了

memset(in, 0, sizeof in);
in[u] = 1;
// 修改入队部分的操作
if(!vis[v]){
    q.push(v);
    vis[v] = true;
    ++in[v];
    if(in[v] > n){
        return true;
    }
}

3、$floyd$多源最短路算法

$∀1≤k≤n,dp [i] [j] = min（dp[i] [j]，dp[i][k]+ dp [k][j]）$

int g[N][N];
void floyd(int n) {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }    
}

初识hadoop

Hadoop：提供分布式的存储（一个文件被拆分成很多个块，并且以副本的方式存储在各个节点中）和计算，是一个分布式的系统基础架构：用户可以在不了解分布式底层细节的情况下进行使用。

分布式文件系统：HDFS实现将文件分布式存储在很多的服务器上

分布式计算框架：MapReduce实现在很多机器上分布式并行计算

分布式资源调度框架：YARN实现集群资源管理以及作业的调度

常用的Hadoop发行版

Apache

优点：纯开源

缺点：不同版本/不同框架之间整合，常有jar冲突
CDH：https://www.cloudera.com/

优点：cm(cloudera manager) 通过页面一键安装各种框架

缺点：cm不开源、与社区版本有些出入
Hortonworks：HDP 企业发布自己的数据平台可以直接基于页面框架进行改造

优点：原装Hadoop、纯开源、支持tez

缺点：企业级安全不开源

virtualenv基本操作（windows环境）

1、下载virtualenv

pip install virtualenv

2、创建一个virtualenv工作目录

mkdir myproject_env

3、穿件一个python项目

virtualenv venv

4、启动virtualenv中的venv项目

cd venv\Scripts
activate

5、关闭virtualenv

需要在venv\Scripts内

deactivate

pip源修改

国内源：
新版ubuntu要求使用https源，要注意。

清华：https://pypi.tuna.tsinghua.edu.cn/simple

阿里云：http://mirrors.aliyun.com/pypi/simple/

**科技大学 https://pypi.mirrors.ustc.edu.cn/simple/

华中理工大学：http://pypi.hustunique.com/

山东理工大学：http://pypi.sdutlinux.org/

豆瓣：http://pypi.douban.com/simple/

临时使用：
可以在使用pip的时候加参数-i https://pypi.tuna.tsinghua.edu.cn/simple

例如：pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pyspider，这样就会从清华这边的镜像去安装pyspider库。

永久修改，一劳永逸：
Linux下，修改 ~/.pip/pip.conf (没有就创建一个文件夹及文件。文件夹要加“.”，表示是隐藏文件夹)

内容如下：

[global]
index-url = https://pypi.tuna.tsinghua.edu.cn/simple
[install]
trusted-host=mirrors.aliyun.com

windows下，直接在user目录中创建一个pip目录，如：C:\Users\xx\pip，新建文件pip.ini。内容同上。

模板

本模板用于2019年5月安徽省程序设计竞赛

起手

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a,ll b){
	return b == 0 ? a : gcd(b,a%b);
}

ll lcm(ll a,ll b){
	return a*b/gcd(a,b);
}

ll ksm(ll x,ll n,ll mod){
	ll res = 1;
	x = x % mod;
	while(n > 0){
		if(n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

int main(){

    freopen("in","r",stdin);

    clock_t st,ed;
    st = clock();
    /*………………*/
    ed = clock();
    printf("Use Time:%f\n",((double)(ed - st)/CLOCKS_PER_SEC));

    return 0;
}

一、深搜的剪枝策略

1.找数字

给一个数$ n$，让你找出一个只由 $0,1 $组成的十进制数 $m$，要求这个正整数 $m $可以被$ n $整除

/*
input:
2
output:
10
对于输入整数 n 的每一个值，输出 m 的相应值，保证有一个数字长度小于 19 位的数字。如果有一个给定值 n 有多个解，其中任何一个都是可以接受的
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,m;
ll f;

void dfs(ll num,ll flag,ll step){
    if(m) return ;
    if((num % n == 0) && (num != 0)){
        m = num;
        return ;
    }
    if(step == 19){
        return ;
    }
    dfs(num*10, 0, step + 1);
    if(flag == 0){
       dfs(num+1, 1, step);
    }
}

int main(){
    cin>>n;
    m = 0;
    dfs(0, 0, 1);
    cout<<m<<endl;

    return 0;
}

2.全排列

输入$n$，打印输出$1-n$的全排列

/*
input:
3
output:
6
123
132
213
231
312
321
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
ll vis[15];
ll ans[15];

void dfs(ll step){
    //输出要求满足
    if(step == n + 1){
        for(ll i=1;i<=n;i++){
            printf("%lld",ans[i]);
        }
        printf("\n");
        return ;
    }
    for(ll i=1;i<=n;i++){
        if(!vis[i]){
            vis[i] = 1;
            ans[step] = i;
            dfs(step + 1);//取了
            vis[i] = 0;
        }
    }
}

ll cnt;

int main(){

    scanf("%lld",&n);
    cnt = 1;
    for(ll i=2;i<=n;i++){
        cnt *= i;
    }
    printf("%lld\n",cnt);
    dfs(1);

    return 0;
}

3.蒜头君的旅游计划

$n$个城市，$n*n$的矩形表示每两个城市之间的火车花费，求从$1$号城市把所有景点旅游一遍并且回到$1$号城市的最小花费

/*
input:
4
0 1 1 1
1 0 2 1
5 5 0 6
1 1 3 0
output:
8
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int G[20][20];
bool vis[20];
int ans = 1000000000;
int n;

void dfs(int u, int cnt, int sum){
    if(sum >= ans){
        return ;
    }
    if(cnt == n){
        ans = min(ans, sum + G[u][1]);
    }
    vis[u] = 1;
    // 枚举当前城市可能到达的下一个城市
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i, cnt + 1, sum + G[u][i]);
        }
    }
    vis[u] = 0;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>G[i][j];
        }
    }
    dfs(1, 1, 0);
    cout<<ans<<endl;

    return 0;
}

4.正方形

首先输入一个整数 $n(4 \le n \le 20)$，表示木棍数量，接下来输入 $n $根木棍的长度 $p_i(1 \le p_i \le 10000)$

如果蒜头君能拼出正方形，输出"Yes"，否则输出"No"。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
int sum = 0;
int s1;
int le[4] = {0}, a[21], b[21] = {0};
bool ok = 0;

void dfs(int x, int j){
    if(x == 4){
        ok = 1;
        return ;
    }
    if(ok){
        return ;
    }
    if(le[x] > s1){
        return ;
    }
    if(le[x] == s1){
        dfs(x + 1, 1);
    }else{
        for(int f=j;f<=n;++f){
            if(b[f] == 0){
                b[f] = 1;
                le[x] += a[f];
                dfs(x, f + 1);
                le[x] -= a[f];
                b[f] = 0;
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum += a[i];
    }
    s1 = sum / 4;
    if(sum % 4 != 0){
        cout << "No";
        return 0;
    }
    dfs(1, 1);
    if(ok){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
}

二、最短路径算法

1.$Dijkstra$算法

注意：Dijkstra 算法要求图中不能出现负权边。

①、$Dijkstra$算法流程

从 $V−U $中找出一个距离源点最近的顶点$v$，将$v$加入集合$ U$。
并用 $dist_v$和顶点 $v $连出的边来更新和 $v $相邻的、不在集合 $U$ 中的顶点的 $dist$，这一步称为松弛操作。
重复步骤 1 和 2，直到 $V=U$或找不出一个从$ s$ 出发有路径到达的顶点，算法结束。

如果最后 $V \neq U$，说明有顶点无法从源点到达；否则每个$ dist_i$表示从 $s$ 出发到顶点$ i $的最短距离。

Dijkstra 算法的时间复杂度为$ \mathcal{O}(V^2)$，其中 $V$ 表示顶点的数量。

Dijkstra 是解决无负边权的图的单源最短路问题，经常使用邻接表存储。

不优化的时间复杂度是 $O(V^2 + E)$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, fail;
    edge() {}
    edge(int _v, int _w, int _fail) {
        v = _v;
        w = _w;
        fail = _fail;
    }
} e[M << 1];
int head[N], len;
void init() {
    memset(head, -1, sizeof(head));
    len = 0;
}
void add(int u, int v, int w) {
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}
void add2(int u, int v, int w) {
    add(u, v, w);
    add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 0;
    for (int i = 0; i < n; ++i) {
        int mi = inf;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && dis[j] < mi) {
                mi = dis[u = j];
            }
        }
        if (mi == inf) {
            return;
        }
        vis[u] = true;
        for (int j = head[u]; ~j; j = e[j].fail) {
            int v = e[j].v;
            int w = e[j].w;
            if (!vis[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
            }
        }
    }
}
int main() {
    init();
    int u, v, w;
    cin >> n >> m;
    while (m--) {
        cin >> u >> v >> w;
        add2(u, v, w);
    }
    dijkstra(1);
    cout << dis[n] << endl;
    return 0;
}

②、基于小根堆优化的$Dijkstra$算法

用一个set来维护点的集合，这样的时间复杂度就优化到了 $\mathcal{O}((V+E)\log V)$，对于稀疏图的优化效果非常好

const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int w) {  // 插入带权有向边
    e[eid].v = v;
    e[eid].w = w;
    e[eid].next = p[u];
    p[u] = eid++;
}
void insert2(int u, int v, int w) {  // 插入带权双向边
    insert(u, v, w);
    insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int dist[MAX_N];  // 存储单源最短路的结果
bool vst[MAX_N];  // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
    // 初始化 dist、小根堆和集合 U
    memset(vst, 0, sizeof(vst));
    memset(dist, 0x3f, sizeof(dist));
    min_heap.insert(make_pair(0, s));
    dist[s] = 0;
    for (int i = 0; i < n; ++i) {
        if (min_heap.size() == 0) {  // 如果小根堆中没有可用顶点，说明有顶点无法从源点到达，算法结束
            return false;
        }
        // 获取堆顶元素，并将堆顶元素从堆中删除
        set<PII, less<PII> >::iterator iter = min_heap.begin();
        int v = iter->second;
        min_heap.erase(*iter);
        vst[v] = true;
        // 进行和普通 dijkstra 算法类似的松弛操作
        for (int j = p[v]; j != -1; j = e[j].next) {
            int x = e[j].v;
            if (!vst[x] && dist[v] + e[j].w < dist[x]) {
                // 先将对应的 pair 从堆中删除，再将更新后的 pair 插入堆
                min_heap.erase(make_pair(dist[x], x));
                dist[x] = dist[v] + e[j].w;
                min_heap.insert(make_pair(dist[x], x));
            }
        }
    }
    return true;  // 存储单源最短路的结果
}

③、基于优先队列优化的$Dijkstra$算法

const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int w) {  // 插入带权有向边
    e[eid].v = v;
    e[eid].w = w;
    e[eid].next = p[u];
    p[u] = eid++;
}
void insert2(int u, int v, int w) {  // 插入带权双向边
    insert(u, v, w);
    insert(v, u, w);
}
int dist[MAX_N];  // 存储单源最短路的结果
bool vst[MAX_N];  // 标记每个顶点是否在集合 U 中
struct node {
    int u;
  int dist;
    node(int _u, int _dist) : u(_u), dist(_dist) {}
    bool operator < (const node &x) const {
        return dist > x.dist;
    }
}; // 记录点的结构体
bool dijkstra(int s) {
    // 初始化 dist、小根堆和集合 U
    memset(vst, 0, sizeof(vst));
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<node> min_heap;
    dist[s] = 0;
    min_heap.push(node(s, 0));
    while (!min_heap.empty())
        // 获取堆顶元素，并将堆顶元素从堆中删除
        int v = min_heap.top().u;
        min_heap.pop();
        if (vst[v]) {
            continue;
        }
        vst[v] = true;
        // 进行和普通 dijkstra 算法类似的松弛操作
        for (int j = p[v]; j != -1; j = e[j].next) {
            int x = e[j].v;
            if (!vst[x] && dist[v] + e[j].w < dist[x]) {
                dist[x] = dist[v] + e[j].w;
                min_heap.push(node(x, dist[x]));
            }
        }
    }
    return true;
}

2.$SPFA$算法

①、$SPFA$算法流程

在 $SPFA$ 算法中，使用 $d_i$表示从源点到顶点$i$的最短路，额外用一个队列来保存即将进行拓展的顶点列表，并用 $inq_i$来标识顶点$i$是不是在队列中。

1.初始队列中仅包含源点，且源点 $s$ 的 $d_s=0$。

2.取出队列头顶点 $u$，扫描从顶点 $u$ 出发的每条边，设每条边的另一端为 $v$，边$<u,v>$ 权值为 $w$，若 $d_u+w<d_v$，则

将 $d_v$修改为 $d_u+w$
若 $v$ 不在队列中，则
将 $v $入队

3.重复步骤 2 直到队列为空

最终$ d$ 数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队，则说明没有从源点到该顶点的路径。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;

struct edge{
    int v, w, fail;
    edge(){}
    edge(int _v, int _w, int _fail){
        v = _v;
        w = _w;
        fail = _fail;
    }
}e[M << 1];
int head[N], len;
void init(){
    memset(head, -1, sizeof(head));
    len = 0;
    
}

void add(int u, int v, int w){
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}

void add2(int u, int v, int w){
    add(u, v, w);
    add(v, u, w);
}

int n, m;
int dis[N];
bool vis[N];

void spfa(int u){
    memset(vis, false, sizeof(vis));
    vis[u] = true;
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 0;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        u = q.front();
        q.pop();
        vis[u] = false;
        for(int j = head[u];~j;j = e[j].fail){
            int v = e[j].v;
            int w = e[j].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main() {
    
    init();
    int u, v, w;
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        add2(u, v, w);
    }
    spfa(1);
    cout<<dis[n]<<endl;
    
    return 0;
}

②、$SPFA$判断负环

$Dijkstra$不能处理有负权的图，而 $SPFA$ 可以处理任意不含负环（负环是指总边权和为负数的环）的图的最短路，并能判断图中是否存在负环

memset(in, 0, sizeof in);
in[u] = 1;
// 修改入队部分的操作
if(!vis[v]){
    q.push(v);
    vis[v] = true;
    ++in[v];
    if(in[v] > n){
        return true;
    }
}

3、$floyd$多源最短路算法

$∀1≤k≤n,dp [i] [j] = min（dp[i] [j]，dp[i][k]+ dp [k][j]）$

int g[N][N];
void floyd(int n) {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }    
}

三、不带权图算法

1.拓扑排序

对一个有向无环图$ G $进行拓扑排序，是将 $G$中的所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$，若边 $<u,v> \in E(G)$，则 $u$ 在线性序列中出现在 $v$之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序.

①、算法流程

拓扑排序算法主要由以下两步循环执行，直到不存在入度为 0 的顶点为止。

选择一个入度为 0 的顶点并将它输出；
删除图中从顶点连出的所有边。

循环结束，若输出的顶点数小于图中的顶点数，则表示该图中存在回路，也就是无法进行拓扑排序；否则输出的顶点序列就是一个拓扑序列。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
    int v, next;
    int len;
} E[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v) {
    E[eid].v = v;
    E[eid].next = p[u];
    p[u] = eid++;
}

int n, m;
int indegree[MAX_N];

void topo(){
    /*  如果要求为字典序，修改为
 		priority_queue <int, vector<int>, greater<int> > q;
    */
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(indegree[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int now = q.front();
        cout<<now<<endl;
        q.pop();
        for(int i=p[now];i!=-1;i=E[i].next){
            int v = E[i].v;
            indegree[v]--;
            if(indegree[v] == 0){
            	q.push(v);
        	}
    	}
    }
}

int main() {
    init();
    memset(indegree, 0, sizeof(indegree));
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u, v;
        cin>>u>>v;
        insert(u, v);
        indegree[v]++;
    }
    topo();
    return 0;
}

2.欧拉回路和欧拉路径

若图 $G$ 中存在这样一条路径，使得它恰好通过 $G$ 中每条边一次，则称该路径为欧拉路径。

若该路径是一个环路，则称为欧拉回路。

具有欧拉回路的图称为欧拉图。

具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

①、有关欧拉路的重要性质

无向图

一个无向图 $G$ 存在欧拉路径当且仅当无向图 $G$ 是连通图，且该图中有两个奇度顶点（度数为奇数）或者无奇度顶点。
当无向图 $G$ 是包含两个奇度顶点的连通图时，$G$ 的欧拉路径必定以这两个奇度顶点为端点。
一个无向图 $G$ 存在欧拉回路当且仅当无向图 $G$ 连通且不存在奇度顶点。

有向图

一个有向图 $G$ 存在欧拉路径当且仅当 $G$ 是弱连通的有向图（将有向边全部看成无向边后该图是连通图），且满足以下两个条件之一：
- 所有顶点的入度和出度相等；
- 有一个顶点的出度与入度之差为 $1$，一个顶点的出度与入度之差为 $−1$，其余顶点的入度和出度相等。
当有向图 $G$ 包含两个入度和出度不相同的顶点且有欧拉路径时，欧拉路径必定以这两个入度出度不相同的顶点为端点。
一个有向图 $G$ 存在欧拉回路当且仅当图 $G$ 是连通的有向图，且所有顶点的入度和出度相等。

3.例题

1.拓扑判环

这个代码每次仅将一个入度为0的元素放入队列中

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[105][105], r[105];

void topu(int n){
    int rr = 0, s = 0, flag = 0;
    while(rr < n && !flag){
        flag = 1;//1标记拓扑队列内没有元素
        for(int i=0;i<n;i++){
            if(r[i] == 0){
                s++;// 进拓扑的元素+1
                flag = 0; // 标记要开始新的拓扑
                r[i]--; //更改入度
                for(int j=0;j<n;j++){
                    // 扫描更改所有入度
                    if(a[i][j]){
                        r[j]--;
                    }
                }
                break;
            }
        }
    }
    if(s == n){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

int main() {

    int n, m;
    cin>>n>>m;
    memset(a, 0, sizeof(a));
    memset(r, 0, sizeof(r));

    for(int i=0;i<m;i++){
        int x, y;
        cin>>x>>y;
        if(!a[x][y]){
            a[x][y] = 1;
            r[y]++;
        }
    }

    topu(n);

    return 0;
}

四、状态压缩动态规划

1.例题讲解

$n$ 个人在做传递物品的游戏,编号为 $1-n$。游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系。求当物品经过所有 $n$ 个人后，整个过程的总代价是多少。

解析

我们就可以将“当前传递过物品的人的集合、最后一个传递到的人”作为状态进行动态规划，用$dp[i][j]$表示这个状态的最小代价。

这里，我们就要用到状态压缩：把“传递过物品的人的集合”压缩为一个整数。我们用二进制表示这个集合，比如一共$5$个人，第 $0、3、4 $个人被传递过（为了方便起见，序号从 $0$ 开始），就用 $11001_{(2)}$表示，该集合的十进制表示为 $25$。

注意到 $j$ 是最后一个被传递到的人，也就是说必须在传递集合 $i$ 中标记为 $1$，即合法状态必须满足$(i & (1 << j)) != 0$。如果从 $j$ 传递到 $k$，那 $k$ 必须不在集合 $i$ 里，即必须满足$(i & (1 << k)) == 0$。

转移方程为$dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + a[j][k])$，其中$a[j][k]$为从 $j$ 传递到 $k$ 的代价。

因为开始时物品可以在任意一人手上，所以把$dp[1 << i][i]$置为 $0$，其它状态置为无穷大。

总的时间复杂度为 $\mathcal{O}(n^22^n)$。

memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; i++) {
    dp[1 << i][i] = 0;
}
for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
        if (i & (1 << j)) {
            for (int k = 0; k < n; k++) {
                if (!(i & (1 << k))) {
                    dp[i | 1 << k][k] =
                        min(dp[i | 1 << k][k], dp[i][j] + a[j][k]);
                }
            }
        }
    }
}
int ans = INF;
for (int i = 0; i < n; i++) {
    ans = min(ans, dp[(1 << n) - 1][i]);
}

2.旅行商问题

$TSP$ 是一道经典的 $NP-$完全问题，在规模比较小的时候可以用动态规划求解。

有 $n $个城市，两两之间均有道路直接相连。给出每个城市 $i$ 和 $j$ 之间的道路长度 $dist(i,j)$，求一条经过每个城市一次且仅一次，最后回到起点的路线，使得经过的道路总长度最短。$ n \le16$ ，城市编号为 $0\sim n-1$。

因为路线是一个环，可以规定任意点为起点和终点，不妨设城市 $0$ 为起点和终点。设 $d(S,i)$表示当前在城市$i$，已访问城市集合为 $S$ 的最短长度，则 $d(S,i)=\min{ d(S-{i},j)+dist(j,i)|i\in S}$。

初始时 $d(0,{0})=0$，最终答案为$ \min {d({0,1,2,\cdots,n-1},i)+dist(i,0)|i\ne0}$。

时间复杂度为 $\mathcal{O}(n^22^n)$。

memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;
for (int s = 0; s < (1 << n); s++) {
    for (int i = 0; i < n; i++) {
        if (s & (1 << i)) {
            for (int j = 0; j < n; j++) {
                if (j != i && (s & (1 << j))) {
                    dp[s][i] =
                        min(dp[s][i], dp[s ^ 1 << i][j] + dist[j][i]);
                }
            }
        }
    }
}
int ans = INF;
for (int i = 1; i < n; i++) {
    ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
}

3.取方格问题

给定一个 $n \times m$的矩阵，行数和列数都不超过$20$，其中有些格子可以选，有些格子不能选。现在你需要从中选出尽可能多的格子，且保证选出的所有格子之间不相邻（没有公共边）。

#include <iostream>
using namespace std;
int a[21][20];

int state[21];
int dp[21][1 << 20];

bool ok(int now){ //判断行内是否相交
    return (now & (now >> 1)) == 0;
}

bool fit(int now, int i){ //判断选取状态是否和符合第i行的输入
    return (now | state[i]) == state[i];
}

bool not_intersect(int now, int prev){ //判断状态now和状态prev能否放在相邻的行
    return (now & prev) == 0;
}

int count(int now){ // 统计状态Now选取了多少个元素
    int s = 0;
    while(now){
        s += (now & 1);
        now >>= 1;
    }
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;
    // 行从 1 开始，列从 0 开始，这样后面处理起来方便
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    
    // 二维矩阵压成一维
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]){
                state[i] += (1 << j);
            }
        }
    }
    
    // 最外层一共n行，行位元素集合为1<<m
    // 找到一个可行的行以后，枚举上一行的所有状态
    for(int i=1;i<=n;i++){
        for(int j=0;j<(1<<m);j++){
            if(ok(j) && fit(j, i)){
                for(int k=0;k<(1<<m);k++){
                    if(ok(k) && fit(k, i-1) && not_intersect(j, k)){
                        dp[i][j] = max(dp[i][j], dp[i-1][k] + count(j));
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i=0;i<(1<<m);i++){
        ans = max(ans, dp[n][i]);
    }
    cout<<ans<<endl;
    return 0;
}

五、二分法

1. 分割数组的最大值

例题：对于一串数$num$，比如$num=[1,3,4,7,1,4,3,8]$，可以将数组中连续若干个数合并为一组 gi。将这串数组分成至多$ k$组,当$k=4 $的时候，每组数的总和的最大值$max(gi)$最小是多少？

#include <iostream>
using namespace std;
const int N = 1e3 + 9;
const int inf = 0x3f3f3f3f;
int n, k, a[N];

bool check(int x){
    int now = 0, cnt = 0;
    for(int i=0;i<n;++i){
        if(now + a[i] > x){
            ++cnt;
            now = a[i];
        }else{
            now += a[i];
        }
    }
    return cnt <= k;
}

int cal(int l, int r){
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    return l;
}

int main() {
    int ma = -inf, sum = 0;
    cin >> n >> k;
    for(int i=0;i<n;++i){
        cin>>a[i];
        ma = max(ma, a[i]);
        sum += a[i];
    }
    cout<< cal(ma, sum) <<endl;
    return 0;
}

2. 01分数规划

01 分数规划是这样的一类问题，有一堆物品，每一个物品有一个收益 a i ，一个代价 bi，我们要求一个方案,使选择的 k 个元素 $ \frac{\sum{a_i}} { \sum{b_i}} ∑b_i ∑a_i $ 最大值

分数规划的基本**是，我们先假设：
$$
f(x) = \frac{\sum^{n}{0}{x_i}*{a_i}} { \sum^{n}{0}{x_i}*{b_i}}
$$
其中$x_i$ 只有两个取值 0, 1来表示是否选取第 i 个物品，并且 $\sum_0^n x_i = k$，一定选 k 个元素

继续假设有一组 x 在 f(x) = v的时候，为最优解，上式变形如下：
$$
\sum^{n}{0}{x_i}{(a_i - vb_i)} = 0
$$
我们现在对 v二分，如果 v过大的时候,$\sum^{n}{0}{x_i}{(a_i - vb_i)} < 0$,我们无论如何怎么选择这 k个元素，都不会找到一组使得$\sum^{n}_{0}{x_i}{(a_i - vb_i)} >= 0$的x。而实际上，我们只需要对n个元素按照$a_i - v*b_i$ 排序后，选出最大的k个就是最大值了

反之，v过小的时候，$\sum^{n}_{0}{x_i}{(a_i - vb_i)} > 0$ ，那么我们就能根据选出来的最大的k个$a_i - v*b_i$ 的和来判断v和最后答案的关系，从而进行二分

double g(double v) {
    for (int i = 0; i < n; ++i) { // 计算 a(x) - v * b(x)
        tmp[i] = a[i] - v * b[i];
    }
    sort(tmp, tmp + n);
    double sum = 0;
    for (int i = n - k; i < n; ++i) { // 选择 k 个最大的比值
        sum += tmp[i];
    }
    return sum;
}
double cal() {
    double l = 0, r = 1e10;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (g(mid) > 0) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}

3.三分法

三分法解决凸形或者凹形函数的极值

二分法解决连续不间断函数的零点
$$
请计算下面方程的的最大值 (0 \le \theta \le \frac{\pi}{2})
$$

$$
y = \frac{( - x + l * sin(θ)+\frac{d}{cos(θ)})}{tan(θ)}
$$
经过求导计算发现这个方程式凸函数，所以符合三分的使用要求，所以这道题目我们可以使用三分法来计算

#include <iostream>
#include <cmath>
using namespace std;
const double pi = acos(-1);
const double eps = 1e-9;

double x, y, l, d;

double f(double du){
    return (-x + l*sin(du) + d / cos(du)) / tan(du);
}

double cal(){
    double l = 0, r = pi / 2;
    while(r - l > eps){
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(f(mid) < f(mmid)){
            l = mid;
        }else{
            r = mmid;
        }
    }
    return l;
}

int main() {
    cin>>x>>l>>d;
    printf("%.3lf\n", cal());
    return 0;
}

4.两数之和

给定一个包含 $n$ 个整数的数组 $a$，保证每个数字不重复，从中取出两个不同数，使得他们的和值为$ s$，求一共有多少种不同的选取方案。

/*
input:
10 7
-3 -2 -4 4 8 9 3 -1 10 0
ouput:
4
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, s;
ll a[1000005];

int main(){
    ll ans = 0;
    cin>>n>>s;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);

    for(int i=0;i<n;i++){
        ll y = s - a[i];
        ll l = i, r = n;
        bool flag = false;

        while(l <= r){
            ll mid = (l + r) >> 1;
            if(a[mid] == y){
                flag = true;
                break;
            }else if(a[mid] < y){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        if(flag){
            ans++;
        }
    }
    cout<<ans<<endl;

    return 0;
}

5.对数方程

求解关于 x 的方程$ x + ln(x) = a$的解，其中 $a$ 为常数

/*
input:
10
output:
7.929420
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const double eps = 1e-8;
double a;
double f(double x){
    return x + log(x) - a;
}

int main(){

    cin>>a;
    double l = 0,r = 1e9;
    while(r - l > eps){
        double mid = (l + r) / 2;
        if(f(mid) <= 0){
            l = mid;
        }else{
            r = mid;
        }
    }
    printf("%.6lf\n", l);

    return 0;
}

6.气球消消乐

蒜头君有 $n$ 只气球，蒜头君把气球排成一排。初始时，气球都是白色，现在蒜头君想用 $m$ 种颜色给气球涂色，如果相邻的气球的颜色相同，这 2 个气球会发生消消乐，蒜头君希望你求出会发生消消乐的涂色方法有多少种。最后答案对$ 10^9+7 $取模。

/*
input:
3 4
output:
28
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ksm(ll x,ll n,ll mod){
	ll res = 1;
	x = x % mod;
	while(n > 0){
		if(n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

int main(){

    ll n, m;
    const ll mod = 1e9+7;
    cin>>n>>m;
    cout<<(ksm(m, n, mod) - (ksm(m-1, n-1, mod)*m)%mod + mod) % mod<<endl;
    return 0;
}

7.切割钢管

$n$根钢管，第$i$根钢管长度为$a_i$，将n根钢管切割成至少$k$根长度相同的钢管，问钢管切割后最长为多少

/*
input:
8 8
12 3 14 12 14 20 4 8
output:
7
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 10005;
int a[maxn];

int main(){

    int n, k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int l = 0, r = 100000001;
    while(l < r){
        int mid = (l + r)>>1;
        int cnt = 0;
        for(int i=0;i<n;i++){
            cnt += a[i] / mid;
        }
        if(cnt >= k){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    cout<<r - 1<<endl;

    return 0;
}

8.火车站台连锁店

铁路线上有 n 个车站，假设这条铁路线是一条直线，其中每个站点的坐标为 $x_1,x_2,\ldots,x_n$

蒜头君一共要开办 m 个连锁店，并且不希望连锁店离得太近，以使得整体的收益最大化。他希望他的连锁店之间的最近距离尽可能大，你能帮他算出这个最大的最近距离吗？

输入为$n、m、x[]$

/*
input:
5 4
5
7
10
28
9
output:
2
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 100005;
int a[maxn];
int n, m;

bool check(int mid){
    int last = 0;
    int cnt = 1;
    while(last < n - 1){
        int j;
        for(j = last+1;j<n;++j){
            if(a[j] - a[last] >= mid){
                last = j;
                ++cnt;
                break;
            }
        }
        if(j == n){
            break;
        }
    }
    if(cnt >= m){
        return 1;
    }
    return 0;
}

int main(){

    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);

    int l = 0, r = a[n-1];
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    cout<<r - 1<<endl;

    return 0;
}

六、基础数论

1.欧几里得算法

快速计算2个数的最大公约数

// 可直接用__gcd(a, b)
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

时间复杂度为$O(logN)$，可以证明其递归层数不会超过$4.7851*lgonN+1.6723$

2.Eratosthenes 素数筛选

for (int i = 2; i <= n; i++) {
    is_prime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
    if (is_prime[i]) {
        for (int j = i * i; j <= n; j +=i) {
             is_prime[j] = false;
        }
    }
}

优化后时间复杂度比$O(NloglogN)$还要低

3.积性函数

积性函数是满足下列性质的一类函数
$$
f(mn) = f(m)*f(n),∀gcd(m,n) = 1
$$
欧拉函数$ ϕ(n)$：小于等于 n 的所有数中与 n 互质的数的个数

例如$ϕ(10) = 4$，因为1,3,7,9均和10互质

欧拉函数为积性函数
$$
ϕ(x) = x(1 - (1/p1))(1 - (1/p2))(1 - (1/p3))\cdots*(1 - (1/pn)),其中 p_1,p_2 \cdots,p n 是 x 的所有质因数
$$
欧拉定理：若$a,b$互质，则有
$$
a^{ϕ(n)}≡ 1: (mod :n)
$$
特例：费马小定理
$$
a^{p-1}≡ 1: (mod :p)
$$
其他性质
$$
\displaystyle \sum^{}_{d|n}{ϕ(d) = n}
$$
求一个数的欧拉函数值

int res = n;
for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
        res = res / i * (i - 1);
        while (n % i == 0) {
            n /= i;
        }
    }
}
if (n > 1) {
    res = res / n * (n - 1);
}
cout << res << endl;

区间预处理欧拉函数

for (int i = 1; i <= n; i++) {
    phi[i] = i;
}
for (int i = 2; i <= n; i++) {
    if (phi[i] == i) {
        for (int j = i; j <= n; j += i) {
            phi[j] = phi[j] / i * (i - 1);
        }
    }
}

欧拉函数例题：
$$
给定一个整数 n，请问有多少个整数 i满足条件：gcd(i, n) = 1，1 \leq i \leq n
$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin>>n;
    int res = n;
    for(int i=2;i*i<=n;i++){
        if(n % i == 0){
            res = res / i * (i-1);
            while(n%i == 0){
                n /= i;
            }
        }
    }
    if(n > 1){
        res = res / n * (n-1);
    }
    cout<<res<<endl;

    return 0;
}

4.矩阵

矩阵乘法

struct matrix {
   int n, m;
   int a[100][100];
};
// A.m == B.n
matrix matrix_mul(matrix A, matrix B) {
    matrix C;
    C.n = A.n;
    C.m = B.m;
    for (int i = 0; i < A.n; ++i) {
        for (int j = 0; j < B.m; ++j) {
            C.a[i][j] = 0;
            for (int k = 0; k < A.m; ++k) {
                C.a[i][j] += A.a[i][k] * B.a[k][j];
            }
        }
    }
    return C;
}

int n; // 所有矩阵都是 n * n 的矩阵
struct matrix {
   int a[100][100];
};
matrix matrix_mul(matrix A, matrix B, int mod) {
    // 2 个矩阵相乘
    matrix C;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            C.a[i][j] = 0;
            for (int k = 0; k < n; ++k) {
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
            }
        }
    }
    return C;
}
matrix unit() {
    // 返回一个单位矩阵
    matrix res;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                res.a[i][j] = 1;
            } else {
                res.a[i][j] = 0;
            }
        }
    }
    return res;
}
matrix matrix_pow(matrix A, int n, int mod) {
    // 快速求矩阵 A 的 n 次方
    matrix res = unit(), temp = A;
    for (; n; n /= 2) {
        if (n & 1) {
            res = matrix_mul(res, temp, mod);
        }
        temp = matrix_mul(temp, temp, mod);
    }
    return res;
}

七、线段树和树状数组基础

1.线段树

1.建树

const int maxn = 10010;
int minv[4 * maxn], a[maxn];
// id 表示结点编号，l, r 表示左右区间
void build(int id, int l, int r) {
    if (l == r) {
        minv[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    // pushup函数
    minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}

2.单点更新

// 把 x 位置更为成为 v
void update(int id, int l, int r, int x, int v) {
    if (l == r) {
        minv[id] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        update(id << 1, l, mid, x, v);
    } else {
        update(id << 1 | 1, mid + 1, r, x, v);
    }
    pushup(id);
}

3.单点查询

int query(int id, int l, int r, int x) {
    if (l == r) {
        return minv[id];
    }
    int mid = (l + r) >> 1;
    if (mid <= x) {
        return query(id << 1, l, mid, x);
    } else {
        return query(id << 1 | 1, mid + 1, r, x);
    }
}

4.区间查询

int query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {  // 如果完全包含，直接返回
        return minv[id];
    }
    int mid = (l + r) >> 1;
    int ans = inf;
    if (x <= mid) {
        ans = min(ans, query(id << 1, l, mid, x, y));  // 如果左区间包含，递归的查询左子树
    }
    if (y > mid) {
        ans = min(ans, query(id << 1 | 1, mid + 1, r, x, y));  // 如果右区间包含，递归的查询右子树
    }
    return ans;
}

2.树状数组

1.区间查询

//getsum(r) - getsum(l-1)
int lowbit(int x){
    return x & -x;
}

int getsum(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += C[i];
    }
    return res;
}

2.单点更新

void update(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
         C[i] += v;
    }
}

3.差分序列

给定包含 $n$ 个数的数组 $a_1, a_2, \cdots a_n$。有 $q$ 次操作

每次操作把区间$ [l, r$] 上的数加上 $v$。最后求出数列每个位置的数。

我们对于数列做差分，得到差分序列 $d$。那么对于每次更新区间$ [l, r]$，实际上只有$ a_l - a_{l - 1}$和 $a_{r + 1} - a_r$的值会发生变化，也就是 $d_{l}$会增加 $v$，$d_{r + 1}$会减少 $v$。那么每次更新只需要处理差分序列中的两个值。

得到最后的差分序列，然后还原成原数列就可以了。

#include <iostream>
using namespace std;
const int maxn = 110;
int a[maxn], d[maxn];
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    for(int i=1;i<=n;++i){
        d[i] = a[i] - a[i-1];
    }
    int q;
    cin>>q;
    while(q--){
        int l,r,v;
        cin>>l>>r>>v;
        d[l] += v;
        d[r+1] -= v;
    }
    for(int i=1;i<=n;++i){
        a[i] = a[i-1] + d[i];
        cout<<a[i]<<" ";
    }
    return 0;  
}

4.杂乱的模板

1.线段树求区间最大值(区间和值需要修改一下max部分，改为+)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 200005;
int c[N << 4];

void update(int o, int l, int r, int x, int v){
    if(x <= l && r <= x){
        c[o] = v;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid){
        update(o << 1, l, mid, x, v);
    }
    if(mid < x){
        update(o << 1 | 1, mid + 1, r, x, v);
    }
    c[o] = max(c[o << 1] , c[o << 1 | 1]);
}

int query(int o, int l, int r, int x, int y){
    if(x <= l && r <= y){
        return c[o];
    }
    int mid = l + r >> 1;
    int res = 0;
    if(x <= mid){
        res = max(res, query(o << 1, l, mid, x, y));
    }
    if(mid < y){
        res = max(res, query(o << 1 | 1, mid + 1, r, x, y));
    }
    return res;
}

int main() {
    int n, v, m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> v;
        update(1, 1, n, i, v);
    }
    string s;
    while(m--){
        int x,y;
        cin >> s;
        cin >> x >> y;
        if(s[0] == 'Q'){
            cout<<query(1, 1, n, x, y)<<endl;
        }else if(s[0] == 'U'){
            update(1, 1, n, x, y);
        }
    }

    return 0;
}

2.区间修改(lazy标记)

#include<cstdio>
#include<algorithm> 
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+7;
int N,Q;
LL a[maxn],t[4*maxn],laz[4*maxn];
void build(int rt,int l,int r)
{
	if(l==r)
	{
		t[rt]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	t[rt]=t[rt<<1]+t[rt<<1|1]; 
}
void pushdown(int rt,int l,int r)
{
	if(laz[rt]==0)
		return;
	int mid=(l+r)>>1;
	t[rt<<1]+=laz[rt]*(mid-l+1);
	laz[rt<<1]+=laz[rt];
	t[rt<<1|1]+=laz[rt]*(r-mid);
	laz[rt<<1|1]+=laz[rt];
	laz[rt]=0; 
}
void updata(int rt,int l,int r,int a,int b,LL c)
{
	if(a<=l&&r<=b)
	{
		t[rt]+=c*(r-l+1);
		laz[rt]+=c;
		return;	
	}
	pushdown(rt,l,r);
	int mid=(l+r)>>1;
	if(b<=mid)
		updata(rt<<1,l,mid,a,b,c);
	else if(a>mid)
		updata(rt<<1|1,mid+1,r,a,b,c);
	else
	{
		updata(rt<<1,l,mid,a,b,c);
		updata(rt<<1|1,mid+1,r,a,b,c);
	}
	t[rt]=t[rt<<1]+t[rt<<1|1]; 
}
LL query(int rt,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
		return t[rt];
	if(r<ql||l>qr)
		return 0;
	pushdown(rt,l,r);
	int mid=(l+r)>>1;
	return query(rt<<1,l,mid,ql,qr)+query(rt<<1|1,mid+1,r,ql,qr);
}
int main()
{
	scanf("%d %d",&N,&Q);
	for(int i=1;i<=N;i++)
		scanf("%lld",&a[i]);
	build(1,1,N);
	while(Q--)
	{
		getchar();
		char C=getchar();
		int a,b;
		scanf("%d %d",&a,&b);
		if(C=='C')
		{
			LL c;
			scanf("%lld",&c);
			updata(1,1,N,a,b,c);
		}
		else
			printf("%lld\n",query(1,1,N,a,b));
	}
	return 0; 
}

八、考研复习着玩（杂项）~

1.KMP算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<"["<<x<<"]"<<endl
#define bug printf("***********\n")

void read(int &x){
    char ch = getchar();x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

const int maxn = 1000005;
const int maxm = 10005;
char a[maxn],b[maxm];
int nex[maxm];
int n,m;

int kmp(){
    int i1=0,i2=0,ans=0;
    while(i1 < n){
        if(i2 == -1 || a[i1] == b[i2]){
            i1++;
            i2++;
        }
        else i2 = nex[i2];
        if(i2 == m){
            i2 = 0;
            ans++;
        }
    }
    return ans;
}

void getnext(){
    memset(nex,-1,sizeof(nex));
    nex[0] = -1;
    nex[1] = 0;
    int i = 2;
    int cn = 0;
    while(i <= m){
        if(b[i-1] == b[cn]){
            nex[i++] = ++cn;
        }else if(cn > 0){
            cn = nex[cn];
        }else{
            nex[i++] = 0;
        }
    }
    /*for(int j=0;j<5;j++){
        cout<<nex[j]<<" ";
    }*/
}


int main(){
    //freopen("in","r",stdin);
    int T;
    scanf("%d",&T);
    while(~(scanf("%s",a))){
        if(a[0]=='#') break;
        scanf("%s",&b);
        //cin>>b>>a;
        n = strlen(a);
        m = strlen(b);
        getnext();
        cout<<kmp()<<endl;
    }

    return 0;
}

2.bitset

构造函数
bitset<n> b;
b有n位，每位都为0.参数n可以为一个表达式.
如bitset<5> b0;则”b0”为”00000”;

bitset<n> b(unsigned long u);
b有n位,并用u赋值;如果u超过n位,则顶端被截除
如:bitset<5>b0(5);则”b0”为”00101”;

bitset<n> b(string s);
b是string对象s中含有的位串的副本
string bitval ( “10011” );
bitset<5> b0 ( bitval4 );
则”b0”为”10011”;


bitset<n> b(s, pos);
b是s中从位置pos开始位的副本,前面的多余位自动填充0;
string bitval (“01011010”);
bitset<10> b0 ( bitval5, 3 );
则”b0” 为 “0000011010”;

bitset<n> b(s, pos, num);
b是s中从位置pos开始的num个位的副本,如果num<n,则前面的空位自动填充0;
string bitval (“11110011011”);
bitset<6> b0 ( bitval5, 3, 6 );
则”b0” 为 “100110”;

os << b
把b中的位集输出到os流
os >>b
输入到b中,如”cin>>b”,如果输入的不是0或1的字符,只取该字符前面的二进制位.

bool any( ) 
是否存在置为1的二进制位？和none()相反

bool none( ) 
是否不存在置为1的二进制位,即全部为0？和any()相反.

size_t count( )
二进制位为1的个数.

size_t size( )
二进制位的个数

flip()
把所有二进制位逐位取反

flip(size_t pos)
把在pos处的二进制位取反

bool operator[]( size_type _Pos )
获取在pos处的二进制位

set()
把所有二进制位都置为1

set(pos)
把在pos处的二进制位置为1

reset()
把所有二进制位都置为0

reset(pos)
把在pos处的二进制位置为0

test(size_t pos)
在pos处的二进制位是否为1？

unsigned long to_ulong( )
用同样的二进制位返回一个unsigned long值

string to_string ()
返回对应的字符串.

3.组合数学

1.求解组合数$ C (n, k) % p $

方法1(逆元求法)：

const int N = 1e5 + 10;  
const int MOD = 1e9 + 7;  
int f[N], finv[N], inv[N];  
   
void init(void) {　　　　//要求MOD是质数，预处理时间复杂度O(n)  
    inv[1] = 1;  
    for (int i=2; i<N; ++i) {  
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD%i] % MOD;  
    }  
    f[0] = finv[0] = 1;  
    for (int i=1; i<N; ++i) {  
        f[i] = f[i-1] * 1ll * i % MOD;  
        finv[i] = finv[i-1] * 1ll * inv[i] % MOD;  
    }  
}

方法2：$C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)$

const int N = 2000 + 10;  
const int MOD = 1e9 + 7;  
int comb[N][N];  
   
void init(void) {　　　　//对MOD没有要求，预处理时间复杂度O(n^2)  
    for (int i=0; i<N; ++i) {  
        comb[i][i] = comb[i
        ][0] = 1;  
        for (int j=1; j<i; ++j) {  
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];  
            if (comb[i][j] >= MOD)  {  
                comb[i][j] -= MOD;  
            }  
        }  
    }  
}

方法3(Lucas定理，大组合数取模， HDOJ 3037为例)：

ll f[N];  
void init(int p) {                 //f[n] = n!  
    f[0] = 1;  
    for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;  
}  
   
ll pow_mod(ll a, ll x, int p)   {  
    ll ret = 1;  
    while (x)   {  
        if (x & 1)  ret = ret * a % p;  
        a = a * a % p;  
        x >>= 1;  
    }  
    return ret;  
}  
   
ll Lucas(ll n, ll k, int p) {       //C (n, k) % p  
     ll ret = 1;  
     while (n && k) {  
        ll nn = n % p, kk = k % p;  
        if (nn < kk) return 0;                   //inv (f[kk]) = f[kk] ^ (p - 2) % p  
        ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p;  
        n /= p, k /= p;  
     }  
     return ret;  
}  
   
int main(){  
    init (p);  
    printf ("%I64d\n", Lucas (n + m, n, p));  
   
    return 0;  
}

ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(a == 0 && b == 0) return -1;
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll d = extend_gcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}

ll inv(ll a,ll n){
    ll x,y;
    ll d = extend_gcd(a,n,x,y);
    if(d == 1) return (x%n+n)%n;
    else return -1;
}

ll ksm(ll x,ll n,ll mod){
	ll res = 1;
	x = x % mod;
	while(n > 0){
		if(n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
//m 中 选 n 个
ll getc(ll m,ll n){
    ll mc=1,nc=1;
    for(ll i=m;i>m-n;i--){
        mc*=i;
        mc%=mod;
    }
    for(ll i=n;i>=1;i--){
        nc*=i;
        nc%=mod;
    }
    return mc*inv(nc,mod)%mod;
}

2.二项式定理

又称牛顿二项式定理，是指两个整数的整数幂次的展开式。 $ \displaystyle (x+y)^n=\sum C_n^i x^{n-i}y^i=\binom n 0 x^n+\binom n 1 x^{n-1}y+\cdots+\binom n n y^n$

4.并查集

int par[MAX_N];
int rank[MAX_N];

//初始化n个元素 
void init(int n){
	for(int i=0;i<n;i++){
		par[i] = i;
		rank[i] = 0;
	}
}

//查询树的根 
int find(int x){
	if(par[x] == x){
		return x;
	}else{
		return par[x] = find(par[x]);
	}
}

//合并x和y所属的集合 
void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rank[x] < rank[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(rank[x] == rank[y]) rank[x]++;
	}
}

//判断x和y是否属于同一个集合
bool same(int x,int y){
	return find(x) == find(y);
}

5.搜索

DFS

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
 
int n,m;
char field[105][105]; //园子
 
void dfs(int x,int y){
    field[x][y]='.';
    for(int dx = -1;dx <= 1;dx++){
        for(int dy = -1;dy <= 1;dy++){
            int nx=x+dx,ny=y+dy;
            if(nx>=0 && nx<n && ny<m && ny>=0 && field[nx][ny] =='W') dfs(nx,ny);
        }
    }
    return ;
}
 
void solve(){
    int res = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(field[i][j]=='W'){
                dfs(i,j);
                res++;
            }
        }
    }
    printf("%d\n",res);
}
 
void init(){
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%s",field[i]);
}
 
int main()
{
    //freopen("input.txt","r",stdin);
    init();
    solve();
 
 
    return 0;
}

BFS

#include<bits/stdc++.h>
using namespace std;
 
struct node
{
    int x,y,step;
};
 
int vis[8][8];//8X8储存棋盘
int sx,sy,ex,ey,ans;
int to[8][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};
//第一个8对应的是马的8种移动情况
//第二个2代表的是ch1横坐标和纵坐标变化时对应的数值
 
int check(int x,int y)
{
    if(x<0 || y<0 || x>=8 || y>=8)//超出了棋盘的范围
    return 1;//超出范围，返回1
     
    if(vis[x][y])//非0为真 ，此处为检验该位置是否之前已经用过
    return 1;//该位置以前使用过，返回1
    return 0;//该位置没有超出范围且没有用过，返回0
}
 
void bfs()//void结尾不需要return
{
    int i;
    queue<node> Q;//队列容器
    node a,next;//a和next变成结构体头
    a.x = sx;//ch1横坐标
    a.y = sy;//ch1纵坐标
    a.step = 0;// 目前ch1的坐标变化步骤为0
    vis[sx][sy] = 1;//将ch1目前坐标的位置的数值标志为1
    Q.push(a);//将a整个扔进去，Q是node类型，只能向其中添加node类型的元素，
    //node类型看作一个元素而一个node元素又包含其他的元素
    while(!Q.empty())//若Q不空则运行
    {
        a = Q.front();//返回第一个元素，队顶元素
        //访问queue队首元素，如例：q.front()，即最早被压入队列的元素
        Q.pop();//弹出Q中的第一个元素，并且不会返回数值（出队）
         
        if(a.x == ex && a.y == ey)//ch1是否到达ch2的坐标
        {
            ans = a.step;//把当前的步骤数赋给ans
        }
         
        for(i = 0;i<8;i++)
        {
            next = a;//pop已经弹出上一个队顶元素，现在是下一个
            next.x+=to[i][0];//ch1的横坐标的变化
            next.y+=to[i][1];//ch1的纵坐标的变化
            if(check(next.x,next.y))//调用上面的实参函数check
            continue;//如果返回为1，跳出本次循环，后面三步骤跳过
            next.step = a.step+1;//目前进行过的步骤次数+1
            vis[next.x][next.y] = 1;//将该位置变更状态为已经使用过的位置
            Q.push(next);//将next整个扔进队列里面
        }
    }
    return ;
} 
 
int main()
{
    char ch1[10],ch2[10];
    while(~scanf("%s%s",ch1,ch2))//等价于！=EOF
    {
        //ASCII码
        sx = ch1[0]-'a';//ch1横坐标
        sy = ch1[1]-'1';//ch1纵坐标
        ex = ch2[0]-'a';//ch2横坐标
        ey = ch2[1]-'1';//ch2纵坐标
        memset(vis,0,sizeof(vis));//将vis数组整个清零
        bfs();//调用bfs函数
        printf("To get from %s to %s takes %d knight moves.\n",ch1,ch2,ans);
    }
 
    return 0;
}

6.dp

1.01背包

for(int i=1;i<=N;i++){
    for(int j=0;j<=V;j++){
        if(j>=c[i]){
            dp[i][j] = max(dp[i-1][j-c[i]]+w[i], dp[i-1][j]);
        }else{
            dp[i][j] = dp[i-1][j];
        }
    }
}

for(int i=1;i<=N;i++){
    for(int j=V;j>=c[i];j--){
        dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
    }
}

2.完全背包

for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            if(j >= c[i]){
                dp[i][j] = max(dp[i][j-c[i]]+w[i], dp[i-1][j]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

for(int i=1;i<=N;i++){
        for(int j=c[i];j<=V;j++){
            dp[j] = max(dp[j-c[i]]+w[i], dp[j]);
        }
    }

3.多重背包

for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            for(int k=0;k<=n[i];k++){
                if(j >= c[i]*k){
                    dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k, dp[i][j]);
                }
            }
        }
    }

for(int i=1;i<=N;i++){
        for(int j=V;j>=0;j--){
            for(int k=0;k<=n[i];k++){
                if(j>=c[i]*k){
                    dp[j] = max(dp[j - c[i]*k]+w[i]*k, dp[j]);
                }
            }
        }
    }

二进制优化

#include <iostream>
using namespace std;
int n[110], c[110], w[110];
int nc[1000], nw[1000];
int dp[5010];
int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; ++i) {
        cin >> w[i] >> c[i] >> n[i];
    }
    int ncnt = 0;
    // 二进制拆分
    for (int i = 1; i <= N; ++i) {
        int k;
        // 找到最大的 k
        for (k = 1; n[i] - (1 << k) + 1 > 0; ++k) {
            nc[ncnt] = (1 << (k - 1)) * c[i];
            nw[ncnt] = (1 << (k - 1)) * w[i];
            ++ncnt;
        }
        --k;
        // 最后一组
        nc[ncnt] = (n[i] - (1 << k) + 1) * c[i];
        nw[ncnt] = (n[i] - (1 << k) + 1) * w[i];
        ++ncnt;
    }
    // 01 背包
    for (int i = 0; i < ncnt; ++i) {
        for (int j = V; j >= nc[i]; --j) {
            dp[j] = max(dp[j], dp[j - nc[i]] + nw[i]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

更加易懂的二进制优化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool dp[500005];
int n[10];
int nc[500005];
int flag = 0;

int main(){
    freopen("dolls.in","r",stdin);
    freopen("dolls.out","w",stdout);
    memset(n, 0, sizeof(n));
    memset(dp, false, sizeof(dp));

    int V = 0;
    int k = 0;

    for(int i=1;i<=6;i++){
        cin>>n[i];
        if(n[i]) dp[i] = true;
        V = V + n[i] * i;
    }
    if(V % 2 == 1){
        cout<<"Can't be divided."<<endl;
		return 0;
    }

    int ncnt = 0;
    for(int i=1;i<=6;i++){
        int c = n[i];
        for(int k = 1;k <= c; k = k * 2){
            ++ncnt;
            nc[ncnt] = k*i;
            c -= k;
        }
        ++ncnt;
        nc[ncnt] = c * i;

    }

    dp[0] = true;
    for(int i=1;i<=ncnt;i++){
        for(int j=V/2;j>=nc[i];j--){
            dp[j] |= dp[j - nc[i]];
            if(dp[V/2]){
                break;
            }
        }
        if(dp[V/2]){
            break;
        }
    }

    if(dp[V/2]) cout<<"Can be divided."<<endl;
	else cout<<"Can't be divided."<<endl;

    return 0;
}

4.数位dp

不要62

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<"["<<x<<"]"<<endl
#define bug printf("***********\n")

void read(int &x){
    char ch = getchar();x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int n,m;
int dp[10][2],a[10];

int dfs(int len,bool lead,bool limit){
    if(len < 0) return 1;
    if(dp[len][lead] != -1 && !limit) return dp[len][lead];
    int ans = 0,i,e=limit?a[len]:9;
    for(i=0;i<=e;i++){
        if(!(lead && i == 2) && i != 4){
            ans += dfs(len-1,i==6,limit&&i == e);
        }
    }
    if(!limit){
        dp[len][lead] = ans;
    }
    return ans;
}

int solve(int x){
    int len = 0;
    while(x){
        a[len++] = x % 10;
        x /= 10;
    }
    return dfs(len-1,0,1);
}

int main(){
    //freopen("in","r",stdin);
    while(~scanf("%d %d",&n,&m)){
        if(n == 0 && m == 0) break;
        memset(dp,-1,sizeof(dp));
        memset(a,0,sizeof(a));
        printf("%d\n",solve(m) - solve(n-1));
    }

    return 0;
}

typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
    //递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
    if(pos==-1) return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
    //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    /*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/
    int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
    ll ans=0;
    //开始计数
    for(int i=0;i<=up;i++)//枚举，然后把不同情况的个数加到ans就可以了
    {
        if() ...
        else if()...
        ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
        /*这里还算比较灵活，不过做几个题就觉得这里也是套路了
        大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论
        去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目
        要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类，
        前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/
    }
    //计算完，记录状态
    if(!limit && !lead) dp[pos][state]=ans;
    /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/
    return ans;
}
ll solve(ll x)
{
    int pos=0;
    while(x)//把数位都分解出来
    {
        a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来，反正注意数位边界就行
        x/=10;
    }
    return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
}
int main()
{
    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        //初始化dp数组为-1,这里还有更加优美的优化,后面讲
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}

5.区间dp

for(int len = 1;len<=n;len++){//枚举长度
    for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
        int ends = j+len - 1;
        for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
            dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
        }
    }
}

7.字典树

const int MAX_N = 10000;  // Trie 树上的最大结点数
const int MAX_C = 26;  // 每个结点的子结点个数上限
struct Trie {
    int *ch[MAX_N];  // ch 保存了每个结点的 26 个可能的子结点编号，26 对应着 26 种小写字母，也就是说，插入的字符串全部由小写字母组成。初始全部为 -1
    int tot;  // 总结点个数（不含根结点），初始为 0
    int cnt[MAX_N];  // 以当前结点为终端结点的 Trie 树中的字符串个数

    void init() {  // 初始化 Trie 树，根结点编号始终为 0
        tot = 0;
        memset(cnt, 0, sizeof(cnt));
        memset(ch, 0, sizeof(ch));  // 将 ch 中的元素初始化为 NULL
    }

    void insert(char *str) {
        int p = 0;  // 从根结点（0）出发
        for (int i = 0; str[i]; ++i) {
            if (ch[p] == NULL) {
                ch[p] = new int[MAX_C];  // 只有 p 当包含子结点的时候才去开辟 ch[p] 的空间
                memset(ch[p], -1, sizeof(int) * MAX_C);  // 初始化为 -1
            }
            if (ch[p][str[i] - 'a'] == -1) {  // 该子结点不存在
                ch[p][str[i] - 'a'] = ++tot;  // 新增结点
            } 
            p = ch[p][str[i] - 'a'];  // 在 Trie 树上继续插入字符串 str
        }
        cnt[p]++;
    }

    int find(char *str) {  // 返回字符串 str 的出现次数
        int p = 0;
        for (int i = 0; str[i]; ++i) {
            if (ch[p][str[i] - 'a'] == -1) {
                return 0;
            }
            p = ch[p][str[i] - 'a'];
        }
        return cnt[p];
    }
};

/*
char now[MAX_LEN];
void dfs(int p, int len) {
    if (cnt[p] > 0) {
        now[len] = '\0';
        while (cnt[p] --> 0) {
            cout << now << endl;
        }
    }
    for (int i = 0; i < 26; ++i) {
        if (ch[p][i]) {
            now[len] = 'a' + i;
            dfs(ch[p][i], len + 1);
        }
    }
}
*/

8.容斥原理

求区间 $[a, b]$ 上和 $x$ 互质的数的个数。

解法：首选把 $x$分解质因子，$x=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}$ 。其中$p_1,p_2,\cdots p_m$都是质数，我们称为 $x$ 的因子。这时我们来容斥。初始的时候有 $b-a+1$个数，减去$ [a,b] $上和$ p_1,p_2,\cdots p_m$不互质的数的个数，然后加上$ [a,b]$ 上同时和 $p_1p_2,p_1p_3,\cdots p_1p_m, p_2p_3, \cdots p_{m-1}p_{m-2}$不互质的数个数$ \cdots \cdots$。

#include <iostream>
#include <vector>
using namespace std;
vector<int> breakdown(int x) {
    vector<int> l;
    for (int i = 2; i * i <= x; ++i) {
        int cnt = 0;
        while (x % i == 0) {
            ++cnt;
            x /= i;
        }
        if (cnt) {
            l.push_back(i);
        }
    }
    if (x > 1) {
        l.push_back(x);
    }
    return l;
}
int main() {
    int a = 10, b = 20, x = 15;
    vector<int> list = breakdown(x);
    int ans = 0, len = list.size();
    for (int i = 0; i < (1 << len); ++i) {
        int cnt = 0, pp = 1;
        for (int j = 0; j < len; ++j) {
            if (i & (1 << j)) {
                ++cnt;
                pp *= list[j];
            }
        }
        ans += (b / pp - (a - 1) / pp) * ((cnt & 1) ? -1 : 1);
    }
    cout << ans << endl;
    return 0;
}

9.数制转换

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll Arbitrary_change(ll n,int m){

	char s[100];
	int i;

	for(i=0;n>0;i++){
		if(n%m<10){
			s[i] = n%m + '0';
		}else{
			s[i] = n%m - 10 + 'A';
		}
		n /= m;
	}
    ll cnt = 0;
    for(n=i;n>0;n--){
        cnt = cnt * 10 + (s[n-1] - '0');
    }
    return cnt;
}

ll Ten_change(int n,string str){
    ll ans = 0, sum = 1;
    for(int i = str.length(); i > 0; i--){
        if(str[i-1] >='A') ans = ans + (str[i - 1] - 'A'+10) * sum;
		else ans = ans + (str[i - 1] - '0') * sum;
        //cout<<ans<<endl;
        sum *= n;
    }
    return ans;
    //printf("%d\n", ans);
}

int main() {

    int T;
    cin>>T;
    string x;
    ll ans;
    while(T--){
        cin>>x;
        ans = 0;
        for(int i=2;i<=10;i++){
            ans += Ten_change(i, x);
        }
        cout<<ans<<endl;
    }

    return 0;
}

10.JAVA

1.简介：
Java中两个类BigDecimal（表示浮点数）和BigInteger（表示整数）；
分别表示不可变的任意精度的整数和不可变的有符号的任意精度的十进制数（浮点数）。
主要用于高精度计算中。这两个类使得java中的大数，高精度运算变得很简单。
使用时注意每个单词首字母大写~新手很容易犯这个错/(ㄒoㄒ)/~~

使用这两个类的时候需要加上包 import java.math.*;
或是直接打：

import java.math.BigInteger;
import java.math.BigDecimal;

2.声明与赋值

通常以这种方法声明：

BigInteger a;
BigDecimal b；

也可将声明和赋值写在一起：

BigDecimal a=new BigDecimal("0");

还有常用的常量赋值方法：

A=BigInteger.ONE //=1
B=BigInteger.TEN //=10
C=BigInteger.ZERO //=0

相当于：

BigInteger A = BigInteger.valueOf(1);
BigInteger B = BigInteger.valueOf(10);
BigInteger C = BigInteger.valueOf(0);

$valueOf()$,可将数据转换为指定类型：
具体用法如下;

int a = 3;
BigInteger b = BigInteger.valueOf(a);
//即b = 3；(int)

2.输入方法：

例：

while(cin.hasNext()) //等同于!=EOF
{
    int n;
    BigInteger m;
    n=cin.nextInt(); //读入一个int;
    m=cin.BigInteger();//读入一个BigInteger;
    System.out.print(m.toString());
    System.out.print(m);
}

3.一些基础运算：

$add();$//加法
$substract(); $//减法
$multiply();$ //乘法
$divided(); $//相除取整
$remainder();$ //取余
$pow(); //a.pow(b) = a ^ b$
$gcd(); $//最大公约数
$abs(); $//绝对
$negate();$ //取反数
$mod(); //a.mod(b) = a % b = a.remainder(b)$
$max(); min();$
$compareTo(); $//比较
$equals();$ //比较是否相等

$a+b$的例子：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        BigInteger a, b;
        int T;
        Scanner in = new Scanner(System.in);
        //Scanner cin = new Scanner(new BufferedInputStream(System.in));
        T = in.nextInt();
        for (int i = 1; i <= T; ++i) {
            System.out.println("Case" + " " + i + ":");
            a = in.nextBigInteger();
            b = in.nextBigInteger();
            if (i < T) {
                System.out.println(a + " + " + b + " = " + a.add(b) );
                System.out.println();
            } else {
                System.out.println(a + " + " + b + " = " + a.add(b));
            }
        }
    }
}

a+b浮点数的例子：

import java.util.*;
import java.math.*;

public class Main{
    public static void main(String []args){
        BigDecimal a;
        BigDecimal b;
        a=new BigDecimal("0");
        b=new BigDecimal("0");
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext())
        {
            a=cin.nextBigDecimal();
            b=cin.nextBigDecimal();
            a=a.add(b);
            String str=a.stripTrailingZeros().toPlainString();
            //stripTrailingZeros()这个方法是用来去掉末尾的0的。  
            //toPlainString()这个方法是使字符串大数变成普通的数字字符组成的字符串，  
            //如果不使用这个方法很可能数字变成了科学计数法，带E的那种。  
            System.out.println(str);
        }
    }
}

Hadoop环境搭建

本搭建适用的Hadoop相关版本：CDH

CDH相关软件包下载地址：http://archive.cloudera.com/cdh5/cdh/5/

Hadoop使用版本：hadoop-2.6.0-cdh5.15.1

Hadoop下载：wget http://archive.cloudera.com/cdh5/cdh/5/hadoop-2.6.0-cdh5.15.1.tar.gz

Hive使用版本：hive-1.1.0-cdh5.15.1

hadoop安装前置要求

Java 1.8+

ssh

JDK1.8部署

拷贝本地软件包到服务器：scp jdk-8u91-linux-x64.tar.gz [email protected]:~/software/
解压jdk到~/app/：tar -zvxf jdk-8u91-linux-x64.tar.gz -C ~/app/
把jdk配置系统环境变量中： ~/.bash_profile
export JAVA_HOME=/home/hadoop/app/jdk1.8.0_91
export PATH=$JAVA_HOME/bin:$PATH
使得配置修改生效：source .bash_profile
验证：java -version

安装ssh无密码登陆

ssh-keygen -t rsa 一路回车
cd ~/.ssh
cat id_rsa.pub >> authorized_keys
chmod 600 authorized_keys

hdfs安装

解压：~/app
添加HADOOP_HOME/bin到系统环境变量
修改Hadoop配置文件

hadoop-env.sh
	export JAVA_HOME=/home/hadoop/app/jdk1.8.0_91

core-site.xml
	<property>
    	<name>fs.defaultFS</name>
    	<value>hdfs://hadoop000:8020</value>
    </property>

hdfs-site.xml
	<property>
    	<name>dfs.replication</name>
    	<value>1</value>
    </property>
		
    <property>
    	<name>hadoop.tmp.dir</name>
    	<value>/home/hadoop/app/tmp</value>
    </property>

slaves
	hadoop000

启动hdfs

第一次执行的时候一定要格式化文件系统，不要重复执行: hdfs namenode -format
启动集群：$HADOOP_HOME/sbin/start-dfs.sh

http://192.168.86.129:50070

如果发现jps ok，但是浏览器不OK？十有八九是防火墙问题

查看防火墙状态：sudo firewall-cmd --state

关闭防火墙: sudo systemctl stop firewalld.service

hadoop软件包常见目录说明

bin：hadoop客户端名单

etc/hadoop：hadoop相关的配置文件存放目录

sbin：启动hadoop相关进程的脚本

share：常用例子

hdfs命令行操作

hadoop fs [generic options]
[-appendToFile ... ]
[-cat [-ignoreCrc] ...]
[-chgrp [-R] GROUP PATH...]
[-chmod [-R] <MODE[,MODE]... | OCTALMODE> PATH...]
[-chown [-R] [OWNER][:[GROUP]] PATH...]
[-copyFromLocal [-f] [-p] [-l] ... ]
[-copyToLocal [-p] [-ignoreCrc] [-crc] ... ]
[-count [-q] [-h] [-v] [-x] ...]
[-cp [-f] [-p | -p[topax]] ... ]
[-df [-h] [ ...]]
[-du [-s] [-h] [-x] ...]
[-get [-p] [-ignoreCrc] [-crc] ... ]
[-getmerge [-nl] ]
[-ls [-C] [-d] [-h] [-q] [-R] [-t] [-S] [-r] [-u] [ ...]]
[-mkdir [-p] ...]
[-moveFromLocal ... ]
[-moveToLocal ]
[-mv ... ]
[-put [-f] [-p] [-l] ... ]
[-rm [-f] [-r|-R] [-skipTrash] ...]
[-rmdir [--ignore-fail-on-non-empty]

...]
[-text [-ignoreCrc] ...]

hadoop常用命令：
hadoop fs -ls /
hadoop fs -put
hadoop fs -copyFromLocal
hadoop fs -moveFromLocal
hadoop fs -cat
hadoop fs -text
hadoop fs -get
hadoop fs -mkdir
hadoop fs -mv 移动/改名
hadoop fs -getmerge
hadoop fs -rm
hadoop fs -rmdir
hadoop fs -rm -r

Scrapy使用教程

1.scrapy简介

特点：属于一种全家桶式的框架，在架构上很特别，都是基于插件式的增量开发模式，而且其并行运行能力非常出众

优点：

提供了内置的HTTP缓存，以加速本地开发
提供了自动节流调节机制，而且具有遵守robots.txt的设置的能力
可以定义爬行深度的限制，以避免爬虫进入死循环链接
会自动保留会话
执行自动HTTP基本认证，不需要明确保存状态
可以自动填写登录表单
Scrapy有一个内置的中间件，可以自动设置请求中的引用(referer)头
支持通过3xx响应重定向，也可以通过HTML元刷新
避免被网站使用的 $ $ meta重定向困住，以检测没有JS支持的页面
默认使用CSS选择器或XPath编写解析器
可以通过Splash或任何其他技术（如Selenium）呈现JavaScript页面
拥有强大的社区支持和丰富的插件和扩展来扩展其功能。
提供了通用的蜘蛛来抓取最常见的格式：站点地图、CSV和XML
内置支持以多种格式（JSON、CSV、XML、JSON-lines）导出收集的数据并将其存储在多个后端（FTP、S3、本地文件系统）中

缺点：

官方文档很混乱，学习曲线相对陡峭，对于初学者不容易上手
配置项目繁多，使用起来复杂

2.Scrapy安装

当前只说明windows下Scrapy的安装过程

若直接安装

c:\pip install scrapy

很大可能会出现

Microsoft Visual C++ 14.0 is required. Get it with "Microsoft Visual C++ Build Tools": http://landinghub.visualstudio.com/visual-cpp-build-tools

上面的错误

因此我们按照下面步骤来进行安装

1.安装Wheel

c:\ pip install wheel

2.安装Twisted

https://www.lfd.uci.edu/~gohlke/pythonlibs/

去上面的链接中查找与自己操作系统以及Python版本相符的Twisted安装包，下载后进入whl文件所在路径执行以下命令

c:\pip install Twisted‑19.2.0‑cp37‑cp37m‑win_amd64.whl

（此处若失败可以尝试一下win32）

3.安装scrapy

在上面链接中找到scrapy的whl包下载，并安装

c:\pip install Scrapy-1.6.0-py2.py3-none-any.whl

完成安装后再命令行执行：

c:\scrapy -h

如果正常输出了scrapy的命令帮助信息则说明安装成功

4.运行scrapy项目

如果安装完成后运行scrapy项目报以下错误

no module named win32api

则表示Windows系统中，python因为原生并不能访问windows的api，所以需要额外安装pypiwin32库

pip install pypiwin32

3.构建Scrapy项目结构

我们可以通过scrapy内置的startproject指令来快速构建scrapy项目

startproject的指令模式如下：

$ scrapy startscrapy startproject <项目名称>

项目必须以英文开头，多个单词之间可以用下划线（_）为连接符，切记不要采用-，否则会报错

当startproject被成功执行后，将会在控制台看到以下的输出信息

New Scrapy project 'my_crawler', using template directory '/Users/ray/Projects/scrapy-courses/venv/lib/python3.7/site-packages/scrapy/templates/project', created in:
    /Users/ray/Projects/scrapy-courses/my_crawler

You can start your first spider with:
    cd my_crawler
    scrapy genspider example example.com

意思是我们可以进入创建的项目的目录并执行scrapy genspider 项目名目标网站创建scrapy项目中的爬虫类。在此之前先让我们来了解以下startproject指令为我们创建的哪些的文件，目录以及它们的作用是什么

展开“my_crawler”目录可以看到以下的目录结构：

my_crawler
├── my_crawler         # 爬虫项目包目录
│   ├── __init__.py 
│   ├── items.py        # Item定义文件
│   ├── middlewares.py  # 自定义中间件
│   ├── pipelines.py    # 自定义管道
│   ├── settings.py     # 项目配置文件
│   └── spiders         # 蜘蛛类的存放目录
│       └── __init__.py
└── scrapy.cfg          # Scrapy 运行配置

4.Scrapy其他常用指令的介绍

Scrapy给我们提供了两种类型的命令：项目命令（Project-specific）需要进入项目目录执行才可生效，全局命令则不需要进入项目。

所有的命令行工具都会以以下的调用格式提供：

$ scrapy <命令> [选项] [参数]

全局指令

Scrapy提供的全局命令主要包括以下这些：

scrapy startproject <项目名> - 初始化爬虫项目，创建基本目录与必要的文件
scrapy settings --get <配置项的名称> - 在项目中运行时，该命令将会输出项目的设定值，否则输出Scrapy默认设定
scrapy runspider <spider_file.py> - 在未创建项目的情况下，运行一个编写在Python文件中的spider
scrapy shell - 以给定的URL启动Scrapy指令外壳，可以在命令行中直接操作scrapy内置的python对象（也可以借助pycharm的调试器看到）
scrapy fetch - 初始化爬虫项目，创建基本目录与必要的文件使用Scrapy下载器（downloader）下载给定的URL，并将获取到的内容打印到控制台上
scrapy view <项目名> - 在浏览器中打开给定的URL，并用一个Scrapy spider获取目标URL并将结构显示到浏览器中
scrapy version <-v> - 输出Scrapy版本，配合-v运行时，该命令同时输出Python，Twisted以及平台的信息，方便bug提交

出了startproject是常用命令之外，只有fetch和view指令比较有用，其他的指令作用不大

项目命令

scrapy crawl <蜘蛛名> - 使用指定的蜘蛛执行爬取
scrapy genspider - 在当前项目中创建spider。这仅仅是创建spider的一种快捷方法。该方法可以是使用提前定义好的模板来生成spider。
scrapy list - 列出当前项目中有多少个可用的蜘蛛（不实用）
scrapy check [-l] <蜘蛛名> - 运行contract检查。（无实际意义，不推荐使用）
scrapy edit <蜘蛛名> - 启用一个IDE编辑蜘蛛
scrapy deploy [target:project | -l | -L] - 将项目部署到Scrapyd服务
scrapy bench - 运行benchmark测试

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.

pearfl / blog Goto Github PK

blog's People

Contributors

blog's Issues

HDFS-API开发

VM虚拟机网络环境配置

最短路径算法

1.$Dijkstra$算法

①、$Dijkstra$算法流程

②、基于小根堆优化的$Dijkstra$算法

③、基于优先队列优化的$Dijkstra$算法

2.$SPFA$算法

①、$SPFA$算法流程

②、$SPFA$判断负环

3、$floyd$多源最短路算法

virtualenv基本操作（windows环境）

pip源修改

模板

起手

一、深搜的剪枝策略

1.找数字

2.全排列

3.蒜头君的旅游计划

4.正方形

二、最短路径算法

1.$Dijkstra$算法

①、$Dijkstra$算法流程

②、基于小根堆优化的$Dijkstra$算法

③、基于优先队列优化的$Dijkstra$算法

2.$SPFA$算法

①、$SPFA$算法流程

②、$SPFA$判断负环

3、$floyd$多源最短路算法

三、不带权图算法

1.拓扑排序

①、算法流程

2.欧拉回路和欧拉路径

①、有关欧拉路的重要性质

3.例题

1.拓扑判环

四、状态压缩动态规划

1.例题讲解

2.旅行商问题

3.取方格问题

五、二分法

1. 分割数组的最大值

2. 01分数规划

3.三分法

4.两数之和

5.对数方程

6.气球消消乐

7.切割钢管

8.火车站台连锁店

六、基础数论

1.欧几里得算法

2.Eratosthenes 素数筛选

3.积性函数

4.矩阵

七、线段树和树状数组基础

1.线段树

1.建树

2.单点更新

3.单点查询

4.区间查询

2.树状数组

1.区间查询

2.单点更新

3.差分序列

4.杂乱的模板

1.线段树求区间最大值(区间和值需要修改一下max部分，改为+)

2.区间修改(lazy标记)

八、考研复习着玩（杂项）~

1.KMP算法

2.bitset

3.组合数学

1.求解组合数$ C (n, k) % p $

2.二项式定理

4.并查集

5.搜索

6.dp