算法模板(不定期更新)

bfs最短路模板

最短路+打印路径+记录方向

#include <bits/stdc++.h>
using namespace std;
// bfs路径打印
// https://blog.csdn.net/ryo_218/article/details/88830082?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_paycolumn_v3&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_paycolumn_v3&utm_relevant_index=1
int m, n; //长，高
struct node
{
    int x;
    int y;
    string path;
};
char maze[100][100];
bool visit[100][100];
int dirx[4] = {1, 0, 0, -1}; // D<L<R<U
int diry[4] = {0, -1, 1, 0};
char dir[4] = {'D', 'L', 'R', 'U'};
bool judge(int x, int y, int startx, int starty)
{
    if (x == n && y == m)
        return true;
    else
        return false;
}
void bfs(int startx, int starty)
{
    queue<node> q;
    visit[startx][starty] = 1;
    node p;
    p.x = startx, p.y = starty;
    q.push(p);
    while (!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        string way = q.front().path;
        q.pop();
        if (judge(x, y, startx, starty))
        {
            cout << way;
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            int rempx = x + dirx[i];
            int rempy = y + diry[i];
            string rempway = way + dir[i];
            if (maze[rempx][rempy] == '0' && visit[rempx][rempy] == 0 && rempx <= n && rempx > 0 && rempy <= m && rempy > 0)
            {
                // cout<<"1 ";
                //  cout<<rempway<<endl;
                visit[rempx][rempy] = 1;
                node remp;
                remp.x = rempx, remp.y = rempy, remp.path = rempway;
                // cout << rempway << endl;
                q.push(remp);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        string remp;
        cin >> remp;
        for (int j = 1; j <= m; j++)
        {
            maze[i][j] = remp[j - 1];
        }
    }
    bfs(1, 1);
    return 0;
}
/* 样例
50 30
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
*/

迪杰斯特拉（最短路）

一道模板题：

大循环是n-1次循环
标号从0开始到n-1
题目没说清楚

#include <bits/stdc++.h>
using namespace std;
#define maxn 100
#define INF 10000
int edge[maxn][maxn];
int path[maxn];
bool visit[maxn];
int main()
{
	int n, s;
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		path[i] = INF;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> edge[i][j];
			if (edge[i][j] == 0)
				edge[i][j] = INF;
		}
	}
	for (int i = 0; i < n; i++)
		edge[i][i] = 0;

	path[s] = 0;
	for (int i = 1; i < n; i++)
	{
		int min1 = -1;
		for (int j = 0; j < n; j++)
		{
			if ((min1 == -1 || path[j] < path[min1]) && visit[j] == false)
			{
				min1 = j;
			}
		}
		visit[min1] = true;

		for (int j = 0; j < n; j++)
		{
			path[j] = min(path[min1] + edge[min1][j], path[j]);
			//			cout<<path[j]<<" ";
		}
		//		cout<<endl;
	}


	for (int i = 0; i < n; i++)
	{
		if (i == s)
			continue;
		if (path[i] == INF)
			cout << -1 << " ";
		else
			cout << path[i] << " ";
	}
	cout << endl;
	return 0;
}

另附有最大公因数，最小公倍数求法

#include <bits/stdc++.h>
using namespace std;
// 传送门：https://blog.csdn.net/qq_36306833/article/details/121872050
// 迪杰斯特拉算法(首次使用紫书模板)
 #define INF 0x3f3f3f3f
int edge[2030][2030];
int path[2030];
bool visit[2030];
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}
int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}
int main()
{
    memset(edge, INF, sizeof(edge));
    for (int i = 1; i <= 2021; i++)
        for (int j = i + 1; j <= 2021; j++)
        {
            if (j - i > 21)
                continue;
            int cost = lcm(i, j);
            edge[i][j] = cost;
            edge[j][i] = cost;
        }
    // 算法开始
    memset(visit, 0, sizeof(visit));
    memset(path, INF, sizeof(path));
    path[1] = 0;
    for (int i = 1; i <= 2021; i++)
    {
        int start, min1 = INF;
        for (int j = 1; j <= 2021; j++)
        {
            if (!visit[j] && path[j] <= min1)
            {
                min1 = path[j];
                start = j;
            }
        }
        visit[start] = 1;
        for (int j = 1; j <= 2021; j++)
        {
            path[j] = min(path[j], path[start] + edge[start][j]);
        }
    }
    cout << path[2021];
    return 0;
}

记录并打印路径版本：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int maze[100][100];
int dis[100];
int path[100];
int visit[100];
void print(int tar) // 打印路径
{
    cout << tar;
    int remp = tar;
    while (path[remp])
    {
        cout << " " << path[remp];
        remp = path[remp];
    }
}
int main()
{
    int n, s = 1;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> maze[i][j];
            if (maze[i][j] == 0)
                maze[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; i++)
        maze[i][i] = 0;
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i <= n; i++)
    {
        int min1 = -1;
        for (int j = 1; j <= n; j++)
        {
            if (visit[j] == false && (min1 == -1 || dis[min1] > dis[j]))
            {
                min1 = j;
            }
        }
        visit[min1] = true;
        for (int j = 1; j <= n; j++)
        {
            if (dis[j] > dis[min1] + maze[min1][j])
            {
                path[j] = min1; //记录前驱节点
                dis[j] = dis[min1] + maze[min1][j];
            }
        }
    }
    cout << dis[n] << endl;
    print(n);
    return 0;
}

另外附上打印路径方式(加变式)：

#include <bits/stdc++.h>
using namespace std;
// 传送门：https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840
// 迪杰斯特拉最短路(加变式)+打印路径
#define maxn 600
#define INF 0x3f3f3f3f
int city[maxn];       //每一个城市的救援队
int cost[maxn][maxn]; //维护图
int path[maxn];       //代表从起点到i城市的权值
int pre[maxn];        //记录i城市前驱节点
int num[maxn];        //记录从起点到i城市有最短路有多少种走法
int sum[maxn];        // i城市到起点最短路上能积极的最多救援队
int visit[maxn];      //标记蓝点
int main()
{
    ios::sync_with_stdio(false);
    int n, m, s, d;
    cin >> n >> m >> s >> d;
    memset(cost, INF, sizeof(cost));
    for (int i = 0; i < n; i++)
    {
        cin >> city[i];
        sum[i] = city[i]; //初始化sum数组
        num[i] = 1;       //初始化num数组
        pre[i] = -1;
    }
    for (int i = 1; i <= m; i++)
    {
        int c1, c2, cos;
        cin >> c1 >> c2 >> cos;
        cost[c1][c2] = cost[c2][c1] = cos;
    }
    memset(path, INF, sizeof(path));
    path[s] = 0;
    for (int i = 1; i < n; i++)
    {
        int min1 = INF, start = -1;
        for (int j = 0; j < n; j++)
        {
            if (visit[j] == false && path[j] <= min1)
            {
                start = j;
                min1 = path[j];
            }
        }
        visit[start] = true;
        for (int j = 0; j < n; j++)
        {
            if (path[j] > path[start] + cost[start][j])
            {
                path[j] = path[start] + cost[start][j];
                pre[j] = start; //更新pre前驱
                sum[j] = city[j] + sum[start];
                num[j] = num[start];
            }
            else if (path[j] == path[start] + cost[start][j])
            {
                if (sum[j] < city[j] + sum[start])
                {
                    pre[j] = start;
                    sum[j] = city[j] + sum[start];
                }
                num[j] = num[j] + num[start];
            }
            // path[j] = min(path[start] + cost[start][j], path[j]);
        }
    }
    // cout << "path ";
    // for (int i = 0; i < n; i++)
    //     cout << path[i] << " ";
    // cout << endl;
    // cout << "pre ";
    // for (int i = 0; i < n; i++)
    //     cout << pre[i] << " ";
    // cout << endl;
    // cout << "sum ";
    // for (int i = 0; i < n; i++)
    //     cout << sum[i] << " ";
    // cout << endl;
    // cout << "num ";
    // for (int i = 0; i < n; i++)
    //     cout << num[i] << " ";
    // cout << endl;
    cout << num[d] << " " << sum[d] << endl;
    vector<int> a;
    int end = d;
    while (d != -1)
    {
        a.push_back(d);
        d = pre[d];
    }
    for (int i = a.size() - 1; i >= 0; i--)
    {
        if (i)
            cout << a[i] << " ";
        else
            cout << a[i];
    }

    return 0;
}

堆优化版的迪杰斯特拉

#include <bits/stdc++.h>
using namespace std;
// 迪杰斯特拉(堆优化)
// https://www.luogu.com.cn/problem/P4779#submit
// 链式前项星
const int maxn = 100010, maxn2 = 500010;
int head[maxn], dis[maxn], cnt;
bool visit[maxn];
int n, m, s;
struct edge6
{
    int to, dis, next;
} e[maxn2];
void add(int u, int v, int d)
{
    e[++cnt].dis = d, e[cnt].to = v, e[cnt].next = head[u], head[u] = cnt;
}
struct node
{
    int dis;
    int pos;
    bool operator<(const node &x) const
    {
        return x.dis < dis;
    }
};
priority_queue<node> q;
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; ++i)
        dis[i] = 0x7fffffff;
    for (int i = 1; i <= m; i++)
    {
        register int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        add(u, v, d);
    }
    dis[s] = 0;
    q.push((node){0, s});
    while (!q.empty())
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if (visit[x])
            continue;
        visit[x] = 1;
        for (int i = head[x]; i; i = e[i].next)
        {
            int y = e[i].to;
            if (dis[y] > dis[x] + e[i].dis)
            {
                dis[y] = dis[x] + e[i].dis;
                if (!visit[y])
                {
                    q.push((node){dis[y], y});
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}

蓝书模板

#include <bits/stdc++.h>
using namespace std;
#define maxn 10001000
int n, m, s;
int head[maxn], to[maxn], edge[maxn], Next[maxn], cnt;
int dist[maxn];
bool visit[maxn];
priority_queue<pair<int, int> > q; //前一个数是节点的权值，后一个是终点
// 原本是大根堆，我们将数字取负，变成小根堆
void add(int x, int y, int z)
{
    edge[++cnt] = z, to[cnt] = y, Next[cnt] = head[x], head[x] = cnt;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    // 开始施法
    memset(dist, 0x7f, sizeof(dist));
    memset(visit, 0, sizeof(visit));
    dist[s] = 0;
    q.push(make_pair(0, 1));
    while (q.empty() == false)
    {
        int x = q.top().second;
        q.pop();
        if (visit[x])
            continue;
        visit[x] = true;
        for (int i = head[x]; i; i = Next[i])
        {
            int y = to[i], z = edge[i];
            if (dist[y] > dist[x] + z) 
            {
                dist[y] = dist[x] + z;
                q.push(make_pair(-dist[y], y));//负的！
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dist[i] << " ";
    return 0;
}

弗洛伊德算法

注：假如是普通的最短路寻找，数组的初始化有所不同，要把所有的自回路赋值为0

for(int i=1;i<=num;i++)
	edge[i][i]=0;

#include <bits/stdc++.h>
using namespace std;
// floyed算法(会超时大概一分钟之后得到答案/捂脸）)
// 传送门：https://blog.csdn.net/qq_36306833/article/details/121872050
// 答案：10266837
int edge[2030][2030];
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}
int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}
int main()
{
    memset(edge, 0x3f, sizeof(edge));
    for (int i = 1; i <= 2021; i++)
        for (int j = i + 1; j <= 2021; j++)
        {
            if (j - i > 21)
                continue;
            int cost = lcm(i, j);
            edge[i][j] = cost;
            edge[j][i] = cost;
        }
    for (int k = 1; k <= 2021; k++)
        for (int i = 1; i <= 2021; i++)
            for (int j = 1; j <= 2021; j++)
            {
                edge[i][j] = min(edge[i][k] + edge[k][j], edge[i][j]);
            }
    cout<<edge[1][2021];
    // cout<<lcm(3,5);
    return 0;
}

克鲁斯卡尔算法

原题：繁忙的都市
克鲁斯卡尔+并查集模板

#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.luogu.com.cn/problem/P2330
// 最小生成树+克鲁斯卡尔算法
#define maxn 10000
#define con 100000
int n, m;
struct node
{
    int start;
    int end;
    int cost;
} edge[con];
int father[maxn];
bool cmp(node a, node b)
{
    return a.cost < b.cost;
}
// int link[maxn];
int find(int a)
{
    if (father[a] == a)
        return a;
    else
        return father[a] = find(father[a]);
}
int num_ans, cost_ans;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int remp1, remp2, remp3;
        cin >> remp1 >> remp2 >> remp3;
        edge[i].start = remp1,
        edge[i].end = remp2;
        edge[i].cost = remp3;
    }
    // 好戏登场
    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1; i <= n; i++)
    {
        father[i] = i;
        // link[i] = 1;
    }
    int link = 0;
    for (int i = 1; i <= m; i++)
    {
        int s = edge[i].start;
        int e = edge[i].end;
        if (find(s) != find(e))
        {
            link++;
            num_ans++;
            cost_ans = edge[i].cost; //因为数组按照cost值升序，所以最大值一定是最后一个进入mst的路的权值
            int fa1 = find(s);
            int fa2 = find(e);
            father[fa1] = father[fa2];
            // int sum = link[fa1] + link[fa2];
            // link[fa1] = link[fa2] = sum;
            // if (sum == n)
            //     break;
        }
        if (link == n - 1)
            break;
    }
    cout << n - 1 << " " << cost_ans;//每个边一次连两个点，所以个数一定是n-1个
    return 0;
}

拓扑排序

原题： 最长食物链

#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.luogu.com.cn/problem/P4017
// 题解：https://www.luogu.com.cn/problem/solution/P4017
// 拓扑排序
#define maxn 5000000
#define mod 80112002
int n, m;
vector<int> edge[maxn];
int in[maxn], out[maxn]; //一个是入度，一个是出度
long long ans[maxn];     // ans[i]表示到达第i个结点时，此时拥有的路径总数
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int remp1, remp2;
        cin >> remp1 >> remp2;        // remp2吃remp1
        edge[remp1].push_back(remp2); //被吃掉的后面接捕食者
        in[remp2]++;
        out[remp1]++; //右节点入度+1,左节点出度+1
    }

    for (int i = 1; i <= n; i++)
        if (in[i] == 0)
        {
            q.push(i);
            ans[i] = 1;
        }

    while (!q.empty())
    {
        int front = q.front();
        q.pop();
        for (int i = 0; i < edge[front].size(); i++)
        {
            in[edge[front][i]]--;
            ans[edge[front][i]] = (ans[edge[front][i]] + ans[front]) % mod;
            if (in[edge[front][i]] == 0)
            {
                q.push(edge[front][i]);
            }
        }
    }
    long long ans1 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (out[i] == 0) //只要出度为0，说明是食物链终点（切不可用sort快排取最大！因为出度为0的点不止一个！）
            ans1 += ans[i];
    }
    cout << ans1 % mod;
    return 0;
}

素数筛

埃式筛：

#include <bits/stdc++.h>
using namespace std;
bool prime[1000];
int main()
{
    int num;
    cin>>num;
    for(int i=2;i<=num;i++)
    {
        for(int j=i*i;j<=num;j+=i)//这里有一个小优化，j 从 i * i 而不是从 i + i开始，因为 i*(2~ i-1)在 2~i-1时都已经被筛去，所以从i * i开始。
        prime[j]=1;
    }
    for(int i=2;i<=num;i++)
    {
        if(!prime[i])
        cout<<i<<endl;
    }

    return 0;
}

欧拉筛

#include <bits/stdc++.h>
using namespace std;
//欧拉筛 时间复杂度O(n)
bool judge[1000000] = {1, 1}; // 0，1先筛去
int prime[100000];
int main()
{
    int num;
    cin >> num;
    int count = 0;
    for (int i = 2; i <= num; i++)
    {
        if (!judge[i])
            prime[count++] = i;
        for (int j = 0; j < num; j++)
        {
            if (prime[j] * i > num)
                break; //如果此时已经大于边界，后面的素数肯定也大于边界，所以直接break
            judge[prime[j] * i] = 1;
            if (i % prime[j] == 0)
                break;
// 对于 i%prime[j] == 0 就break的解释 ：当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。
// 举个例子 ：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。
        }
    }
    for(int i=0;i<count;i++)
    cout<<prime[i]<<endl;
    return 0;
}

快速幂

#include <iostream>
using namespace std;
// 给定三个正整数A，B和C，求A ^B  mod C的结果
long long fastpower(long long a, long long b, long long c)
{
	a %= c;
	long long ans = 1;
	while (b)
	{
		a %= c;
		if (b & 1)
			ans = (ans*a) % c;
		b = b / 2;
		a = (a*a)%c;
	}
	return ans;
}
int main()
{
	long long a, b, c;
	cin >> a >> b >> c;
	cout << fastpower(a, b, c) << endl;
	return 0;
}

string查找子串

#include <bits/stdc++.h>
using namespace std;
int main()
{
	string tar;
	cin>>tar;
	string remp;
	cin>>remp;
	if(tar.find(remp)!=string::npos)
	{
		cout<<"YES";
	}
	else
	{
		cout<<"NO";
	}
	
	return 0;
}

STL迭代器

这里以vector为例

vector<int> a;
vector<int>::iterator it;
for (it = a.begin(); it != a.end(); it++)
{
    cout << *it << " ";
}

priority_queue使用和自定义排序

因为自定义排序是重载 < 运算符来实现的，而且优先队列默认是大顶堆，所以定义时
return xxx < xxx 是从大到小排
return xxx > xxx 是从小到大排
是恰好相反的

样例：
1 324 23  21 794 9 90 92 12 29 
输出:
1 9 12 21 23 29 90 92 324 794 
1 9 12 21 23 29 90 92 324 794 

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int cost;
};
struct cmp1
{
    bool operator()(node a, node b)
    {
        return a.cost > b.cost; //从小到大
    }
};
struct cmp2
{
    bool operator()(int a, int b)
    {
        return a > b; //从小到大
    }
};
int main()
{
    priority_queue<node, vector<node>, cmp1> a;
    priority_queue<int, vector<int>, cmp2> b;
    for (int i = 1; i <= 10; i++)
    {
        int remp;
        cin >> remp;
        node t;
        t.cost = remp;
        a.push(t);
        b.push(remp);
    }
    for (int i = 1; i <= 10; i++)
    {
        cout << a.top().cost << " ";
        a.pop();
    }
    cout << endl;
    for (int i = 1; i <= 10; i++)
    {
        cout << b.top() << " ";
        b.pop();
    }
    cout << endl;
    return 0;
}

区间dp

区间dp模板
    memset(dp, 0, sizeof(dp));
    //初始dp数组
    for (int len = 2; len <= n; len++)
    {
        //枚举区间长度
        for (int i = 1; i + len - 1 < n; ++i)
        {                                //枚举区间的起点
            int j = i + len - 1;         //根据起点和长度得出终点
            for (int k = i; k <= j; ++k) //枚举最优分割点
                                         //状态转移方程
        }
    }

#include <bits/stdc++.h>
using namespace std;
// 传送门：https://pintia.cn/problem-sets/1506479836133273600/problems/1506481091213017090
// 区间dp
#define maxn 1010
int dp[maxn][maxn];
int main()
{
    string str;
    getline(cin, str);
    int len = str.length();
    for (int i = 0; i < len; i++)
        dp[i][i] = 1;
    // 注意！一定要先枚举区间长度，再去枚举起点！
    for (int l = 1; l <= len; l++) //枚举长度
    {
        for (int i = 0; i < len; i++) //枚举起点
        {
            int j = l + i;
            if (j >= len)
                continue;
            if (str[i] == str[j])
            {
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                bool judge = true; //下面判断这一段区间是不是回文的
                for (int node1 = i, node2 = j; node1 <= node2; node1++, node2--)
                {
                    if (str[node1] != str[node2])
                    {
                        judge = false;
                        break;
                    }
                }
                if (judge)
                {
                    dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
                }
            }
            else
            {
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
    }
    cout << dp[0][len - 1];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
// 区间dp
// 传送门：http://lx.lanqiao.cn/problem.page?gpid=T2767
// 其实就是求最长回文区间长度，最终结果就是总长减去最长回文区间
int dp[10000][10000];
int main()
{
  string str;
  cin >> str;
  int len = str.length();
  for (int l = 1; l <= len; l++) //枚举区间长度
  {
      for (int i = 0; i + l - 1 < len; i++) //枚举区间起点
      {
          int j = i + l - 1; //区间终点
          if (l == 1)
          {
              dp[i][j] = 1; //长度为一的区间回文长度为1
          }
          else
          {
              dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); //一种是选右不选左，另一种是选左不选右
              if (str[i] == str[j])
              {
                  dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
              }
          }
      }
  }
  cout << len - dp[0][len - 1];
  return 0;
}
/*
区间dp模板
  memset(dp, 0, sizeof(dp));
  //初始dp数组
  for (int len = 2; len <= n; len++)
  {
      //枚举区间长度
      for (int i = 1; i + len - 1 < n; ++i)
      {                                //枚举区间的起点
          int j = i + len - 1;         //根据起点和长度得出终点
          for (int k = i; k <= j; ++k) //枚举最优分割点
                                       //状态转移方程
      }
  }

*/

逆序对

思想就是分治排序，多一行算逆序对的步骤罢了。
逆序对模板题提交oj

#include <iostream>
using namespace std;
long long ans = 0;
int a[10000000], c[10000000];
void mergesort(int a[], int left, int right)
{
	if (left >= right)
		return;
	int mid = (right + left) / 2;
	mergesort(a, left, mid);
	mergesort(a, mid + 1, right);
	int k = 0;
	int i = left, j = mid + 1;
	while (i <= mid && j <= right)
	{
		if (a[i] <= a[j])
			c[k++] = a[i++];
		else
		{
			ans = ans + mid - i + 1;
			c[k++] = a[j++];
		}
	}
	while (j <= right)
		c[k++] = a[j++];
	while (i <= mid)
		c[k++] = a[i++];
	for (i = left, j = 0; i <= right; i++, j++)
		a[i] = c[j];
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	mergesort(a, 0, n - 1);
	cout << ans;
	return 0;
}

(LCA)最近公共祖先

倍增广度搜索

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
// LCA问题
// https://www.luogu.com.cn/problem/P3379
int cnt, n, m, s;
int to[maxn], Next[maxn], head[maxn];
int d[maxn], f[maxn][20];
int t;
queue<int> q;
void add(int s, int e) //加边
{
    to[++cnt] = e, Next[cnt] = head[s], head[s] = cnt;
}
void bfs()
{
    q.push(s);
    d[s] = 1;
    while (q.empty() == false)
    {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = Next[i])
        {
            int tar = to[i];
            if (d[tar])
                continue;
            d[tar] = d[x] + 1;

            f[tar][0] = x;
            for (int j = 1; j <= t; j++)
                f[tar][j] = f[f[tar][j - 1]][j - 1];
            q.push(tar);
        }
    }
}
int lca(int x, int y)
{
    if (d[x] > d[y])
        swap(x, y); //默认x小于y
    for (int i = t; i >= 0; i--)
        if (d[f[y][i]] >= d[x])
            y = f[y][i];
    if (x == y)
        return x;
    for (int i = t; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    t = (int)(log(n) / log(2)) + 1; //层数
    for (int i = 1; i < n; i++)
    {
        int s, e;
        cin >> s >> e;
        add(s, e);
        add(e, s);
    }
    bfs();
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b)<<endl;
    }
    return 0;
}

负环+SPFA

#include <bits/stdc++.h>
using namespace std;
// 判断负环https://www.luogu.com.cn/problem/P3385
#define maxn 1000000
int T, n, m;
int to[maxn], edge[maxn], head[maxn], Next[maxn], cnt;
int dist[maxn];
bool visit[maxn];
int num[maxn]; //判断负环
queue<int> q;
void add(int x, int y, int z)
{
    to[++cnt] = y, edge[cnt] = z, Next[cnt] = head[x], head[x] = cnt;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        bool flag = false;
        memset(visit, 0, sizeof(visit));
        memset(dist, 0x3f, sizeof(dist));
        memset(num, 0, sizeof(num));
        memset(head, 0, sizeof(head));
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            if (w >= 0)
            {
                add(u, v, w);
                add(v, u, w);
            }
            if (w < 0)
            {
                add(u, v, w);
            }
        }
        dist[1] = 0, visit[1] = 1;
        q.push(1);
        while (q.empty() == false)
        {
            int x = q.front();
            q.pop();
            visit[x] = 0;
            for (int i = head[x]; i; i = Next[i])
            {
                int y = to[i], z = edge[i];
                if (dist[y] > dist[x] + z)
                {
                    dist[y] = dist[x] + z;
                    num[y] = num[x] + 1; //这一行和下面的num判断去掉就是SPFA了
                    if (num[y] >= n)
                    {
                        flag = true;
                        break;
                    }
                    if (!visit[y])
                        q.push(y), visit[y] = true;
                }
            }
        }
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

二分图最大匹配

匈牙利算法

#include <bits/stdc++.h>
using namespace std;
// 传送门;https://www.luogu.com.cn/problem/P3386
// 匈牙利算法
#define maxn 10000100
int n, m, e, ans;
bool f[1000][1000];
int to[maxn], Next[maxn], head[maxn], cnt;
int match[maxn];
bool visit[maxn];

void add(int x, int y)
{
    to[++cnt] = y, Next[cnt] = head[x], head[x] = cnt;
}
bool dfs(int x)
{
    for (int i = head[x]; i; i = Next[i])
    {
        int y = to[i];
        if (visit[y] == false)
        {
            visit[y] = true;
            if (!match[y] || dfs(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++)
    {
        int u, v;
        cin >> u >> v;
        if (u <= n && v <= m)
            add(u, v);
    }
    ans = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(visit, 0, sizeof(visit));
        if (dfs(i))
            ans++;
    }
    cout << ans << endl;
    return 0;
}