基础算法总结

三年前暑假学习算法的总结笔记，先全部放上来，之后根据自己现在的理解再慢慢修改。

并查集

基础模板

查找

int find(int x)	
{
	while(pre[x] != x)	
		x = pre[x];	
	return x;
}

合并

void join(int x,int y)
{
    int fx=find(x), fy=find(y);
    if(fx != fy)    
        pre[fx]=fy;
}

优化模板

路径压缩之优化函数

int find(int x) 
    {
        if (pre[x] == x)
            return x; 
        return pre[x] = find(pre[x]);  //此代码相当于先找到根结点rootx，然后pre[x]=rootx  
    }

小缺陷：只有当查找了某个节点的根节点后，才能对该查找路径上的各节点进行路径压缩。换言之，第一次执行查找操作的时候是实现没有压缩效果的，只有在之后才有效。

路径压缩之加权标记法

主要思想：加权标记法的核心在于对rank数组的逻辑控制，其主要的情况有：
1、如果rank[x] < rank[y]，则令pre[x] = y；
2、如果rank[x] == rank[y]，则可任意指定上级；
3、如果rank[x] > rank[y]，则令pre[y] = x；

void join(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)   //如果 x和 y的根节点一致，说明他们共属同一集合，则不需要合并，直接返回；否则，执行下面的逻辑
            return;
        if (rank[x] > rank[y])
            pre[y] = x;
        else
        {
            if (rank[x] == rank[y]) 
                rank[y]++;  ////如果 x的高度和 y的高度相同，则令 y的高度加1  (这里是随便选的x或者y增加)
        }
    }

以上两种方法不能同时使用

带权并查集

路径压缩

原理：先记录下原本父节点的编号，因为在路径压缩后父节点就变为根节点了，再将当前节点的权值加上原本父节点的权值，此时父节点的权值已经是父节点到根节点的权值了，因此加上这个权值就会得到当前节点到根节点的权值。

int find(int x)
    {
        if (x != parent[x])
        {
            int t = parent[x];
            parent[x] = find(parent[x]);
            value[x] += value[t];
        }
        return parent[x];
    }

带权合并

现在是已知x所在的并查集根节点为px，y所在的并查集根节点为py，如果有了x、y之间的关系，要将px并到py上，如果不考虑权值直接修改parent就行了，但是现在是带权并查集，必须得求出px与py这条边的权值是多少，很显然x到py两条路径的权值之和应该相同。

int px = find(x);
int py = find(y);
if (px != py)
{
	parent[px] = py;
	value[px] = -value[x] + value[y] + s;
}

二分函数

头文件<algorithm>

1.binary_search(arrfirst,arrlast,value)

arrlast为数组末地址后一个位置，相当于左闭右开，value为具体值.

功能：函数返回值为真或假.

2.lower_bound(arrfirst , arrlast, value) (仍为左闭右开区间)

功能：返回指向大于或等于value的第一个元素的指针。如果所有元素都小于value，则返回arrlast.

重载：lower_bound(arrfist , arrlast, value, greater())

功能：返回小于或等于value的元素地址.

3.upper_bound(arrfirst , arrlast, value)

功能：在左闭右开区间进行二分查找，返回指向大于value的第一个元素的指针。如果所有元素都小于value，则返回arrlast.

重载：upper_bound(arrfist , arrlast, value, greater())

功能：返回小于value的元素地址.

4.equal_range(arrfirst,arrlast,value)

功能：返回一个迭代器(i,j),其中i是在不破坏次序的前提下，value可插入的第一个位置，j则是在不破坏次序的前提下，value可插入的最后一个位置.因此，[i,j)内的每个元素都等同于value，而且[i,j)是[arrfirst,arrlast)之中符合此一性质的最大子区间.

以上函数在对容器使用时会返回迭代器，无需减去初始地址.

5.includes(beg,end,searchBeg,searchEnd)

功能：返回一个bool变量，两种形式都用来判断有序序列[beg,end)是否包含另一个有序序列[searchBeg,searchEnd)的全部元素.即判断子集.

折半枚举

最小化最大值

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

最大化最小值

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

二分进阶

二分深入剖析

哈夫曼树

给定n个权值，作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为哈夫曼树。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

WPL:树的带权路径长度所有叶子结点的带权路径长度之和，即为树的带权路径长度，记为WPL。

构造哈夫曼树

给定n个权值，作为n个叶子结点，构造哈夫曼树。设n个权值分别为w1、w2、······wn，哈夫曼树的构造方式如下：

（1）将n个结点加入小根堆。

（2）从小根堆中取出权值最小的两个结点合并为一棵树，树的根结点的权值即为两个子结点的权值之和。

（3）将(2)中合成的根结点加入小根堆，保持堆仍为小根堆。

（4）重复(2) (3)步骤，直到小根堆中只剩一个结点，即完成一棵哈夫曼树。

设六个结点的权值分别是{6，3，8，2，10，4}，构造哈夫曼树

哈夫曼树

WPL的三种求法

1.所有叶子结点的带权路径长度之和

WPL=24+34+43+62+82+210=80

2.除根结点外的所有结点的权值之和

WPL=2+3+4+5+6+8+9+10+14+19=80

3.除叶子结点的所有结点的权值之和

WPL=33+19+14+9+5=80

哈夫曼树的特性

1.哈夫曼树并不唯一（即左右子树可以交换），但带权路径长度是相同的。

2.权值越大的结点越靠近根结点。

3.哈夫曼树中只有叶子结点（度为0）和度为2的结点，没有度为1的结点。

4.一棵有n个叶子结点的哈夫曼树共有2n-1个结点。

BFS用队列实现的思路：

每遇到一个元素，就把这个元素的所有邻接元素放入队列，当队列不为空的时候，不断从队首拿出元素进行操作，直到队列为空。

PS:一般情况下，用递归实现BFS比较为难，所以常用队列实现。

基本模型

/*
 * @param Vs 起点 
 * @param Vd 终点 
 */
bool BFS(Node& Vs, Node& Vd){  
    queue<Node> Q;  
    Node Vn, Vw;  
    int i;  

    //初始状态将起点放进队列Q  
    Q.push(Vs);  
    hash(Vw) = true;//设置节点已经访问过了！  

    while (!Q.empty()){//队列不为空，继续搜索！  
        //取出队列的头Vn  
        Vn = Q.front();  

        //从队列中移除  
        Q.pop();  

        while(Vw = Vn通过某规则能够到达的节点){  
            if (Vw == Vd){//找到终点了！  
                //把路径记录  
                return true;//返回  
            }  

            if (isValid(Vw) && !visit[Vw]){  
                //Vw是一个合法的节点并且为白色节点  
                Q.push(Vw);//加入队列Q  
                hash(Vw) = true;//设置节点颜色  
            }  
        }  
    }  
    return false; 
}

BFS基础题-连通块问题(也可以用dfs解决)

AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
char a[102][102];
int row, col;
int dir[8][2] =
    {{1, 0}, {1, 1}, {1, -1}, {0, -1}, {0, 1}, {-1, 0}, {-1, 1}, {-1, -1}};
using namespace std;
void dfs(int i, int j)
{
    a[i][j]='*';
    for (int k = 0; k < 8; k++)
    {
        int x = i + dir[k][0];
        int y = j + dir[k][1];
        if (x >= 1 && x <= row && y >= 1 && y <= col && a[x][y] == '@')
            dfs(x, y);
    }
    return;
}
int main()
{
    while ((cin >> row >> col) && (row != 0 || col != 0))
    {
        int c = 0;
        getchar();
        for (int i = 1; i <= row; i++)
            for (int j = 1; j <= col; j++)
                cin >> a[i][j];
        for (int i = 1; i <= row; i++)
            for (int j = 1; j <= col; j++)
                if (a[i][j] == '@')
                {
                    dfs(i, j);
                    c++;
                }
        cout << c << endl;
    }
    return 0;
}

八皇后问题

三维BFS

Dungeon Master

AC代码

#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
 
const int inf = 0x3f3f3f3f;
int l, r, c, ans;
int sx, sy, sz;
char mp[35][35][35];
int vis[35][35][35];
 
struct node {
    int x, y, z, step;
}nw, nxt;
 
int dx[6] = {1, -1, 0, 0, 0, 0}, dy[6] = {0, 0, 1, -1, 0, 0}, 
    dz[6] = {0, 0, 0, 0, 1, -1};
 
void bfs(int z, int x, int y) {
    vis[z][x][y] = 1;
    nw.z = z, nw.x = x, nw.y = y, nw.step = 0;
    queue<node> q;
    q.push(nw);
    while(!q.empty()) {
        nw = q.front(), q.pop();
        if(mp[nw.z][nw.x][nw.y] == 'E') {
            ans = nw.step;
            return;
        }
        for(int i = 0; i < 6; i++) {
            nxt.z = nw.z + dz[i];
            nxt.x = nw.x + dx[i];
            nxt.y = nw.y + dy[i];
            if(nxt.z >= 0 && nxt.z < l && nxt.x >= 0 && nxt.x < r && nxt.y >=0 && nxt.y < c && vis[nxt.z][nxt.x][nxt.y] == 0 && mp[nxt.z][nxt.x][nxt.y] != '#') { 		//到其它层时相对位置不能为'#'
                nxt.step = nw.step + 1;
                vis[nxt.z][nxt.x][nxt.y] = 1;
                q.push(nxt);
            }
        }
    }
}
 
int main() {
    while(~scanf("%d%d%d", &l, &r, &c) && (l + r + c)) {
        for(int i = 0; i < l; i++) {
            for(int j = 0; j < r; j++) {
                scanf("%s", mp[i][j]);			 //三维存图第一维是层数！！！ 
                for(int k = 0; k < c; k++) {	 //第二维是行数，第三维是列数
                    if(mp[i][j][k] == 'S') {
                        sx = j, sy = k, sz =i;
                    }
                }
            }
        }
        memset(vis, 0, sizeof(vis));
        ans = inf;
        bfs(sz, sx, sy);
        if(ans >= inf) {
            printf("Trapped!\n");
        } else {
            printf("Escaped in %d minute(s).\n", ans);
        }
    }
    return 0;
}

DFS

DFS也可用栈实现(比较小众)

思路：每遇到一个元素，就把这个元素所有的邻接元素入栈，当栈不为空时，不断的从栈顶拿出元素进行操作，直到栈为空。

优点:DFS能够做到使用一个状态变量去搜索所有的状态空间，这对空间的消耗来说，是非常节约空间的（通常使用递归实现）。主要应用于回溯的搜索问题中，比如迷宫问题，岛屿问题。

基本模型

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}

模板例题

P1605-迷宫链接

进阶

DFS算法+剪枝+优化总结

图论基础

图的基本概念

1.若一个图的边数接近完全图，则称这样的图为稠密图。

2.若一个图的边数远小于完全图，则称这样的图为稀疏图。

顶点的度

在无向图中，是指依附于该点的边数，在有向图中还分入度和出度。

图的存储方式

邻接矩阵——适合稠密图

邻接表——适合稀疏图

链式前向星(静态邻接表)

通常情况下，邻接表是O(n+e)的复杂程度（n表示节点数，e表示边长），邻接矩阵则是O(n^2)的复杂程度。

邻接矩阵

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

const int maxn=105;
int G[maxn][maxn]={0};    //定义邻接矩阵 
int x,y;    //输入两条边
int n,m;    //供输入n对边 ,m个顶点 (x,y <= m)

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> y;
        G[x][y] = 1;
        G[y][x] = 1;	//有向图去掉就可
    }
    
    for (int i = 0; i < m; i++)		//输出邻接矩阵
    {
        for (int j = 0; j < m; j++)
        {
            cout << G[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

邻接表(vector)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
const int INF = 0x3f3f3f3f;		// 仅存储
vector<int> edge[MAXN];
int main()
{
    int n, m, u, v;
    scanf("%d%d", &n, &m); // n个点，m条边
    while (m--)
    {
        scanf("%d%d", &u, &v);
        // 无向图
        edge[u].push_back(v);
        edge[v].push_back(u);
        // 有向图
        // edge[u].push_back(v);
    }
    return 0;
}

拓扑排序

概念：拓扑排序要解决的问题是给一个图的所有节点排序。

Kahn 算法

算法的核心思想是维持一个入度为 0 的顶点的集合。

从图中取出入度为0的顶点放入集合，并在图中删除与该顶点相关的所有边，如此往复，最后检查图中是否存在任何边，若存在，那么这个图一定有环路，否则返回集合中的顶点，返回的顺序就是拓扑排序的顺序。

对其排序的结果就是：2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12

代码实现

#include <bits/stdc++.h>
using namespace std;
 
bool TopSort(vector<vector<int>> &G, int n, vector<int> &inDegree) {
	int num = 0;				//记录加入拓扑排序的顶点数
	queue<int> q;
	for (int i = 0; i < n; i++)
		if (inDegree[i] == 0)
			q.push(i);		//将所有入度为0的顶点入队
	while (!q.empty()) {
		int u = q.front();		//取队首顶点u
		cout << u << " ";		
		q.pop();
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];		//u的后继节点
			inDegree[v]--;			//v的入度减1
			if (inDegree[v] == 0)		//顶点v的入度减为0则入队
				q.push(v);
		}
		G[u].clear();			//清空顶点u的所有出边
		num++;
	}
	if (num == n)				//加入拓扑序列的顶点数为n，说明拓扑排序成功，否则，失败
		return true;
	else
		return false;
}
 
int main() {
	int n, m;
	cout << "请输入顶点数和边数:";
	cin >> n >> m;
	vector<vector<int>> G(n);
	for (int i = 0; i < m; i++) {
		int x, y;
		cout << "请输入第" << i+1 << "条边的顶点:";
		cin >> x >> y;
		G[x].push_back(y);
	}
	cout << "拓扑排序为:";
	vector<int> inDegree(n);
	for (auto x : G) {
		for (auto y : x)
			inDegree[y]++;
	}
	bool res = TopSort(G, n, inDegree);
 
	return 0;
	
}

DFS算法

vector<int> G[MAXN];  // vector 实现的邻接表
int c[MAXN];          // 标志数组
vector<int> topo;     // 拓扑排序后的节点

bool dfs(int u) {
  c[u] = -1;
  for (int v : G[u]) {
    if (c[v] < 0)
      return false;
    else if (!c[v])
      if (!dfs(v)) return false;
  }
  c[u] = 1;
  topo.push_back(u);
  return true;
}

bool toposort() {
  topo.clear();
  memset(c, 0, sizeof(c));
  for (int u = 0; u < n; u++)
    if (!c[u])
      if (!dfs(u)) return false;
  reverse(topo.begin(), topo.end());
  return true;
}

前缀和&差分

前缀和

即为数列的前n项和。

C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。

注意：一般写前缀和遍历的时候令i=1，因为递推公式是B[i]=A[i]+B[i-1],要保证第一位存在所以不能让i=0。

求前缀和区间值:sum[l,r]=B[r]-B[l-1]

二维前缀和

假定一个矩阵

1 2 4 3
5 1 2 4
6 3 5 9

它的二维前缀和矩阵为

1   3   7   10
6   9   15  22
12  18  29  45

公式：sum[i] [j]=sum[i] [j-1]+sum[i-1] [j]-sum[i-1] [j-1]+a[i] [j]

子矩阵之和

求(x1,y1)到(x2,y2)的子矩阵之和

**sum[x2] [y2] – sum[x2] [y1-1] – sum[x1-1] [y2] + sum[x1-1] [y1-1] **

差分

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

b[i]=a[i]-a[i-1]

单调栈&单调队列

概念：单调栈和单调队列都是满足单调性的数据结构。两者不同之处在于单调队列只能在一端进出，而单调队列是一端入一端出。

单调栈

插入

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

使用样例：栈中自顶向下的元素为 1,3,5,20,30,插入元素10时为了保证单调性需要依次弹出元素1,3,5，最后操作后栈中元素为10,20,30。

单调队列

概念：从队列头部到队列的尾部严格保持递增(或递减)，与普通队列不同的是，单调队列要求可以在队尾进行操作，<queue>无法做到，可以手动模拟或者使用stl的双端队列<deque> 。

例题Sliding Window

分析

要求的是每连续的个数中的最大（最小）值，很明显，当一个数进入所要 “寻找” 最大值的范围中时，若这个数比其前面（先进队）的数要大，显然，前面的数会比这个数先出队且不再可能是最大值。也就是说——当满足以上条件时，可将前面的数 “弹出”，再将该数真正 push 尾。

这就相当于维护了一个递减的队列，符合单调队列的定义，减少了重复的比较次数，不仅如此，由于维护出的队伍是查询范围内的且是递减的，队头必定是该查询区域内的最大值，因此输出时只需输出队头即可。

题解

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define maxn 1000100
using namespace std;
int q[maxn], a[maxn];
int n, k;
void getmin() {
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

void getmax() {
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  getmin();
  printf("\n");
  getmax();
  printf("\n");
  return 0;
}

线段树

概念：线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在***O(logN)***的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

模板代码

建树

void build(int *a, int q, int l, int r)
{
  if (l == r)
  {
    st[q] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(a, q * 2 + 1, l, mid);
  build(a, q * 2 + 2, mid + 1, r);
  st[q] = st[q * 2 + 1] + st[q * 2 + 2];
}

//build(a, 1, 1, n);

单点更新

void update_single(int q, int l, int r, int x, int num)
{		//q为初始节点(一般默认为1)，l，r为线段树范围，x为具体节点，num为更新值
  if (l == x && r == x)
  {
    st[q] += num;
    return;
  }
  int mid = (l + r) / 2;
  if (mid >= x)
    update(q * 2 + 1, l, mid, x, num);
  else
    update(q * 2 + 2, mid + 1, r, x, num);
  st[q] = st[q * 2 + 1] + st[q * 2 + 2];
}

只单点更新的区间求和

int query(int q, int l, int r, int tl, int tr)
{			//tl,tr为求和区间
  if (tl <= l && r <= tr)
    return st[q];
  int mid = (l + r) / 2, sum = 0;
  if (tl <= mid)
    sum += query(q * 2 + 1, l, mid, tl, tr);
  if (tr > mid)
    sum += query(q * 2 + 2, mid + 1, r, tl, tr);
  return sum;
}

区间更新

//区间[tl,tr]的值全部加num
void update_region(int q, int l, int r, int tl, int tr, int num)
{
    if (l >= tl && r <= tr)
    {
        st[q] += num * (r - l + 1);
        lazy[q] += num;
        return;
    }
    if (lazy[q])
        pushdown(q, l, r);
    int mid = (l + r) / 2;
    if (tl <= mid)
        update_region(q * 2, l, mid, tl, tr, num);
    if (tr > mid)
        update_region(q * 2 + 1, mid + 1, r, tl, tr, num);
    st[q] = st[q * 2] + st[q * 2 + 1];
}

延迟标记

//将下标k的节点lazy向下传递
void pushdown(int k, int l, int r)
{
    int mid = (l + r) / 2;
    lazy[2 * k] += lazy[k];
    st[2 * k] += ((mid - l) + 1) * lazy[k];
    lazy[2 * k + 1] += lazy[k];
    st[2 * k + 1] += (r - mid) * lazy[k];
    lazy[k] = 0;
}

区间更新的区间求和

int query(int q, int l, int r, int tl, int tr)
{
    if(l>=tl&&r<=tr)
        return st[q];
    if(lazy[q])
        pushdown(q, l, r);//下放标记
    int sum = 0;
    int mid = (l + r) / 2;
    if (tl <= mid)
        sum += query(q * 2, l, mid, tl, tr);
    if (tr > mid)
        sum += query(q * 2 + 1, mid + 1, r, tl, tr);
    return sum;
}

经典例题敌兵布阵+思路+题解

字典树

概念：字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。

模板代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7;
int trie[maxn][26];
string s;
int ind=1;
int flag[maxn];
void insert(string s)//插入操作
{
	int t = 0;
	for (int i = 0; s[i]; i++)
	{
		int x = s[i] - 'a';			//x是t节点的第x个孩子
		if (trie[t][x] == 0)		//如果没有就添加节点
			trie[t][x] = ind++;		//ind为节点编号
		t = trie[t][x];
		ans[t]++;
	}
    // flag[t]=1;		//用flag标记字符串的最后一个节点位置，查询的时候可以防止出错，如树中有cart，不添加标记如果查询car就会出现错误
}


bool query(string s) //查询是否存在目标字符串
{
	int t = 0;
	for (int i = 0; s[i]; i++)
	{
		int x = s[i] - 'a';
		if (trie[t][x] == 0)		//中途没有查询到就返回false
            return 0;
		t = trie[t][x];				//前往下一个节点
	}
    return flag[t];		//插入时的标记在此发挥作用
}

最短路问题

四种算法

Floyd算法
Dijkstra算法
Bellman-Ford算法
SPFA算法

Floyd算法

用来求任意两个节点之间的最短路

缺点：复杂度较高为O(n^3)，一般只适合三位数的数据大小。

优点：适用于任何图，代码简单，边权可以为负，但是不能有负环(必须存在最短路)。

核心代码

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    }
  }
}

原本f数组是有三维的，但是第一维可以省略不会产生影响，这里不进行深究。

Dijkstra算法

用来求单源最短路的算法，图的边权不能为负，时间复杂度为O(N^2)，堆优化为O(mlogn)。

模板代码

#include <iostream>
#include <cmath>
#include <set>
#include <string.h>
#include<queue>
#include<map>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn = 1e3 + 10;
int n,m;//n个顶点，m条边。
bool visited[maxn];//判断是否确定到源点的最终最短距离。
int graph[maxn][maxn];
int dis[maxn];//顶点到源点的最短距离。
int start,goal;

void init()
{
    memset(visited, false, sizeof(visited));
    for (int i = 1; i <= n; i++)
    {
        dis[i] = graph[start][i]; //从start点到i点的距离
    }
}

void dijkstra()
{
	int minn;//记录每趟最短路径中最小的路径值。
    int pos = 0; //记录得到的minn所对应的下标。 
    init();
    visited[start] = true;	//因为pos为0，所以这里标不标记都一样
    for (int i = 1; i <= n; i++)
    {
        //将n个顶点依次加入判断。
        minn = inf;
        for (int j = 1; j <= n; j++)
        {
            if (!visited[j] && dis[j] < minn)
            {
                minn = dis[j];
                pos = j;
            }
        }
        //经过这趟for循环后找到的就是我们想要的点，可以确定这点到源点的最终最短距离了。
        visited[pos] = true; //将此点并入已知集合。
        //接下来就是更新dis数组了，也就是当前最短距离，这都是针对还没有并入已知集合的点。
        for (int j = 1; j <= n; j++)
        {
            if (!visited[j] && dis[j] > dis[pos] + graph[pos][j])
                dis[j] = dis[pos] + graph[pos][j];
        }
    }
    //退出循环后，所有的点都已并入已知集合中，得到的dis数组也就是最终最短距离了。
    if (dis[goal] == inf)
        cout << -1 << endl;
        else
        cout << dis[goal] << endl; //输出目标点到源点的最短路径长度。
}

int main()
{
    while (cin >> n >> m && n && m)
    {
        memset(graph, inf, sizeof(graph));
    int u, v, w;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        if (w < graph[u][v])// 判断重边，取最小值
            graph[u][v] = w;
        if (w < graph[v][u])
            graph[v][u] = w;
    }
        start = 1, goal = n;
        dijkstra();
    }
    
    
    return 0;
}

Bellman-Ford算法

能找到某个结点出发到所有结点的最短路，或者报告某些最短路不存在

可以在负权图中使用，可以用来寻找是否有负环

核心代码

for(int k = 1 ; k <= n - 1 ; k ++) //n为点
{
    for(int i = 1 ; i < m ; i ++) //m为边，枚举每一条边
    {
        if(dis[v[i]] > dis[u[i]] + w[i])//尝试对每一条边进行松弛
            dis[v[i]] = dis[u[i]] + w[i] ;//dis数组记录源点到其余各个顶点的最短路径  
    }
}

模板例题+代码

题目

第1行输入n,m，其中n为顶点，m为边的关系

第2-m+1行给出两个点和之间的距离

求1号点到每个点的最短路

题解

#include<bits/stdc++.h>
const int INF = 0x3f3f3f;
using namespace std;
int main()
{
    int u[100] , v[100] , w[100] , dis[100] , n , m ;
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i ++)
    {
      cin >> u[i] >> v[i] >> w[i];
    }
    for(int i = 1 ; i  <= n ; i ++)
    dis[i] = INF;
    dis[1] = 0;
    for(int k = 1 ; k <= n - 1 ; k ++)
        for(int i = 1 ; i <= m ; i ++)
            if(dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];
            for(int i = 1 ; i <= n ; i ++)
              cout << dis[i] << " ";
    return 0 ;
}

SPFA算法

是Bellman-Ford的队列优化

优化原理：Bellman-Ford算法会进行很多次无用的松弛操作，但是易知，只有上次被松弛过得节点所连接的边才会引起下一次的松弛，所以用队列维护可能引起松弛操作的节点就可以省略操作不必要的边。

思想：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

模板代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
struct edge
{
  int to, next, w;
} e[maxn];

int n, m, cnt, p[maxn], Dis[maxn];
int In[maxn];
bool visited[maxn];

void add(const int x, const int y, const int z)
{
  e[++cnt].to = y;
  e[cnt].next = p[x];
  e[cnt].w = z;
  p[x] = cnt;
  return;
}
bool Spfa(const int S)
{
  int i, t, temp;
  queue<int> Q;
  memset(visited, 0, sizeof(visited));
  memset(Dis, 0x3f, sizeof(Dis));
  memset(In, 0, sizeof(In));
  Q.push(S);
  visited[S] = true;
  Dis[S] = 0;
  while (!Q.empty())
  {
    t = Q.front();
    Q.pop();
    visited[t] = false;
    for (i = p[t]; i; i = e[i].next)
    {
      temp = e[i].to;
      if (Dis[temp] > Dis[t] + e[i].w)
      {
        Dis[temp] = Dis[t] + e[i].w;
        if (!visited[temp])
        {
          Q.push(temp);
          visited[temp] = true;
          if (++In[temp] > n)
            return false;
        }
      }
    }
    }
    return true;
}
int main ( )
{
  int s, t;
  cin >> n >> m >> s >> t;
  for (int i = 1; i <= m; ++i)
  {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
  }
    if (!Spfa(s))
      cout << "fail<<endl";
    else
      cout << Dis[t] << endl;
    return 0;
}

最小生成树

Kruskal算法

知识点：对边贪心，并查集

思想：从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了n-1条边，即形成了一棵树。

模板代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
struct node
{
    int u, v, w;
} edge[N];

int n, m, num, ans;
int pre[N];

bool cmp(node a, node b)//按照边的距离排序
{
    return a.w < b.w;
}

void init()
{
    num = 0, ans = 0;
    for (int i = 1; i <= n; i++)
        pre[i] = i;//初始化，父节点为自己
}

int find(int x)
{
    if (x != pre[x])	//路径压缩
        return pre[x] = find(pre[x]);
    return x;
}

void merge(int x,int y)//合并函数
{
    int a = find(x);
    int b = find(y);
    if (a != b)
        pre[a] = b;
}

void krusal()
{
    sort(edge, edge + m, cmp);//排序
    for (int i = 0; i < m; i++)
    {
        int x = edge[i].u;
        int y = edge[i].v;
        if (find(x) != find(y))	//两个点的父节点不是同一个就直接合并，如果是同一个的话就直接丢弃这个边，继续下一个边
        {
            merge(x, y);
            num++;
            ans += edge[i].w;
            if (num == n - 1)//根据性质，最小生成树的边是结点数-1,，如果边数够了就表明满足条件
            {
                cout << ans << endl;
                return;
            }
        }
    }//循环结束边数都不够说明无法构成最小生成树
    cout << "orz" << endl;
    return;
}

int main()
{
    cin >> n >> m;
    init();
    for (int i = 0; i < m; i++)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    krusal();
    return 0;
}

Prim算法

知识点：对点贪心

思想：每次选择距离当前节点最近的一个节点，并用这条边更新其它节点的距离。

模板代码

#include<iostream>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f;
const int maxx=500+10;
int e[maxx][maxx], dis[maxx];
bool book[maxx];
int n,m;
void init()//初始化，自己到自己初始化为0，到其他点为inf
{
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = inf;
}

int prim(int e[][maxx], int n)
{
    int ans = 0;
    memset(book, false, sizeof(book));	
    for (int i = 0; i < n; i++)
        dis[i] = e[0][i];
    for (int i = 0; i < n; i++)
    {
        int minn = inf, u = -1;
        for (int j = 0; j < n; j++)
        {
            if (!book[j] && dis[j] < minn)	//未被标记且距离更小
            {
                minn = dis[j];
                u = j;
            }
        }
        if (u == -1)
            return 0;
        ans += minn;
        book[u] = true;//访问后进行标记
        for (int v = 0; v < n; v++)
            if (!book[v] && e[u][v] != inf)
                dis[v] = min(dis[v], e[u][v]);
    }
    return ans;
}

int main()
{
    
    cin >> m >> n;
    init();
    for (int i = 0; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (e[a][b] > c)
            e[a][b] = e[b][a] = c;//无向图
    }
    int cnt = prim(e, m);
    if (cnt)
        cout << cnt << endl;
    else
        cout << "orz" << endl;//没有最小生成树
   
    return 0;
}

Prim参考代码

/*prim算法求最小生成树
邻接矩阵法构造图 
算法思想：首先从顶点0出发，然后找到下一个距离顶点0最近的顶点i，也进入集合U
此算法是从进入了集合U的顶点中找到个各顶点与其他未进入集合U的顶点之间的一条最短的边去连接的 
*/
# include<stdio.h>
#include<iostream>
using namespace std;
int inf=0x3f3f3f3f;
int s[100][100];//存储图 
 
bool selected[100];//判断顶点是否被选中 
int minCost[100];//保存已选顶点中到该顶点的最小的路径 
int parent[100];//保存父节点 
 
void prim(int n,int k){
	//第一步，第K个顶点被选中 
	selected[k]=true;
	minCost[k]=-1;
	//开始更新minCost数组和parent数组 
	for(int i=0;i<n;i++){
		if(s[k][i]!=inf&&s[k][i]<minCost[i]) {
			minCost[i]=s[k][i];
			parent[i]=k;
		}
	}
	//在minCost数组中找到最小的那个值，然后选择对应的点
	int min=inf;int f=-1;
	 for(int j=0;j<n;j++) {
	 	if(minCost[j]!=-1&&minCost[j]<min){
	 		min=minCost[j];
	 		f=j;
		 }
	 }
	 if(f==-1) return;//全部都已经被选了 
	 prim(n,f);
}
int main(void){
	//输入图的顶点个数
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>s[i][j];
			if(s[i][j]==0)
			s[i][j]=inf;
		}
		selected[i]=false; 
		minCost[i]=inf;
		parent[i]=-1;
	} 
	// cout<<"图输入完成！"; 
	 prim(n,0);
	 int sum=0;
	 for(int i=1;i<n;i++)
	 {
	 	sum=sum+s[i][parent[i]];
	 }
	 cout<<sum<<endl;
	 
}
/*6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0*/

倍增求LCA

朴素算法

让节点一层一层在树上跳，预处理时需要dfs整棵树，时间复杂度为O(n)，单次查询O(logN),如果是单次查询的话可以考虑朴素算法，应该比倍增快。

BFS求节点深度

#include <bits/stdc++.h>
#define MXN 50007
using namespace std;
vector<int> v[MXN];
vector<int> w[MXN];
int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;
// 接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
  // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
  // 2^(i-1) 的祖先节点。
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // 遍历子节点来进行 dfs。
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}

倍增算法

时间复杂度为O(nlogn)

基础模板代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n, m, s;
int lg[maxn];
int dep[maxn];
int fa[maxn][25];
vector<int> G[maxn];

void getdep(int u)   
{       //求祖先数组
    for (int i = 1; i <= lg[dep[u]]; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = 0; i < G[u].size(); i++)
    {
        //遍历u所有边
        int e = G[u][i];
        if (e != fa[u][0])
        {
            fa[e][0] = u;
            dep[e] = dep[u] + 1;
            getdep(e);
        }
    }
}

int lca(int u,int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    while (dep[u] != dep[v])
        u = fa[u][lg[dep[u] - dep[v]]];
    if (u == v)
        return u;
    for (int j = lg[dep[u]]; j >= 0; j--)
    {
        if (fa[u][j] != fa[v][j])
        {
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        lg[i] = lg[i - 1];
        if (i == (1 << lg[i - 1]))
            lg[i]++;
    }
    for (int i = 1; i <= n; i++)
        lg[i]--;
    for (int i = 1; i <= n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);//无向图 
        G[v].push_back(u);
    }
    //无向图可以用任意一个节点当做根节点
    //选择初始化1的深度为1，以1为根节点建树
    dep[1] = 1;
    getdep(1);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
        return 0;
}

例题HDU 2586 How far away?

思路:只需要在LCA中执行上跳的操作时，加上对应的长度，就可以求得需要距离。

题解

#include <bits/stdc++.h>
using namespace std;
const int maxn=4e4+5;
int n,m;
int lg[maxn];
int dep[maxn];  //深度
int f[maxn][25];
int value[maxn][25];
vector<int> a[maxn],w[maxn];
void init()
{
  memset(dep, 0, sizeof dep);
  memset(f, 0, sizeof f);
  memset(value, 0, sizeof value);
  for (int i = 0; i < maxn; i++)
  {
    a[i].clear();
    w[i].clear();
  }
}
void getdep(int u)
{
  //完善祖先数组和到这个祖先长度的数组
  for (int i = 1; i <= lg[dep[u]]; i++)
  {
    f[u][i] = f[f[u][i - 1]][i - 1];
    value[u][i] = value[u][i - 1] + value[f[u][i - 1]][i - 1];
  }
  //遍历所有u的边
  for (int i = 0; i < a[u].size(); i++)
  {
    int e = a[u][i];
    //不遍历父亲的边
    if (e != f[u][0])
    {
      //无向图不能在录入边时记录父亲，所以在这记录
      f[e][0] = u;
      //记录的点是到父亲的长度
      value[e][0] = w[u][i];
      dep[e] = dep[u] + 1;
      getdep(e);
    }
  }
}
int lca(int u, int v)
{
  int sum = 0;
  if (dep[u] < dep[v])
  {
    swap(u, v);
  }
  while (dep[u] != dep[v])
  {
    //u节点上跳的同时，更新总长度
    sum += value[u][lg[dep[u] - dep[v]]];
    u = f[u][lg[dep[u] - dep[v]]];
  }
  //如果v是u祖先；直接返回现在的总长度；
  if (u == v)
    return sum;
  for (int j = lg[dep[u]]; j >= 0; j--)
  {
    if (f[u][j] != f[v][j])
    {
      //节点上跳的同时，更新总长度
      sum += value[u][j];
      sum += value[v][j];
      u = f[u][j];
      v = f[v][j];
    }
  }
  //u和v离LCA还差一步，加上这两个距离。
  sum += value[u][0];
  sum += value[v][0];
  return sum;
}
int main()
{
  //lg[i]中是i内最大的2的幂次数，如lg【5】中值为2，代表2^2是5内最大2的幂次数。
  for (int i = 1; i < maxn; i++)
  {
    lg[i] = lg[i - 1];
    if (i == (1 << lg[i - 1]))
      lg[i]++;
  }
  for (int i = 1; i < maxn; i++)
  {
    lg[i]--;
  }
  //t组样例
  int t;
  cin >> t;
  while (t--)
  {
    //初始化
    init();
    //n个节点，m次询问
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
      int u, v, k;
      cin >> u >> v >> k;
      //无向图建边两次
      //都加上边权
      a[u].push_back(v);
      w[u].push_back(k);
      a[v].push_back(u);
      w[v].push_back(k);
    }
    //无向图任意节点都可以为根节点，这里选了1做根节点
    dep[1] = 1;
    getdep(1);
    for (int i = 0; i < m; i++)
    {
      int x, y;
      cin >> x >> y;
      cout << lca(x, y) << endl;
    }
  }
}

LCA还可以用tarjan算法求,这里不拓展总结。

Tarjan算法

Tarjan求强连通分量

在 Tarjan 算法中为每个结点u维护了以下几个变量：

dfn[u]:深度优先搜索遍历时结点u被搜索的次序
low[u]:u在图中可以到达最小的dfn

性质:

每个结点的dfn都是不一样的
每次在dfn中找到新结点时，该结点的dfn和low赋相同值
一个结点的子树内结点的 dfn 都大于该结点的 dfn从根开始的一条路径上的dfn 严格递增，low 严格非降。

伪代码

tarjan(u){
    DFN[u]=Low[u]=++Index	//为节点u设定次序编号和Low初值
    Stack.push(u)			//将节点u压入栈中
 	
    foreach(u,v) in E		//枚举每一条边
	if(v is not visted)	//如果节点v未被访问过
	    tarjan(v)		//继续向下找
	    Low[u]=min(Low[u],Low[v])
	else if(v in S)		//如果节点v还在栈内
		Low[u]=min(Low[u],DFN[v])
    if(DFN[u]==Low[u])	//如果节点u是强连通分量的根
	repeat
		v=S.pop//将v退栈，为该强连通分量中一个顶点
		print v
	until(u==v)
}

可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。N为点数，M为边数。

模板代码（手动模拟栈）

#include<iostream>
#include<vector>
using namespace std;
const int MAX = 10005;
#define ll long long

vector<ll> g[MAX];
ll color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX];
//deep:节点编号 top：栈顶  sum：强连通分量数目
ll deep, top, sum, res = 0;

void tanjan(ll v)
{
  dfn[v] = ++deep;
	low[v] = deep;   //(1)初始化dfn数组，同时将low设置为相同值
	vis[v] = 1;
	stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组

  for (unsigned i = 0; i < g[v].size(); i++)
  { //(3)遍历所有可能到达的点
    ll id = g[v][i];
		if (!dfn[id]) {//如果这个点从没访问过，则先访问它更新low[v]的值
			tanjan(id);
      low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以
    }
		else {
      if (vis[id])
      { //不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
        low[v] = min(low[v], low[id]);
      }
    }
  }

  if (low[v] == dfn[v])
  { //(4)自己和子节点形成了强连通分量，或者只有自己孤身一人
    color[v] = ++sum;
		vis[v] = 0;
    while (stack[top] != v)
    {                         //将从v开始所有的点取出
      color[stack[top]] = sum;//给予同一颜色
			vis[stack[top--]] = 0;//出栈要顺便修改vis
    }
    top--;
  }
}

Tarjan缩点

仍使用了求强连通分量的方法，适用于具有传递性的题面，如路径权值之类。

原理：一个强连通分量中的每两个点都是强连通的，可以将一个强连通分量缩小成一个点，点权如何计算根据题意而定。

部分代码

vector<int> g[MAX];
int color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX], num[MAX];
int ind[MAX], outd[MAX];//每个点的出度入度
//deep:节点编号 top：栈顶  sum：强连通分量数目
int deep, top, sum, res = 0;

void tanjan(int v) {
	dfn[v] = ++deep;
	low[v] = deep;   //(1)初始化dfn数组，同时将low设置为相同值
	vis[v] = 1;
	stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组

	for (unsigned i = 0; i < g[v].size(); i++) {//(3)遍历所有可能到达的点
		int id = g[v][i];
		if (!dfn[id]) {//如果这个点从没访问过，则先放问它，再用它更新low[v]的值
			tanjan(id);
			low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以
		}
		else {
			if (vis[id]) {//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
				low[v] = min(low[v], low[id]);
			}
		}
	}

	if (low[v] == dfn[v]) {//(4)自己和子节点形成了强连通分量，或者只有自己孤身一人
		color[v] = ++sum; num[sum]++; //num统计该颜色有多少点
		vis[v] = 0;
		while (stack[top] != v) {//将从v开始所有的点取出
			color[stack[top]] = sum;//给予同一颜色
			vis[stack[top--]] = 0;//出栈要顺便修改vis
			num[sum]++;
		}
		top--;
	}
}
int main(){
	for (int i = 1; i <= N; i++) {
		for (unsigned k = 0; k < g[i].size(); k++) {
			int v = g[i][k];
			if (color[v] != color[i]) {//二者分属于不同的联通集
				outd[color[i]] += 1; //以颜色作为点，更新相应点的出度
			}
		}
	}
}

Tarjan割点、割桥

能力不足，日后再补

欧拉图

定义

在图上用一种走法，能够经过所有的边一次，且每条边只经过一次的路径，即为欧拉路径
通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路
通过图中所有边恰好一次且行遍所有顶点的回路(回到起点)称为欧拉回路(所有点的入度等于出度)
具有欧拉回路的无向图或有向图称为欧拉图
具有欧拉通路但不具有欧拉回路的无向图或有向图称为半欧拉图

性质

欧拉图中所有顶点的度数都是偶数

Hierholzer 算法

思想：

判断奇点数，为0则随意指定起点，若为2则其一为起点
从一个起点出发，进行DFS，每次从一个顶点到另一个顶点时，都要删除两顶点之间的边，如果没有可移动的边，则将该顶点加入栈中
输出栈中顶点，该顺序即是从起点出发的欧拉路径

例题骑马修栅栏

题解

#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;

struct edge {
  int to;
  bool exists;
  int revref;
  bool operator<(const edge &b) const
  {
    return to < b.to;
  }
};

vector<edge> beg[505];
int cnt[505];

const int dn = 500;
stack<int> ans;

void Hierholzer(int x)
{
  for (int &i = cnt[x]; i < (int)beg[x].size();)
  {
    if (beg[x][i].exists)
    {
      edge e = beg[x][i];
      beg[x][i].exists = 0;
      beg[e.to][e.revref].exists = 0;
      ++i;
      Hierholzer(e.to);
    } else {
      ++i;
    }
  }
  ans.push(x);
}

int deg[505];
int reftop[505];

int main()
{
  for (int i = 1; i <= dn; ++i)
  {
    beg[i].reserve(1050);
  }

  int m;
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) 
  {
    int a, b;
    scanf("%d%d", &a, &b);
    beg[a].push_back((edge){b, 1, 0});
    beg[b].push_back((edge){a, 1, 0});
    ++deg[a];
    ++deg[b];
  }

  for (int i = 1; i <= dn; ++i)
  {
    if (!beg[i].empty())
    {
      sort(beg[i].begin(), beg[i].end());  // 为了要按字典序贪心，必须排序
    }
  }

  for (int i = 1; i <= dn; ++i)
  {
    for (int j = 0; j < (int)beg[i].size(); ++j)
    {
      beg[i][j].revref = reftop[beg[i][j].to]++;
    }
  }

  int bv = 0;
  for (int i = 1; i <= dn; ++;i)
  {
    if (!deg[bv] && deg[i])
    {
      bv = i;
    }
    else if (!(deg[bv] & 1) && (deg[i] & 1))
    {
      bv = i;
    }
  }

  Hierholzer(bv);

  while (!ans.empty())
  {
    printf("%d\n", ans.top());
    ans.pop();
  }
  return 0;
}

题解2

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int map[10001][10001];//记录两个点之间的路径个数 
int du[10001];//辅助记录奇点 
int lu[10001];//记录路径 
int n,x,y,js=0;
int maxn=0;
void find(int i)//
{
	int j;
	for(j=1;j<=maxn;++j)//而且这里不是n而是maxn因为n不是点的个数而是下面有多少行 
	{
		if(map[i][j]>=1)
		{
			map[i][j]--;//删去边一次吗避免重复 
			map[j][i]--;//z这里和一笔画不一样这里是累减而一笔画直接变成0 
			find(j);
		}
	}
	lu[++js]=i;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&x,&y);
		map[x][y]++;
		map[y][x]++;
		du[x]++;
		du[y]++;//记录出现的次数 
		maxn=max(maxn,max(x,y));
	}
	int start=1;//默认奇点是1 
	for(int i=1;i<=maxn;++i)
	{
		if(du[i]%2)//找到奇点 
		{
			start=i;//记录奇点
			break;//然后结束循环 
		}
	}
	find(start);//从奇点开始找 
	for(int i=js;i>=1;i--)
	{
		printf("%d\n",lu[i]);//挨个输出路径并且换行 
	}
	return 0;
}

注意，不能在递归的同时进行输出，输出的路径是错误的

void dfs(int x)//错误输出
{
	for(int i=1;i<=n;i++)if(a[i][x])
	{
		printf("%d\n",x);
		a[i][x]--;a[x][i]--;
		dfs(i);
	}
}
int main()
{
	//……
    printf("%d",&s);//s是起点
    dfs(s);
}

void dfs(int x)//正确输出
{
	for(int i=1;i<=n;i++)if(a[i][x])
	{
		a[i][x]--;a[x][i]--;
		dfs(i);
	}
	p[size++]=x;
}
int main()
{
	//……
	dfs(s);
	for(int i=size-1;i>=0;i--)printf("%d\n",p[i]);
	return 0;
}

二分图

定义：节点由两个集合组成，且两个集合内部没有边的图。

性质

如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。
二分图不存在长度为奇数的环

二分图判定

AcWing-860染色法判定二分图

//dfs染色法
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx; //邻接表的存储
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c)
{
    color[u] = c; //当前这个点u的颜色是 c

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j]) //u 的邻接点 j 未被染色
        {
            dfs(j, 3 - c); // u的颜色如果是1，j就是3-1=2；u的颜色如果是2，j就是3-2=1
        }
        else if (color[j] == c)
            return false; //两邻接点染相同颜色
    }
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));

    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a); // 无向图建两条相反方向的边
    }

    bool flag = true;
    for (int i = 1; i <= n; i++) //遍历图的所有点
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }

    if (flag)
        cout << "Yes";
    else
        cout << "No";
}

//bfs染色法
//不建议使用
//太玄幻了根本看不懂还是把代码粘贴进来吧
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII; //first存点编号，second存颜色
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx; //邻接表的存储
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool bfs(int u)
{
    queue<PII> q;
    q.push({u, 1});
    color[u] = 1; //当前这个点u的颜色是 c

    while (q.size()) //队列不空
    {
        PII t = q.front();
        q.pop();

        int ver = t.first, c = t.second;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];

            if (!color[j]) //未被染色
            {
                color[j] = 3 - c;
                q.push({j, 3 - c});
            }
            else if (color[j] == c)
                return false; //两邻接点染相同颜色
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));

    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a); // 无向图建两条相反方向的边
    }

    bool flag = true;
    for (int i = 1; i <= n; i++) //遍历图的所有点
        if (!color[i])
        {
            if (!bfs(i))
            {
                flag = false;
                break;
            }
        }

    if (flag)
        cout << "Yes";
    else
        cout << "No";
}

增广路算法

匹配：一个边集中的任意两条边都不依附于同一个顶点，则称这个边集是一个匹配。

最大匹配：在匹配的基础上让边最大。

通俗理解可以看成左边一个集合是所有男孩，右边一个集合是所有女孩，我们需要求最多可以凑成几对情侣。

增广路：增广路径是指，由一个未匹配的顶点开始，经过若干个匹配顶点，最后到达对面集合的一个未匹配顶点的路径，即这条路径将两个不同集合的两个未匹配顶点通过一系列匹配顶点相连。

增广路算法例题

#include <bits/stdc++.h>
using namespace std;
const int maxn = 600 + 5;
bool line[maxn][maxn];
//line[x][y]=true表示x号女生喜欢y男生(边）
int boy[maxn];
//存储y号男生匹配边另一端的匹配点女生，如果是未覆盖点则为0
bool falg[maxn];
//存储y号男生是否在这条交替路上被使用过,男生是否被别人喜欢
int k, n, m;
bool dfs(int x)
{

    for (int j = 1; j <= m; j++)
    {
        if (line[x][j] && !falg[j])
        {
            falg[j] = true;
            if (!boy[j] || dfs(boy[j]))
            {
                //满足上面的判断语句说明找到了增广路
                //即终点是未覆盖点的交替路
                boy[j] = x;
                return true;
            }
        }
        //该条路不是增广路
    }

    return false;
}
int main()
{
    while (cin >> k)
    {
        if (!k)
            break;
        cin >> n >> m;
        int x, y;
        int ans = 0;
        memset(line, false, sizeof(line));//初始化
        memset(boy, 0, sizeof(boy));
        while (k--)
        {
            cin >> x >> y;
            line[x][y] = true;
        }
        for (int i = 1; i <= n; i++)
        {
            memset(falg, false, sizeof(falg));//每次循环都要初始化flag
            if (dfs(i))
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

C++高精度

高精度四则运算

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

struct bign //大整数数组
{
    int len; //位数
    int num[1000];
};
//大整数转换
bign change(char a[])
{
    bign c;
    c.len = strlen(a);
    for (int i = 0; i < c.len; i++)
    {
        c.num[i] = a[c.len - i - 1] - '0';
    }
    return c;
}
//大整数比较
int compare(bign a, bign b)
{                      //大于返回1，小于返回-1，相等返回0
    if (a.len > b.len) //位数多的数比位数少的数大
        return 1;
    if (a.len < b.len)
        return -1;
    for (int i = a.len - 1; i >= 0; i--)
    { //位数相同，高位到低位逐位比较
        if (a.num[i] > b.num[i])
            return 1;
        else if (a.num[i] < b.num[i])
            return -1;
    }
    return 0; //执行到最后肯定相等
}

bign add_bign(bign a, bign b)
{
    bign c;
    for (int i = 0; i < a.len || i < b.len; i++)
    {                                  //以位数长的结束条件
        c.num[c.len] += a.num[i] + b.num[i]; //对应位置相加再加上进位
        if (c.num[c.len] >= 10)
        {                     //大于等于10需要进位
            c.num[c.len + 1]++; //进位加到前一位上
            c.num[c.len] -= 10; //更新原位置的值
        }
        c.len++;
    }
    if (c.num[c.len]) //最高位不为零长度加一
        c.len++;
    return c;
}

bign sub_bign(bign a, bign b)
{
    bign c;
    for (int i = 0; i < a.len || i < b.len; i++)
    { //以位数长的结束条件
        if (a.num[i] < b.num[i])
        { //如果同位的被减数比减数小需要借位
            a.num[i] += 10;
            a.num[i + 1]--;
        }
        c.num[c.len++] = a.num[i] - b.num[i];
    }
    while (c.len > 1 && !c.num[c.len - 1]) //消除前缀零
        c.len--;
    return c;
}

bign mutli_bign(bign a, bign b)
{
    bign c;
    for (int i = 0; i < a.len; i++) //大数a逐位乘大数b
        for (int j = 0; j < b.len; j++)
        {
            c.num[i + j] += a.num[i] * b.num[j]; //a的第i位乘b的第j位加上进位
            if (c.num[i + j] >= 10)
            { //大于等于十进位
                c.num[i + j + 1] += c.num[i + j] / 10;
                c.num[i + j] %= 10;
            }
        }
    c.len = a.len + b.len;                   //两个数乘积的位数不超过两个数位数之和
    while (c.len > 1 && c.num[c.len - 1] == 0) //取出前导零
        c.len--;
    return c;
}

bign div_bign(bign a, bign b)
{
    bign c;
    c.len = a.len - b.len + 1; //求商的位置
    for (int i = c.len - 1; i >= 0; i--)
    {
        bign temp;
        for (int j = 0; j < b.len; j++) //b补零存在临时数组
            temp.num[j + i] = b.num[j];
        temp.len = b.len + i;
        while (compare(a, temp) >= 0)
        {                      //a的高b.len位比temp小重新补零
            c.num[i]++;          //累计减的次数
            sub_bign(a, temp); //大整数减法
        }
    }
    while (c.len > 1 && !c.num[c.len - 1]) //消去前导零
        c.len--;
    return c;
}

char a[1000], b[1000];

int main()
{
    /*cin >> a >> b;
    bign a1 = change(a);
    bign b1 = change(b);
    bign c = add_bign(a1, b1);
    for (int i = c.len - 1; i >= 0; --i)
        cout << c.num[i];*/
    return 0;
}

JAVA高精度

高精度加法

//package com.company;交题的时候不需要这一行

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

public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        BigInteger a=in.nextBigInteger();
        BigInteger b=in.nextBigInteger();
        System.out.println(a.add(b));
    }//减法换成subtract，乘法换成multiply，除法换成divide
}

求大整数的阶乘

//package com.company;

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

public class Mai n{

    public static void main(String[] args){
        // write your code here
        Scanner in=new Scanner(System.in);
        BigInteger ans=BigInteger.ONE;
        int n=in.nextInt();
        for(int i = 1; i <= n; i++){
            ans=ans.multiply(BigInteger.valueOf(i));
        }
        System.out.println(ans);
    }
}

高精度整数BigInteger

String temp1 = "-1000000000000000000000000000000000000";
BigInteger bg1 = new BigInteger(temp1);          //注意初始化的方式,使用字符串来初始化
System.out.println(bg1.abs());                   //绝对值方法    object.abs()

String temp2 = "100000000000000000000000000";
BigInteger bg2 = new BigInteger(temp2);
System.out.println(bg1.add(bg2));                //加法    object.add(BigInteger b)

System.out.println(bg1.subtract(bg2));           //减法   返回为 bg1 - bg2  (this - param)

System.out.println(bg1.multiply(bg2));           //乘法  返回 bg1 * bg2

System.out.println(bg1.divide(bg2));             //除法  返回bg1 / bg2

System.out.println(bg1.mod(bg2));                //取模运算 返回的是   bg1%bg2 (this mod param)

System.out.println(bg1.gcd(bg2));                //直接封装好了 求解bg1,bg2 的最大公约数

int temp5 = 5;
System.out.println(bg2.pow(temp5));              //乘方运算  注意这个方法的参数是基本类型int

System.out.println(bg2.compareTo(bg1));          // 比较方法 结果为1  bg2大
System.out.println(bg1.compareTo(bg2));          // 结果为-1  bg2大
                                                 //这个地方注意比较的方法，还有一个方法是equal()
String temp3 = "1000";
String temp4 = "001000";
BigInteger bg3  = new BigInteger(temp3);
BigInteger bg4 = new BigInteger(temp4);
System.out.println(bg3.compareTo(bg4));          //结果为0 表示相等
System.out.println(bg3.equals(bg4));             //返回结果为true     这样看是没有区别，但是更推荐比较的时候使用compareTo()方法，
                                                 //在BigDecimal更直观，例如0.1 与0.10 ，equal返回false 而compareTo则是正确的结果。

高精度浮点数

String temp1 = "1.2222222222222222222222222";
BigDecimal bd1 = new BigDecimal(temp1);
String temp2 = "2.333333333333333333333333";
BigDecimal bd2 = new BigDecimal(temp2);
System.out.println(bd1.add(bd2)); // 加法  输出   3.5555555555555555555555552
System.out.println(bd1.add(bd2).doubleValue());         // 输出    3.5555555555555554 这里用了一个方法将结果转化为double类型了

System.out.println(bd2.subtract(bd1)); //减法    输出 1.1111111111111111111111108
System.out.println(bd2.subtract(bd1).doubleValue());    //输出   1.1111111111111112

System.out.println(bd2.multiply(bd1)); 			//乘法 输出    2.8518518518518518518518513925925925925925925925926
System.out.println(bd2.multiply(bd1).doubleValue());    //乘法    2.8518518518518516

System.out.println(bd2.divide(bd1, 5, RoundingMode.HALF_UP));             //除法应该注意很有可能会有除不尽的情况，这时候会有异常抛出，所以要传入控制参数
System.out.println(bd2.divide(bd1, 5, RoundingMode.HALF_UP).doubleValue());     //输出都是  1.90909

System.out.println(bd1.compareTo(bd2));          //比较方法
BigDecimal bd3 = new BigDecimal("1.20");
BigDecimal bd4 = new BigDecimal("1.2");
System.out.println(bd3.compareTo(bd4));          //返回0表示相等
System.out.println(bd3.equals(bd4));             //返回的是false  是错误的
                                                 //所以比较的时候使用compareTo()方法

素数筛法

六倍原理

除了2和3以外，其余素数都与6的倍数相邻，满足6x+1和6x-1。也就是说大于3的质数一定和6相邻

埃氏筛法

原理：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

模板代码

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
bool is_prime[1000];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++)
        is_prime[i] = true; //初始化所有的数为素数
    for (int i = 2; i <= sqrt(n); i++)
    { //从第一个素数2开始筛选
        if (is_prime[i])
        { //如果是素数
            for (int j = i * i; j <= n; j += i)
            { //则剔除掉它的倍数
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i])
            cout << i << endl;
    }
    return 0;
}

欧拉筛法（线性筛）

基本思想：埃氏筛法要重复标记很多次相同的数，在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

模板代码

//题目
//求小于等于n的素数的个数，并输出每个素数
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, cnt = 0;
    int prime[100001]; //存素数
    bool vis[100001];  //保证不做素数的倍数
    cin >> n;
    memset(vis, false, sizeof(vis)); //初始化
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])          //不是目前找到的素数的倍数
            prime[cnt++] = i; //找到素数
        for (int j = 0; j < cnt && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = true; //找到的素数的倍数不访问
            if (i % prime[j] == 0)
                break; //关键！！！！
        }
    }
    cout << cnt << endl; //总数
    for (int i = 0; i < cnt; i++)
        cout << prime[i] << endl; //输出每个素数
    return 0;
}

最长上升子序列-LIS

定义：在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。

朴素算法

dp[i] = max(dp[i], dp[j] + 1) (1 <= j < i, a[j] < a[i])

模板代码

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

int a[100];
int dp[100];
int main()
{
    int n;
    fill(dp, dp + sizeof(dp), 1);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) 	//两个for循环遍历整个数组并求dp
        for (int j = 0; j < i; j++)
        {
            if (a[i] > a[j])//满足次条件才能形成升序列
                dp[i] = max(dp[i], dp[j] + 1);
        }

    for (int i = 0; i < n; i++)
        cout << dp[i] << ' ';

        return 0;
 }

二分+贪心优化

#include<iostream>  
#include<string.h>  
#include<algorithm>  
  
using namespace std;
const int maxn = 1e5 + 10;
int num[maxn];
const int INF = 0x3f3f3f3f;
int slow[maxn], d[maxn];

int main()  
{
	fill(slow, slow + maxn, INF);//fill函数初始化
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	int len = -1;
	for (int i = 1; i <= n; i++)
	{
        int j = lower_bound(slow + 1, slow + maxn + 1, num[i]) - slow;//二分查找
        d[i] = j;
		if (len < d[i])
			len = d[i];
		slow[j] = num[i];
	}

	cout << len << endl;//输出最长上升子序列的长度
	return 0;  
}

最长公共子序列-LCS

定义：一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。

模板代码

#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false)
const int N = 1010;
int n, m;
char a[N], b[N];
int dp[N][N];
int main()
{
	memset(dp, 0, sizeof(dp));
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];//A字符串
	for (int j = 1; j <= m; ++j)
		cin >> b[j];//B字符串
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (a[i] == b[j])
				dp[i][j] = dp[i - 1][j - 1] + 1; //左上角的值+1
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);//左边或上边取最大

	cout << dp[n][m] << endl;//最长公共序列

	//以下是输出该序列
	int i = n, j = m, index = 0;
	char lcs[1005];
	while (i != 0 && j != 0)
	{
		if (dp[i][j] == dp[i][j - 1])//反向回退
			j--;
		else if (dp[i][j] == dp[i - 1][j])
			i--;
		else
		{
			lcs[index++] = a[i];
			i--, j--;
		}
	}
	for (int i = index - 1; i >= 0; --i)//最后一步会index会多加一个1所以要在这里减掉
		cout << lcs[i];
	return 0;
}

LCS表格

推一遍就懂了

此处图片丢失

背包

01背包

题目

有N件物品和一个容量为V的背包。第i件物品的费用是w [ i ] ，价值**是v [ i ] **，求将哪些物品装入背包可使价值总和最大。

状态转移方程

核心代码

memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
    {
        if (j >= w[i]) //如果背包装得下当前的物体
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
        else //如果背包装不下当前物体
        {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

例题

优化空间复杂度的01背包

用dp[j]表示当前总重量为j的所有方案中的最大价值

核心代码

for (int i = 1; i <= n; i++)
    for (int j = m; j >= w[i]; j--)//反向线性更新
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

完全背包

题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w [ i ] ，价值是v [ i ]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

可以将完全背包简化成01背包。

状态转移方程

此处图片丢失

优化后

此处图片丢失

还可以根据1背包的优化原则对,完全背包进行优化。

优化代码

#include <iostream>
using namespace std;

int N, V;
int v[1010], val[1010];
int dp[1010];
int main()
{
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> val[i];
    for (int i = 1; i <= N; i++)
        for (int j = 0; j <= V; j++)
        {
            dp[j] = dp[j]; //此时右边的dp[j]是上一层i-1的dp[j],然后赋值给了当前i的dp[i]
            if (j >= v[i])
            {
                dp[j] = max(dp[j], dp[j - v[i]] + val[i]); //dp[j-v[i]],已经被算过
            }
        }
    cout << dp[V] << endl; //输出最大体积,即最优解

    return 0;
}

例题1

多重背包

多重背包也是 01 背包的一个变式。与 01 背包的区别在于每种物品有k个，而非一个。

题目

有N种物品和一个容量为V的背包。第i种物品最多有p[i]件可用，每件费用是w[i] 价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

状态转移方程

此处图片丢失

还是可以转化为01背包问题，但是要用到二进制拆分

此处图片丢失

二进制拆分代码

for (int i = 1; i <= n; i++)
{
    int num = min(p[i], V / w[i]);
    for (int k = 1; num > 0; k <<= 1)
    {
        if (k > num)
            k = num;
        num -= k;
        for (int j = V; j >= w[i] * k; j--)
            dp[j] = max(dp[j], dp[j - w[i] * k] + v[i] * k);
    }
}

例题

例题2

博弈基础

巴什博奕

规则：有一堆n个石子，两个足够聪明的人玩，每个人可以去1～m个石子，取到最后一个石子为胜。

结论：当n%(m+1)==0，先手必输，否则先手必胜。

代码

#include <iostream>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    if (n % (m + 1))
        cout << "先手胜" << endl;
    else
        cout << "后手胜" << endl;
    return 0;
}

例题

威佐夫博弈

规则：有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。

结论：若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5）+1）/2）*z ]；
若w=x，则先手必败，否则先手必胜。

代码

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int n1, n2, temp;
    while (cin >> n1 >> n2)
    {
        if (n1 > n2)
            swap(n1, n2);
        temp = floor((n2 - n1) * (1 + sqrt(5.0)) / 2.0);
        if (temp == n1)
            cout << "后手必胜" << endl;
        else
            cout << "先手必胜" << endl;
    }
    return 0;
}

斐波那契博弈

规则：有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。

结论：先手胜当且仅当n不是斐波那契数（n为物品总数）

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 55;
int f[N];
void Init()
{
    f[0] = f[1] = 1;
    for (int i = 2; i < N; i++)
        f[i] = f[i - 1] + f[i - 2];
}

int main()

{

    Init();
    int n;
    while (cin >> n)
    {
        if (n == 0)
            break;
        bool flag = 0;
        for (int i = 0; i < N; i++)
        {
            if (f[i] == n)
            {
                flag = 1;
                break;
            }
        }
        if (flag)
            puts("Second win");
        else
            puts("First win");
    }
    return 0;
}

例题

尼姆博弈

规则：任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。

结论：把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。

代码

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int n, ans, temp;
    while (cin >> n)
    {
        temp = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> ans;
            temp ^= ans;//异或
        }
        if (temp == 0)
            cout << "后手必胜" << endl;

        else
            cout << "先手必胜" << endl;
    }
    return 0;
}

隔板法

定义：隔板法就是在n个元素间的（n-1）个空中插入k个板，可以把n个元素分成k+1组的方法。

条件：

这n个元素必须互不相异
所分成的每一组至少分得1个元素
分成的组别彼此相异

普通隔板法
例1. 求方程 $x+y+z=10$的正整数解的个数。

分析：将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为x、y、z之值）。则隔法与解的个数之间建立了一一对立关系，故解的个数为$C_{n-1}^{m-1}=C_9^2=36（个）$。

添元素隔板法
例2. 求方程 $x+y+z=10$的非负整数解的个数。

分析：注意到x、y、z可以为零，故例1解法中的限定“每空至多插一块隔板”就不成立了，怎么办呢？只要添加三个球，给x、y、z各添加一个球，这样原问题就转化为求 $x+y+z=13$的正整数解的个数了，则问题就等价于把13个相同小球放入3个不同箱子，每个箱子至少一个，有几种情况？易得解的个数为$C_{n+m-1}^{m-1}=C_{12}^2=66（个）$。

例3：把10个相同小球放入3个不同箱子，第一个箱子至少1个，第二个箱子至少3个，第三个箱子可以放空球，有几种情况？
我们可以在第二个箱子先放入10个小球中的2个，小球剩8个放3个箱子，然后在第三个箱子放入8个小球之外的1个小球，则问题转化为把9个相同小球放3不同箱子，每箱至少1个，几种方法？ $C_8^2=28$

例4. 将20个相同的小球放入编号分别为1，2，3，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。（减少球数用隔板法）

分析：先在编号1，2，3，4的四个盒子内分别放0，1，2，3个球，剩下14个球，有1种方法；再把剩下的球分成4组，每组至少1个，由例1知方法有$C_{13}^3=286（种）$。

例5：有一类自然数，从第三个数字开始，每个数字都恰好是它前面两个数字之和，直至不能再写为止，如257，1459等等，这类数共有几个？
因为前2位数字唯一对应了符合要求的一个数，只要求出前2位有几种情况即可，设前两位为ab
显然$a+b<=9$ ,且a不为0
1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1

1代表9个1，-代表8个空位
我们要把9个1分成两组，但b可以为0，我们先给b一个1，然后就相当于10个小球放入两个（a，b）不同的箱子，每一个箱子至少放一个那就是$C_9^1$，但这是错误的，为什么？因为1不一定要全部放入。其实解决这个问题可以这么想，我们在引进一个盒子c来放ab取完剩下的1，所以报证c中球数大于0，所以要在增加一个球，题目就等价于，11个小球放入两个（a，b）不同的箱子，每一个箱子至少放一个，所以一共有 $C_{10}^2=45$

添板插板法
例5另一种解法：

显然a+b<=9 ,且a不为0
1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - -

1代表9个1，-代表10个空位（第一个没有因为a不能为0），我们可以在这9个空位中插入2个板，分成3组，第一组取到a个1，第二组取到b个1，但此时第二组始终不能取空，若多添加第10个空时，设取到该板时第二组取空，即b=0，所以一共有$C_{10}^2=45$

添板插板法就是添元素隔板法的变形。

选板法

例6：有10粒糖，如果每天至少吃一粒(多不限)，吃完为止，求有多少种不同吃法？
o - o - o - o - o - o - o - o - o – o

o代表10个糖，-代表9块板
10块糖，9个空，插入9块板，每个板都可以选择放或是不放，相邻两个板间的糖一天吃掉
这样一共就是 $2^9=512$

分类插板

例7：小梅有15块糖，如果每天至少吃3块，吃完为止，那么共有多少种不同的吃法？
此问题不能用插板法的原因在于没有规定一定要吃几天，因此我们需要对吃的天数进行分类讨论
最多吃5天，最少吃1天
1：吃1天或是5天，各一种吃法一共2种情况
2：吃2天，每天预先吃2块，即问11块糖，每天至少吃1块，吃2天，几种情况？ $C_{10}^ 1=10 $
3：吃3天，每天预先吃2块，即问9块糖，每天至少1块，吃3天? $C_{8}^ 2=28 $
4：吃4天，每天预先吃2块，即问7块糖，每天至少1块，吃4天？$C_{6}^ 3=20 $
所以一共是 $2+10+28+20=60种$

逐步插板法

例8 ：在一张节目单中原有6个节目，若保持这些节目相对次序不变，再添加3个节目，共有几种情况？
-o - o - o - o - o - o - 三个节目abc
可以用一个节目去插7个空位，再用第二个节目去插8个空位，用最后个节目去插9个空位
所以一共是 $C_7^1×C_8^1×C_9^1=504种$

快速幂算法

快速幂

作用：解决乘法溢出问题，如2^100 % 10086

要用到模运算规律：(a * b) % p = (a % p * b % p) % p

朴素版

int ans=1;
for (int i=1; i<=b; ++i)
{
    ans *= a % p;
}
return ans % p;

但是朴素版时间复杂度过高为O(N)

优化版

int pow(int a, int b, int p)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p; //若b&1==1，就选择当前的迭代值a和res累乘。
        a = a * a;             //迭代构造a,a是初始值的2的整数次幂
        b = b >> 1;            //将b右移一位
    }                          //以上计算得到a^b
    return ans % p;            //取模
}

龟速乘

作用：当(a * b) % p中a和b过大时，快速幂也会超出数据范围，可以使用龟速乘防止爆掉

//防止在乘法过程中爆ll
ll fast_mult(ll a, ll b)
{
    ll res = 0;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res + a) % n;
        }
        b >>= 1;
        a = (a + a) % n;
    }
    return res % n;
}

矩阵快速幂

矩阵乘法

const int N = 100;
int c[N][N];
void multi(int a[][N], int b[][N], int n) //n是矩阵大小，n<N
{
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                c[i][j] += a[i][k] * b[k][j];
}

矩阵快速幂模板

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int M, n;
struct node //定义一个矩阵类型的结构体
{
    int m[100][100];
} ans, res; //ans是结果，res是最初的方阵
node mul(node A, node B)
{
    int i, j, k;
    node temp;              //定义一个临时矩阵，存放A*B的结果
    for (i = 0; i < n; i++) //先全部定义为0
    {
        for (j = 0; j < n; j++)
        {
            temp.m[i][j] = 0;
        }
    }
    for (i = 0; i < n; i++) //矩阵相乘的代码
    {
        for (j = 0; j < n; j++)
        {
            for (k = 0; k < n; k++)
            {
                temp.m[i][j] += A.m[i][k] * B.m[k][j];
            }
        }
    }
    return temp;
}
void fastpow(int M, int n)
{
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (i == j)
            {
                ans.m[i][j] = 1;
            }
            else
                ans.m[i][j] = 0;
        }
    } //这里是思想的转换，之前我们定义为1去计算，所以我们先初始化ans为
    //单位矩阵，我们知道单位矩阵与任何矩阵的乘积为其本身
    while (M) //快速幂的步骤
    {
        if (M & 1)
        {
            ans = mul(ans, res);
        }
        res = mul(res, res);
        M = M >> 1;
    }
}
int main()
{
    cin >> n; //方阵的阶数
    cin >> M; //指数
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            cin >> res.m[i][j]; //初始化方阵res
        }
    }
    fastpow(M, n);          //进行快速幂
    for (i = 0; i < n; i++) //输出
    {
        for (j = 0; j < n; j++)
        {
            cout << ans.m[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

数论基础

同余式

定义：同余式是数论的基本概念之一，设m是给定的一个正整数，a、b是整数，若满足m| (a-b)，则称a与b对模m 同余，记为a≡b (mod m)，或记为a≡b (m)。

逆元

每个数a均有唯一的与之对应的乘法逆元x，使得ax≡1(mod n) ，一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在。
逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

逆元的定义：定义：正整数 a, n，如果有 ax ≡ 1(mod n)，则称 x 的最小正整数解为 a 模 n的逆元。

扩展欧几里得算法

#include <cstdio>
#include <iostream>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return r;
}
int inv(int n, int m)
{
    int x, y;
    int ans = exgcd(n, m, x, y);
    if (ans == 1)
        return (x % m + m) % m;
    //定义：正整数 a, n，如果有 ax ≡ 1(mod n)，则称 x 的最小整数解为 a 模 n的逆元。
    else
        return -1;
}
int main()
{
    int n, m;
    cin >> n >> m;
    int ans = inv(n, m);
    ans == -1 ? cout << "no" << endl : cout << ans << endl;
    return 0;
}
/*
    intput:
    5 7
    22 29
    100 97
    
    output:
    3
    4
    65
*/

费马小定理

定义：若存在整数 a , p 且gcd(a,p)=1,即二者互为质数，则有a^(p-1)≡ 1(mod p)。

费马小定理求逆元

long long fast_pow(long long a, long long b, long long p)
{
    long long ans = 1;
    a %= p;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ans;
}
long long inv(long long x, long long p)
{
    return fast_pow(x, p - 2, p);
}

KMP算法

KMP是一种时间复杂度O(n+m)的字符串单模匹配算法，核心是通过预处理模式串的所有前缀串的最长相同前后缀，构造next数组，在原串与模式串匹配失败时参考next数组做跳转避免原串指针的回退并减少模式串指针的回退长度
next数组是一个大小与模式串长度相同的数组，next[i]为模式串[0,i)子串的最长相同前后缀长度

构造next数组

//优化过后的next 数组求法
void GetNext(char *p, int next[])
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++j;
            ++k;
            if (p[j] != p[k])
                next[j] = k; 
            else
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}

kmp模板

int Kmp(char *s, char *p)
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while (i < sLen && j < pLen)
    {
        //如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
            //next[j]即为j所对应的next值
            j = next[j];
        }
    }
    if (j == pLen)
        return i - j;
    else
        return -1;
}

例题1

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#define Memset(x, a) memset(x, a, sizeof(x))
using namespace std;
const int N = 1e6 + 10;
char w[N], t[N];
int next[N];
int sum;

void getNext(const char P[], int next[])
{
    int m = strlen(P);
    int i = 0, j;
    j = next[0] = -1;
    while (i < m)
    {
        while (-1 != j && P[i] != P[j])
            j = next[j];
        next[++i] = ++j;
    }
}

void kmp(const char T[], const char P[], int next[])
{
    int n = strlen(T), m = strlen(P);
    int i, j;
    getNext(P, next);
    i = j = 0;
    while (i < n)
    {
        while (-1 != j && T[i] != P[j])
            j = next[j];
        i++;
        j++;
        if (j >= m)
        {
            sum++;
            j = next[j]; //这儿修改很重要，不然会超时
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        sum = 0;
        Memset(next, 0);
        scanf("%s%s", w, t);
        kmp(t, w, next);
        printf("%d\n", sum);
    }
    return 0;
}

例题2(next数组的使用)

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#define Memset(x, a) memset(x, a, sizeof(x))
using namespace std;
const int N = 4e5 + 10;
int next[N], ans[N];
char s[N];

void getNext(const char P[], int next[])
{
    int m = strlen(P);
    int i = 0, j;
    j = next[0] = -1;
    while (i < m)
    {
        while (-1 != j && P[i] != P[j])
            j = next[j];
        next[++i] = ++j;
    }
}

int main()
{
    while (~scanf("%s", s))
    {
        Memset(next, 0);
        getNext(s, next);
        int cnt = 0;
        int len = strlen(s);
        int j = next[len];
        while (j > 0)
        {
            ans[++cnt] = j;
            j = next[j];
        }
        for (int i = cnt; i > 0; i--)
            printf("%d ", ans[i]);
        printf("%d\n", len);
    }
    return 0;
}

manacher算法

求最长回文子串，一般从字符串的中心开始向两侧遍历，为了防止偶数字串，在每个字符的左右都加上一个特殊字符如#（前提是这个字符在字符串中没有出现）使这两种回文串都变成奇回文串，因为原回文串长度是n,必将插入n+1个分隔符,处理之后的长度为2n+1,无论n的奇偶,2n+1必为奇数,故处理后必是奇回文串

#define maxn 1000010
#include <bits/stdc++.h>

using namespace std;

char str[maxn] = {"3212343219"}; //原字符串
char tmp[maxn * 2];              //转换后的字符串
int Len[maxn * 2];

//转换原始串
int init(char *st)
{
    int i, len = strlen(st);
    tmp[0] = '@'; //字符串开头增加一个特殊字符，防止越界
    for (i = 1; i <= 2 * len; i += 2)
    {
        tmp[i] = '#';
        tmp[i + 1] = st[i / 2];
    }
    tmp[2 * len + 1] = '#';
    tmp[2 * len + 2] = '$'; //字符串结尾加一个字符，防止越界
    tmp[2 * len + 3] = 0;
    return 2 * len + 1; //返回转换字符串的长度
}
//Manacher算法计算过程
int manacher(char *st, int len)
{
    int mx = 0, ans = 0, po = 0; //mx即为当前计算回文串最右边字符的最大值
    for (int i = 1; i <= len; i++)
    {
        if (mx > i)
            Len[i] = min(mx - i, Len[2 * po - i]); //在Len[j]和mx-i中取个小
        else
            Len[i] = 1; //如果i>=mx，要从头开始匹配
        while (st[i - Len[i]] == st[i + Len[i]])
            Len[i]++;
        if (Len[i] + i > mx) //若新计算的回文串右端点位置大于mx，要更新po和mx的值
        {
            mx = Len[i] + i;
            po = i;
        }
        ans = max(ans, Len[i]);
    }
    return ans - 1; //返回Len[i]中的最大值-1即为原串的最长回文子串额长度
}

int main()
{
    int len = init(str);
    manacher(tmp, len);
}

manacher例题

AC代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int MOD=10007;
const int N=200000+5;
const int dx[]= {-1,1,0,0};
const int dy[]= {0,0,-1,1};
using namespace std;
int str[N];
int newStr[N*2];
int p[N*2];
int n;
int init(){
    newStr[0]=-1;
    newStr[1]=0;
 
    int j=2;
    int len=n;
    for (int i=0;i<len;i++){
        newStr[j++]=str[i];
        newStr[j++]=0;
    }
 
    return j;
}
 
int manacher(){
    int len=init();
    int res=-1;
 
    int id;
    int mx=0;
    for(int i=1;i<len;i++){
        int j=2*id-i;
        if(i<mx)
            p[i]=min(p[j], mx-i);
        else
            p[i]=1;
 
        while(newStr[i-p[i]]==newStr[i+p[i]] &&  newStr[i-p[i]]<=newStr[i-p[i]+2] )
            p[i]++;
 
        if(mx<i+p[i]){
            id=i;
            mx=i+p[i];
        }
        res=max(res,p[i]-1);
    }
    return res;
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%d",&str[i]);
        printf("%d\n",manacher());
    }
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。