图论

朴素/堆优化Dijkstra（正权边无环最短路）

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

int dist[100000],g[600][600],st[100000];
int n,m;
void d()
{
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		{
			if(!st[j]&&(t==-1||dist[j]<dist[t]))
			{
				t=j;
			}
		}
		st[t]=1;
		for(int j=1;j<=n;j++)
		{
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}
}
int main()
{
	memset(g,0x3f,sizeof(g));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		g[a][b]=min(g[a][b],w);
	}
	d();
	if(dist[n]==0x3f3f3f3f)
	cout<<-1;
	else
	cout<<dist[n];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 150010, MAXN = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
int st[N], dis[N];
typedef pair<int, int> PII;

priority_queue<PII, vector<PII>, greater<PII> > heap;

int n, m;
void add(int a, int b, int d)
{
    e[idx] = b;
    w[idx] = d;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int d()
{
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	heap.push({0,1});
	while(heap.size())
	{
		PII t=heap.top();
		heap.pop();
		int d=t.first,u=t.second;
		if(st[u])continue;
		st[u]=1;
		for(int i=h[u];i!=-1;i=ne[i])
		{
			int v=e[i];
			if(dis[v]>d+w[i])
			{
				dis[v]=d+w[i];
				heap.push({dis[v],v});
			}
		}
	}
	if(dis[n]==MAXN)
		return -1;
	else
		return dis[n];
}
int main()
{
	memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);

    for(int i = 1;i <= m; i++){
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        add(a, b, d);
    }

    int t = d();
    printf("%d\n", t);

    return 0;
}

spfa算法（负权边无负环）

const int INF = 0x3f3f3f3f;
int n;      // 总点数
int h[N], w[M], e[M], ne[M], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        int u = q.front();
        q.pop();

        st[u] = false;

        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if (dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                if (!st[v])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }

    if (dist[n] == INF) return INF;
    return dist[n];
}

Bellman-ford算法(负权边无负环)（有边数限制的最短路）

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

//边，表示点a到点b的距离为w
struct edge{
    int a, b, w;
}ed[M];

//使用backup[]备份dis[]
//使用之前的最短距离更新当前最短距离，防止发生串联
int dis[N], backup[N];
int n, m, k;

int bellman_ford(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    //循环k次求经过不超过k条边走到每个点的最短距离
    for(int i = 1; i <= k ; i ++){
        memcpy(backup, dis, sizeof dis);
        for(int j = 1; j <= m; j ++){ //遍历每条边，进行松弛
            int a = ed[j].a, b = ed[j].b, w = ed[j].w;
            dis[b] = min(dis[b], backup[a] + w);
        }
    }
    //在松弛过程中可能会改变到n点最短距离，但实际并不存在到n点的最短路径
    if(dis[n] < INF / 2) return dis[n];
    else return INF;
}

Kruskal算法(最小生成树）

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
struct edge
{
    int a,b,w;
} e[2*N];
int n,m;
int p[N];
int cnm(const edge &e1,const edge &e2)
{
    return e1.w<e2.w;
}
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int kruskal()
{
    sort(e+1, e+1 + m, cnm);

    for (int i = 1; i <= n; i ++ ) p[i] = i; 

    int res = 0, cnt = 1;
    for (int i = 0; i < m; i ++ )
    {
        int a = e[i].a, b = e[i].b, w = e[i].w;

        a = find(a), b = find(b);
        if (a != b)     
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return 0x3f3f3f3f;
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].a>>e[i].b>>e[i].w;
    }
    int t=kruskal();
    if(t==0x3f3f3f3f)
    cout<<"impossible";
    else 
    cout<<t;
}

prim求最小生成树

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中

// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

数据结构

单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

队列

//1、普通队列

// head 表示队头，tail表示队尾
int q[N], head = 0, tail = -1;

// 向队尾插入一个数
q[ ++ tail] = x;

// 从队头弹出一个数
head ++ ;

// 队头的值
q[head];

// 判断队列是否为空
if (head <= tail)
{

}

//2、循环队列

// head 表示队头，tail表示队尾的后一个位置
int q[N], head = 0, tail = 0;

// 向队尾插入一个数
q[tail ++ ] = x;
if (tail == N) tail = 0;

// 从队头弹出一个数
head ++ ;
if (head == N) head = 0;

// 队头的值
q[head];

// 判断队列是否为空
if (head != tail)
{

}

单调栈

int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

单调队列（滑动窗口）

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}
 

KMP算法

//s[]是长文本，p[]是模式串，n是s的长度，m是p的长度，求模式串的ne数组
ne[1]=0; //初始状态
for(int i=2, j=0; i<=m;i++){
    //j没有回到起点，并且没有匹配成功
    if(j&&p[j+1]!=p[i]) j=ne[j];
    if(p[j+1]==p[i]) j++; //匹配成功
    ne[i]=j; //将当前匹配个数赋值给ne[i]
}

//kmp匹配
for(int i=1, j=0;i<=n;i++){
    //j没有回到起点（即没有重新开始匹配），并且模式串的下一个字符跟文本串当前字符匹配失败
    if(j&&p[j+1]!=s[i])
        j=ne[j]; //回溯模式串的指针j，从ne[j]开始继续匹配，相当于将模式串后移
    if(p[j+1]==s[i]) //匹配成功
        j++;//模式串指针j后移，继续匹配下一个字符
    if(j==n){//模式串匹配完毕
        printf("%d ", i-n); //输出匹配起点位置
        j=ne[j];//移动模式串指针j，继续下一次匹配
    }
}

trie字符串统计

int son[N][26], cnt[N], idx;
char s[N];
void insert(char s[]){
    int p=0; //从根结点开始查询
    for(int i=0;s[i];i++){//从前向后遍历字符串
        int u=s[i]-'a'; //将当前字符映射为[0...25]的一个数字
        if(!son[p][u]) son[p][u]=++idx; //为当前根结点分配一个子结点
        p=son[p][u]; //将子结点作为新的根结点，继续处理下一个字符
    }
    cnt[p]++; //以p结尾的单词增加一个
}

int query(char s[]){
    int p=0; //从根结点开始查询
    for(int i=0;s[i];i++){
        int u=s[i]-'a';//将当前字符映射为[0...25]的一个数字
        if(!son[p][u]) return 0; //如果不存在该字符，即没有找到，返回0
        p=son[p][u];//将子结点作为新的根结点，继续处理下一个字符
    }
    return cnt[p]; //返回以p结尾的单词出现次数
}

合并集合

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点，并进行路径压缩
int find(int x)
{
  // find(p[x]) 递归查找p[x]的祖宗节点
  // p[x] = find(p[x]); 路径压缩，将路径上所有点的都连接到祖宗节点
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

连通块中点的数量

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

堆

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// pos[k]存储第k个插入的点在堆中的位置
// ord[i]存储堆中下标是i的点是第几个插入的
// idx 记录插入顺序
// si 记录堆的大小
int h[N], pos[N], ord[N], idx, si;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(pos[ord[a]],pos[ord[b]]);
    swap(ord[a], ord[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

模拟散列表

//(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

//(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

字符串哈希

//核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
//小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

排序

快速排序

void quickSort(int a[], int l, int r){
  	if(l >= r) return;
    int i = l - 1, j = r + 1, v = a[l + r >> 1];
  	while(i < j)
    {
      do ++ i;  while(a[i] < v);
      do --j; 	while(a[j] > v);
      if(i < j) swap(a[i], a[j]);
    }
  	//注意，这里是到分成了[l,j]和[j + 1, r]两个区间
  	quickSort(a, l, j);
  	quickSort(a, j + 1, r);
}

归并排序

void mergeSort(int a[], int l, int r){
    if(l>=r) return;//当只剩一个元素时，递归结束
    int mid=l + r >>1; //找到中心位置
    //分成两个区间处理
    mergeSort(a, l, mid);//对左半区间进行归并排序
    mergeSort(a, mid + 1, r);//对右半区间进行归并排序
    //将a[]两个有序区间的数合并到b[]
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        //在两个区间中选择较小的数放入到b数组
        if(a[i]<=a[j]) b[k++]=a[i++];
        else b[k++]=a[j++];
    }
    //如果两边边区间还有剩余，则将剩余元素放入b数组
    while(i <= mid) b[k++]=a[i++];
    while(j <= r) b[k++]=a[j++];
    //将b[]数据赋值到a[]，继续排序
    for(int i = l; i <= r; i++) a[i] = b[i];
}

逆序对的数量

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 100010;
int a[N], b[N];
LL ans = 0;

void merge_sort(int l, int r)
{
    if(l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
    {
        if(a[i] > a[j])
        {
            ans += mid - i + 1;
            b[k ++] = a[j ++];
        }
        else b[k ++] = a[i ++];
    }
    
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    
    for(int i = l; i <= r; i ++) a[i] = b[i];

}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    
    merge_sort(0, n - 1);
    
    cout << ans << endl;
    
    return 0;
}

二分

数的范围

#include <iostream>

using namespace std;

const int N = 100010;

int a[N];

int lower(int l, int r, int x)
{
    while(l < r)
    {
        int mid = l + r >> 1;
        
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if(a[l] == x) return l;
    else return -1;
}

int upper(int l, int r, int x)
{
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        
        if(a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    if(a[l] == x) return l;
    else return -1;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    while(m --)
    {
        int x;
        cin >> x;
        
        int l = lower(0, n - 1, x);
        int r = upper(0, n - 1, x);
        
        cout << l << ' ' << r << endl;
    }
    return 0;
}

数的三次方根

#include<bits/stdc++.h>
using namespace std;
double n;
double b(double l, double r)
{
    const double eps = 1e-8;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (mid*mid*mid>n) r = mid;
        else l = mid;
    }
    return l;
}

int main()
{
    cin>>n;
    printf("%.6f",b(-100.0,100.0));
}

前缀和与差分

前缀和

#include <iostream>

using namespace std;

const int N = 100010;

int s[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        s[i] = s[i - 1] + x;
    }

    while(m--){
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
}

子矩阵的和

#include <iostream>

using namespace std;

const int N = 1010;

int a[N][N],s[N][N];

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    while(q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

差分

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



const int N = 1000010;

int a[N], b[N];

void add(int l, int r, int c)
{
  b[l] += c, b[r + 1] -= c;
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        //构造差分数组
        add(i, i, a[i]);
    }

    while(m--){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;
        b[r + 1] -= c; 
    }

    for(int i = 1; i <= n; i++){
        //通过计算前缀和，输出操作后的原数组
        b[i] += b[i - 1];
        printf("%d ", b[i]);
    }

}

差分矩阵

#include <iostream>

using namespace std;

const int N = 1010;
int n, m, q;
int b[N][N];

void add(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c, b[x1][y2 + 1] -= c, b[x2 + 1][y1] -= c, b[x2 + 1][y2 + 1] += c; 
}

int main()
{
    cin >> n >> m >> q;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            int c;
            cin >> c;
            add(i, j, i, j, c);
        }
        
        
    while(q --)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        
        add(x1, y1, x2, y2, c);
    }
    
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            cout << b[i][j] << ' '; 
        }
        puts("");
    }
    
    return 0;
}

位运算

李白打酒

print 14

得到整数

#include<bits/stdc++.h>
using namespace std;
int a[10000];
int main()
{
    int n,x;
    cin>>n>>x;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int sum=0;
    for(int i=0;i<(1<<n);i++)
    {
        int res=0;
        for(int j=0;j<n;j++)
            if(i>>j&1)
                res+=a[j];
        if(res==x)
            sum++;
    }
    cout<<sum;
}

二进制中1的个数

略

广度优先搜索

池塘计数

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int st[1000010];
int g[1010][1010];
queue<PII> q;
void dfs(int x,int y)
{
    q.push(make_pair(x,y));
    g[x][y]=0;
    while(q.size())
    {
        PII t=q.front();
        q.pop();
        int x1=t.first;
        int y1=t.second;
        for(int i=-1;i<=1;i++)
        {
            for(int j=-1;j<=1;j++)
            {
                if(g[x1+i][y1+j]==1)
                {
                    q.push(make_pair(x1+i,y1+j));
                    g[x1+i][y1+j]=0;
                }
            }
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            if(c=='W')
            {
                g[i][j]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j])
            {
                ans++;
                dfs(i,j);
            }

        }
    }
    cout<<ans;
}

山峰和山谷

略

走迷宫

#include<bits/stdc++.h>
using namespace std;
int g[101][101];
typedef pair<int,int> PII;
queue<PII> q;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m;
void dfs()
{
    q.push(make_pair(1,1));
    g[1][1]=1;
    while(q.size())
    {
        PII t=q.front();
        q.pop();
        int x1=t.first;
        int y1=t.second;
        for(int i=0;i<4;i++)
            if(!g[x1+dx[i]][y1+dy[i]]&&x1+dx[i]<=n&&y1+dy[i]<=m&&x1+dx[i]>=1&&y1+dy[i]>=1)
            {
                g[x1+dx[i]][y1+dy[i]]=g[x1][y1]+1;
                q.push(make_pair(x1+dx[i],y1+dy[i]));
            }
    }
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    dfs();
    cout<<g[n][m]-1;
}

迷宫问题

#include <iostream>

using namespace std;

const int N = 1010;
int n;
int g[N][N], q[N * N][2], pre[N][N][2];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int st[N][N];
void bfs(int x, int y)
{
    int hh = 0, tt = 0;
    q[tt][0] = x, q[tt][1] = y, st[x][y] = 1;
    while(hh <= tt)
    {
        int x = q[hh][0], y = q[hh][1];
        hh ++;
        
        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(g[a][b] || st[a][b]) continue;
            
            q[++ tt][0] = a, q[tt][1] = b, st[a][b] = 1, pre[a][b][0] = x, pre[a][b][1] = y;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> g[i][j];
    
    bfs(n - 1, n - 1);
    
    int ex = 0, ey = 0;

    while(true)
    {
        cout << ex << ' ' << ey << endl;
        if(ex == n -1 && ey == n - 1) break;
        int x = pre[ex][ey][0], y = pre[ex][ey][1];
        ex = x, ey = y;
    }
    return 0;
}

矩阵距离

略

八数码

#include <iostream>
#include <queue>
#include <map>

using namespace std;

const int N = 20;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int bfs(string s)
{
    string e = "12345678x";
    queue<string> q;
    map<string, int> dist;
    q.push(s), dist[s] = 0;
    
    while(q.size())
    {
        string t = q.front();
        q.pop();
        
        if(t == e) return dist[t];
        
        int idx = t.find('x');
        int x = idx / 3, y = idx % 3;
        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= 3 || b < 0 || b >= 3) continue;
            
            string backup = t;
            int k = a * 3 + b;
            swap(backup[k], backup[idx]);
            if(dist.count(backup))  continue;
            
            q.push(backup), dist[backup] = dist[t] + 1;
        }
    }
    return -1;

}

int main()
{
    string s;
    
    for(int i = 0; i < 9; i ++) 
    {
        char c;
        cin >> c;
        s += c;
    }
    
    cout << bfs(s) << endl;
    
    return 0;
}

抓住那头牛

#include <bits/stdc++.h>

using namespace std;
int n,m;
int q[1000100][2];
int minn[1100000];
void bfs(int x)
{
    int h,t,cost;
    h=t=1;
    q[t][0]=x;
    q[t][1]=0;
    t++;
    while(h!=t)
    {
        for(int i=1;i<=3;i++)
        {
            x=q[h][0];
            cost=q[h][1];
            if(i==1)
            {
                x++;
            }
            else
            {
                if(i==2)
                    x--;
                else
                    x*=2;
            }
            if(x>0&&x<=1000000)
            {
                if(minn[x]<0||minn[x]>cost+1)
                {
                    q[t][0]=x;
                    q[t][1]=cost+1;
                    t++;
                    minn[x]=cost+1;
                }
            }
        }
        h++;
    }
}
int main()
{
    cin>>n>>m;
    memset(minn,0xff,sizeof(minn));
    if(n==m)
    {
        cout<<0;
        return 0;
    }
    bfs(n);
    cout<<minn[m];
    return 0;
}

深度优先搜索

红与黑

#include <iostream>
#include <cstring>

using namespace std;

const int N = 25;

char g[N][N];
int n, m;
int st[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int dfs(int x, int y)
{
    st[x][y] = 1;
    int cnt = 1;
    for(int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];

        if(a < 0 || a >= n || b < 0 || b >= m) continue;

        if(g[a][b] == '#' || st[a][b]) continue;

        cnt += dfs(a, b);
    }

    return cnt;
}

int main()
{  
    while(cin >> m >> n, m || n)
    {
        int x, y;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j++)
            {
                cin >> g[i][j];
                if(g[i][j] == '@') x = i, y = j;
            }

        memset(st, 0, sizeof st);

        cout << dfs(x, y) << endl;
    }

    return 0;
}

迷宫

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

const int N = 110;

int n;
char g[N][N];
int sx, sy, ex, ey;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int st[N][N];

bool dfs(int x, int y)
{
    //注意：下面两行代码不能颠倒
    //因为如果(x,y)是'#'则说明该点不可达，优先级更高
    if(g[x][y] == '#') return false;
    if(x == ex && y == ey) return true;

    //注意：这里将(x,y)点标记为已访问过
    //即经过(x,y)所有的路径不能在走回到(x,y)
    st[x][y] = true;

    //尝试所有从(x,y)扩展出去的点
    for(int i = 0; i < 4; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if(st[nx][ny]) continue;

        //如果成功找到一条路径，返回true
        if(dfs(nx, ny)) return true;
    }

    //所有路径都尝试完毕，没有到达终点，返回false
    return false;
}

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        cin >> n;

        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);

        cin >> sx >> sy >> ex >> ey;

        memset(st, 0, sizeof st);
        if(dfs(sx, sy)) puts("YES");
        else puts("NO");
    }

    return 0;
}

选数

#include <iostream>
#include <cmath>
using namespace std;
#define m 9999999
int n,k;

int a[100];
bool c[10000000];
int tot;

int ans[1000];
void dfs(int t,int sum)
{
    if(t==k&&!c[sum])
    {
        tot++;
        return;
    }
    for(int i=ans[t-1]+1;i<=n;i++)
    {
            ans[t]=i;
            dfs(t+1,sum+a[i]);
    }
}
int main()
{
    for(long long a=2;a<=sqrt(m);a++)
        if(c[a]==false)
            for(long long i=2;i<=m/a;i++)
                c[a*i]=true;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dfs(0,0);
    cout<<tot;
    return 0;
}

8皇后问题

#include <bits/stdc++.h>

using namespace std;
int a[1000];
int n=8;
int ans[1000][1000],tot=1;
int chak(int t)
{
    for(int i=1;i<=t-1;i++)
    {
        if(a[i]==a[t]||abs(a[i]-a[t])==abs(i-t))
        {
            return 0;
        }
    }
    return 1;
}
void dfs(int t)
{
    if(t>n)
    {
        for(int i=1;i<=n;i++)
        {
            ans[tot][i]=a[i];
        }
        tot++;
    }
    for(int i=1;i<=n;i++)
    {
        a[t]=i;
        if(chak(t))
        {
            dfs(t+1);
        }
    }
}
int main()
{
    dfs(1);
    int kl;
    cin>>kl;
    int z;
    for(int i=1;i<=kl;i++)
    {
        cin>>z;
        for(int i=1;i<=n;i++)
        {
            cout<<ans[z][i];
        }
        cout<<endl;
    }
    return 0;
}

有重复元素的排列问题

略

马走日

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;

int f[N][N], vis[N][N], res;

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2, }, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int m, n, x, y;

void dfs(int x, int y, int cnt)
{
    if(cnt == m * n) 
    {
        res++;
        return;
    }
    
    vis[x][y] = 1;
    
    for(int i = 0; i < 8; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny])
        {
            dfs(nx, ny, cnt + 1);
        }
    }
    
    vis[x][y] = 0;
}

int main()
{
    int kase;
    cin >> kase;
    
    while(kase--)
    {
        res = 0;
        memset(vis, 0, sizeof vis);
        
        cin >> m >> n >> x >> y;
        
        dfs(x, y, 1);
        
        cout << res << endl;
        
    }
}

动态规划

摘花生

#include<bits/stdc++.h>
using namespace std;
int f[1000][1000];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        for(int j=1;j<=a;j++)
        {
            for(int k=1;k<=b;k++)
            {
                cin>>f[j][k];
            }
        }
        for(int j=1;j<=a;j++)
        {
            for(int k=1;k<=b;k++)
            {
                f[j][k]=max(f[j-1][k],f[j][k-1])+f[j][k];
            }
        }
        cout<<f[a][b];
        cout<<endl;
    }
}

最长不下降子序列

#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N], dp[N]; //dp[i]表示到i个字符之前的最长不下降子序列的长度

int main(){
  int n, ans=0;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++){
  	int maxx=0;
    for(int j=1;j<i;j++){
    	if(a[j]<=a[i]&&dp[j]>maxx){ //a[j]<=a[i]保证不下降
        	maxx=dp[j];
        }
    }
    dp[i]=maxx+1;
  }
  for(int i=1;i<=n;i++){
  	if(ans<dp[i]) ans=dp[i];
  }
  cout<<ans<<endl;
  return 0;
}

最长公共子序列

#include <bits/stdc++.h>

using namespace std;
int f[5010][5010];
char a[10000];
char b[10000];
int main()
{
    int n;
    cin>>n;
    cin>>a+1;
    int m;
    cin>>m;
    cin>>b+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i]==b[j])
                f[i][j]=f[i-1][j-1]+1;
            else
                f[i][j]=max(f[i-1][j],f[i][j-1]);
    cout<<f[n][m];
    return 0;
}

最短编辑距离

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

const int N = 1010;
int dp[N][N];
char a[N], b[N];

int main(){
    int n, m;
  cin>>n>>a+1>>m>>b+1;
    for(int i = 1; i <= m; i++) dp[0][i] = i;
    for(int i = 1; i <= n; i++) dp[i][0] = i;
    
  	for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    cout<<dp[n][m];
    return 0;
}

01背包

#include <bits/stdc++.h>

using namespace std;
int f[1000];
int w[1000];
int v[1000];
int main()
{
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=w[i];j--)
        {
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
    cout<<f[m];
    return 0;
}

完全背包

#include <bits/stdc++.h>
//感觉动归背包不熟，二刷代码加注释，share 哦 
//z5012 普通 
using namespace std;
int m,n;
int dp[1010][1010];
int w[1000000];//weight
int v[1000000];//value
//完全背包
//dp[i][j] -->前i件物品当容量为j时的最大价值
//dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) 
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		 cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			for(int k=0;k*w[i]<=j;k++)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);
			}
		}
	}
	cout<<dp[n][m];
}

多重背包

#include <bits/stdc++.h>

using namespace std;
int f[1000][1000];
int w[1000];
int v[1000];
int c[1000];
int main()
{
    int m,n;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i]>>c[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
           for(int k=0;k*w[i]<=j&&k<=c[i];k++)
           {
               f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*v[i]);
           }
        }
    }
    cout<<f[n][m];
    return 0;
}

直线石子合并

#include<bits/stdc++.h>
using namespace std;
int d1[1001][1001];
int d2[1001][1001];
int sum[1001]; 
int a[1001];
int main()
{
	int n;
	cin>>n;
	memset(d1,0x3f,sizeof(d1));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		d1[i][i]=0;
		
	}
	for(int v=2;v<=n;v++)
	{
		for(int i=1;i<=n-v+1;i++)
		{
			int j=i+v-1;
			for(int k=i;k<=j-1;k++)
			{
				d1[i][j]=min(d1[i][j],d1[i][k]+d1[k+1][j]+sum[j]-sum[i-1]);
				d2[i][j]=max(d2[i][j],d2[i][k]+d2[k+1][j]+sum[j]-sum[i-1]);
			}
		}
	} 
	cout<<d1[1][n]<<endl;
	cout<<d2[1][n]<<endl;
	return 0;
}

环形石子合并

#include <bits/stdc++.h>

using namespace std;
int a[10000];
int dp[1010][1010];
int dp2[1010][1010];
int sum[1010];
int main()
{
    int n;
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    memset(dp2,0,sizeof(dp2));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i];

    }
    for(int i=1;i<=2*n-1;i++)
    {
        sum[i]=sum[i-1]+a[i];
        dp[i][i]=0;
    }
    for(int v=2;v<=n;v++)
    {
        for(int i=1;i<=2*n-v;i++)
        {
            int j=i+v-1;
            for(int k=i;k<=j-1;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
                dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    int ma=0;
    long long mi=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        if(dp2[i][i+n-1]>ma)
            ma=dp2[i][i+n-1];
        if(dp[i][i+n-1]<mi)
            mi=dp[i][i+n-1];
    }
    cout<<mi<<endl<<ma;
    return 0;
}

滑雪

#include <iostream>
using namespace std;
const int N=310;
int a[N][N],f[N][N];
int n,m;
int res;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int dfs(int x,int y)
{
	if(f[x][y]) return f[x][y];
	f[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]<a[x][y])
		{
			f[x][y]=max(dfs(nx,ny)+1,f[x][y]);
		}
	}
	return f[x][y];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
	{
        for(int j=1;j<=m;j++)
		{
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
	{
        for(int j=1;j<=m;j++)
		{
            res=max(dfs(i,j),res);
        }
    }
    cout<<res;
    return 0;
}

没有上司的舞会

#include <iostream>
#include <cstring>

using namespace std;
const int N = 6010;
int dp[N][2], happy[N];
int h[N], ne[N], e[N], idx;
int fa[N];
void add(int x, int y)
{
    e[idx] = y;
    ne[idx] = h[x];
    h[x] = idx;
    idx++;
}
void dfs(int u)
{
    dp[u][1] = happy[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int s = e[i];
        dfs(s);
        dp[u][0] += max(dp[s][0], dp[s][1]);
        dp[u][1] += dp[s][0];
    }
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &happy[i]);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        fa[a] = b; 
    }
    int root = 1;
    while(fa[root]) root++; 
    dfs(root);
    printf("%d\n", max(dp[root][0], dp[root][1]));
    return 0;
}

组合数

求组合数I

#include <bits/stdc++.h>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
int main()
{
    int n; 
    scanf("%d", &n);
    for(int i = 0; i < N; i++) 
        for(int j = 0; j <= i; j++)    
            if(!j) c[i][j] = 1; 
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    while(n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }
}

求组合数II

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010,mod=1e9+7;
int fact[N],infact[N];
int qmi(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=(LL)res*a%p;
		a=(LL)a*a%p;
		b/=2;
	}
	return res;
}
int main()
{
	fact[0]=infact[0]=1;
	for(int i=1;i<N;i++)
	{
		fact[i]=(LL)fact[i-1]*i%mod;
		infact[i]=qmi(fact[i],mod-2,mod)%mod;
	}
	int n;
	cin>>n;
	while(n--)
	{
		int a,b;
		cin>>a>>b;
		cout<<(LL)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
	}
}

博弈论

NIM游戏

略

台阶NIM游戏

#include<bits/stdc++.h>
using namespace std;
int ans,res;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		if(i%2) ans=ans^a;
	}
	if(ans) cout<<"Yes";
	else cout<<"No";
}

集合NIM游戏

略

质数

哥德巴赫猜想

略

分解质因数

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

int main()
{
    int a[100000];
    int c=0;
    int n;
    int z;
    int i;
    cin>>n;
    z=n;
    while(1)
    {
        for(i=2;i<=sqrt(n);i++)
        {
            if(n%i==0)
            {
                a[c]=i;
                c++;
                n/=i;
                break;
            }
        }
        if(i>sqrt(n))
        {
            a[c]=n;
            break;
        }
    }
    cout<<z<<"=";
    for(i=0;i<=c;i++)
    {
        cout<<a[i];
        if(i!=c)
            cout<<"*";
    }
    return 0;
}

筛质数

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

int main()
{
    int a,j;
    cin>>a;
    for(int i=2;i<=a;i++)
    {
         for(j=2;j<=sqrt(i);j++)
            {
                if(i%j==0)
                {

                    break;
                }

            }
            if(j>sqrt(i))
                cout<<i<<" ";
    }
    return 0;
}

试除法求质数

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

int main()
{
    int a,i;
    cin>>a;
    for(i=2;i<=sqrt(a);i++)
    {
        if(a%i==0)
        {
            cout<<"No";
            break;
        }

    }
    if(i>sqrt(a))
        cout<<"Yes";
    return 0;
}

约数

约数个数

#include <iostream>
#include <map>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
int main()
{
    int n;
    cin >>  n;
    map<int, int> h;
    while(n --)
    {
        int x;
        cin >> x;
        for(int i = 2; i <= x / i; i ++)
        {
            while(x % i == 0)
            {
                h[i] ++;
                x /= i;
            }
        }
        if(x > 1) h[x] ++;
    }

    int res = 1;
    for(map<int, int>::iterator it = h.begin(); it != h.end(); it ++)
    {
        res = (LL) res * (it -> second + 1) % mod;
    }
    cout << res << endl;
    return 0;
}

欧拉函数

#include<bits/stdc++.h>
using namespace std;
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int a;
		cin>>a;
		cout<<phi(a)<<endl;
	}
}

最大公约数

#include <iostream>

using namespace std;

int main()
{
    int a,b,r;
    cin>>a>>b;
    r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    cout<<b;
    return 0;
}

快速幂

快速幂求逆元

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % p;
        b = b >> 1;
        a = (LL)a * a % p;
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    while(n--){
        int a, p;
        scanf("%d%d", &a, &p);
        int t =  qmi(a, p-2, p);
        if(a % p) printf("%d\n", t);
        else puts("impossible"); 

    }
    return 0;
}

拓扑排序

有向图的拓扑序列

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int ne[N],e[N],h[N],idx; 
int n,m;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
int q[N];
int din[N];
bool bfs()
{
	int hh=0,tt=-1;
	for(int i=1;i<=n;i++)
	{
		if(din[i]==0) q[++tt]=i;
	}
	while(hh<=tt)
	{
		int u=q[hh++];
		for(int i=h[u];~i;i=ne[i])
		{
			int v=e[i];
			din[v]--;
			if(din[v]==0)
			{
				q[++tt]=v;
			}
		}
	}
	return hh==n;
}
int main()
{
	memset(h,-1,sizeof(h));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		din[b]++;
	}
	if(!bfs())
	{
		cout<<-1;
		return 0;
	}
	for(int i = 0;i<n;i++)
	{
		cout<<q[i]<<' ';
	}
	return 0;
	
}

家谱树

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int ne[N],e[N],h[N],idx;
int n,m;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
int q[N];
int din[N];
bool bfs()
{
	int hh=0,tt=-1;
	for(int i=1;i<=n;i++)
	{
		if(din[i]==0) q[++tt]=i;
	}
	while(hh<=tt)
	{
		int u=q[hh++];
		for(int i=h[u];~i;i=ne[i])
		{
			int v=e[i];
			din[v]--;
			if(din[v]==0)
			{
				q[++tt]=v;
			}
		}
	}
	return hh==n;
}
int main()
{
	memset(h,-1,sizeof(h));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
        int a;
        while(cin>>a&&a!=0)
        {
            add(i,a);
            din[a]++;
        }
	}
	bfs();
	for(int i=0;i<n;i++)
	{
		cout<<q[i]<<' ';
	}
	return 0;

}