ACM刷题之路（十六）Acm程序设计竞赛自制模板

╰+攻爆jí腚メ 2024-02-19 19:52 69阅读 0赞

**2020年2月更新：算法模板V2.1版**

[下载地址][Link 1]

--------------------

**前言**

本模板是我在备战省赛的时光中，把复习过的和新学的算法中比较常用的代码、思路，整合成了模板，供以后的ACM竞赛直接使用，因为时间匆忙、水平有限，若有不足之处，欢迎大佬提出。本版本为V1.0版，会不定期更新。

以下所有代码都是我个人手敲，并且通过HDU、POJ等知名OJ上做题实践验证过的结果，是我两个月的成果。

水平有限，代码比较累赘，以后有机会进一步减少少考的算法，增加比较常用的算法合集。

希望能够抛砖引玉，如有意见，欢迎留言，或E-mail ypacmzwz@163.com

**目录**

前言..................................................................................................................................................................... 1

目录..................................................................................................................................................................... 1

常用思路.............................................................................................................................................................. 1

常见递推公式....................................................................................................................................................... 1

函数库—algorithm................................................................................................................................................ 1

函数库—cstring.................................................................................................................................................... 2

函数库—cmath..................................................................................................................................................... 2

快速幂................................................................................................................................................................. 3

回文数................................................................................................................................................................. 3

二分..................................................................................................................................................................... 3

尺取法................................................................................................................................................................. 3

辗转相除法.......................................................................................................................................................... 3

水仙花数.............................................................................................................................................................. 4

并查集................................................................................................................................................................. 4

分割问题.............................................................................................................................................................. 4

日期差公式.......................................................................................................................................................... 4

组合大小计算....................................................................................................................................................... 4

最大连续子序列和................................................................................................................................................ 5

LIS(最长上升子序列)............................................................................................................................................. 5

LCS(最长公共子序列)............................................................................................................................................ 6

大数a+b............................................................................................................................................................... 6

求第k个排列(阶乘法)........................................................................................................................................... 7

最短路1. Dijkstra算法.......................................................................................................................................... 8

最短路2. Floyd算法.............................................................................................................................................. 9

最小生成树prim算法.......................................................................................................................................... 10

凸包................................................................................................................................................................... 11

深搜dfs.............................................................................................................................................................. 13

广搜bfs.............................................................................................................................................................. 13

母函数或多重背包.............................................................................................................................................. 13

01背包............................................................................................................................................................... 14

完全背包............................................................................................................................................................ 14

多重背包............................................................................................................................................................ 14

状压DP.............................................................................................................................................................. 15

线段树................................................................................................................................................................ 16

**常用思路**

1.计算a到b之间有多少符合条件的数，可打表后二分找a和b的位置后相减

例:

scanf("%lld%lld", &n, &m);
    i = lower_bound(s1.begin(), s1.end(), n) - s1.begin();
    j = upper_bound(s1.begin(), s1.end(), m) - s1.begin();
    printf("%lld\n", j - i);

2.前缀和思想，不要直接暴力模拟。

3.(x1,y1)(x1,y1)(x2,y2)(x2,y2)两点连线之间的整点数是gcd(|x1−x2|,|y1−y2|)+1

4. 满足在\[2,n\]范围内有多少个数是非次方数（也就是不是x^k(k>1)这样的）

答案：![20190418172512582.png][]

**常见递推公式**

f(n)=4\*f(n-2)-f(n-4)

f（n）=f（n-1）+6×（i-1）

f(n)=f(n-4)+f(n-2)+f(n-1)（n>4）

f\[i\]=f\[i-1\]+f\[i-2\]\*4;

f(n)=f(n-2)+f(n-1)，n>3。

F\[i\] = F\[i-1\] + 2 \* F\[i-2\];

a\[n\]\[m\] = a\[n-1\]\[m\] +a\[n\]\[m-1\]

**函数库—algorithm**

//————————algorithm————————
    	int a[] = { 1, 3, 5, 7, 9, 11, 13 };
    	lower_bound(a, a + 7, 7);//返回第一个大于等于7的地址
    	upper_bound(a, a + 7, 7);//返回第一个小于等于7的地址
    	binary_search(a, a + 7, 8);//若a到a+7有8，返回true 否则返回false
    	reverse(a, a + 7);//反转a到a+7的元素
    	fill(a, a + 7, 4);//填充函数，把a到a+7全部填充为4
    	int b[11] = { 1, 2, 3, 4 };
    	copy_backward(a, a + 7, b + 7);//把a数组复制到b，首地址，尾地址，复制后数组的尾地址
    	next_permutation(b, b + 4);//b数组的下一个排列
    	prev_permutation(b, b + 4);//b数组的上一个排列
    	replace(b, b + 4, 3, 5);//把b到b+4中所有3替换成5
    	stable_sort(a, a + 7, cmp);//按照cmp规则稳定排序a到a+7
    	unique(a, a + 7);//去重，返回去重后数组的尾地址
    	printf("%d\n", *max_element(a, a + 6));//返回序列a到a+6的最大元素地址
    	//————————algorithm————————

**函数库—cstring**

//————————cstring————————
            char a[200] = "hello world";
    	char b[] = "hello acm";
    	cout << a << endl << b << endl;
    	memset(a, 0, sizeof(a));//初始化 只能0 -1
    	int len = strlen(a);//返回a的长度  到'\0'就算结束
    	strcpy(a, b);//把b赋值给a 覆盖掉
    	memcpy(a, b, 8);//把b赋值给a 覆盖掉8个长度
    	strcat(a, b);//把b连接到a后面
    	strncat(a, b, 3);//把b的最多3个字符连接到a后面
    	strcmp(a, b);//a>b 返回正数,a<b返回负数，一样返回0
    	strncmp(a, b, 7);//比较a和b的前7位字符 返回规则同上
    	int xiabiao = strchr(a, 'l') - a;//返回a中找字符l出现的首地址 没有返回NULL
    	int xiabiao2 = (char*)memchr(a, 'l', 7) - a;//返回a的前7个字符中找字符l出现的首地址 没有返回NULL
    	strspn(a, b);//比较a和b 从第一位开始比较返回从头数相等的长度
    	strstr(a, b)-a;//返回b在a首次出现的地址 
    //————————cstring————————

**函数库—cmath**

int a = 1, b = -2, c = 3, d = 4;
    	double e = 1.1, f = 8.36, g = 2.2, h =3.4;
    	/*————————<cmath>  部分————————*/
    	e = sqrt(f);//平方根函数 返回根号f
    	e = cbrt(f);//立方根函数 返回三次根号f
    	e = pow(f, g); //幂函数 返回f的g次方
    	e = floor(f);//向下取整 返回f的向下取整的整数
    	e = ceil(f);//向上取整 返回f的向上取整的整数
    	a = abs(b);//int类型 返回b的绝对值
    	e = fabs(f);//double类型 返回f的绝对值
    	e = fmod(f, g);//double类型 返回f除以g的余数
    	e = modf(2.36, &f);//把2.36的整数部分赋值给f(有&) 把小数返回给e
    	e = frexp(1024.0, &a);//把1024.8转化为0.5*2^11;0.5返回 11赋值给a，返回的小数范围[0.5,1)
    	e = ldexp(1.0, 3);//返回1.0 *(2^3) 
    	e = exp(3);//返回e的3次方     exp(1)就是e的值  acos(-1)就是pai的值
    	f = log(666.0);//返回log e (666.0)   以e为底数
    	f = log10(666.0);//返回log 10 (666.0)   以10为底数
    	f = log10(8) / log10(2);// 计算log 2 (8) 运用换底公式
    	f = acos(-1);//返回以弧度表示的 -1 的反余弦
    	f = asin(-1);//返回以弧度表示的 -1 的反正弦
    	f = atan(-1);//返回以弧度表示的 -1 的反正切
    	f = atan2(1, 2); //返回以弧度表示的 1/2 的反正切。1和2的值的符号决定了正确的象限。
    	f = cos(1.1);//返回弧度为1.1的余弦
    	f = sin(1.1);//返回弧度为1.1的正弦
    	f = tan(1.1);//返回弧度为1.1的正切
    	f = cosh(1.1);//返回弧度为1.1的双曲余弦
    	f = sinh(1.1);//返回弧度为1.1的双曲正弦
    	f = tanh(1.1);//返回弧度为1.1的双曲正切
    	f = hypot(3, 4);//返回以3和4为直角边的三角形斜边长
    	/*————————<cmath>  部分————————*/

**快速幂**

int poww(int n, int m)
    {
    	int ans = 1;
    	while (m > 0)
    	{
    		if (m & 1) ans *= n;
    		n *= n;
    		m /= 2;
    	}
    	return ans;
    }

**回文数**

bool huiwen(int n)
    {//判断一个数字是否回文
    	int temp = n, t = 0;
    	while (temp)
    	{
    		t = t * 10 + temp % 10;
    		temp /= 10;
    	}
    	return t == n;
    }

**尺取法**

int s=0,e=0,sum=a[0];
    	int chang=0,min=1000010;
    	while(e<n)
    	{//s到e的一把尺子
    		if(sum<m)//如果sum小于预想结果
    		{
    			e++;//尺子后面边长
    			sum+=a[e];
    		}
    		else if(sum>=m)//若达到结果
    		{
    			if(e-s+1<min) 
    			{
    				min=e-s+1;//记录最小值
    			}
    			sum-=a[s];
    			s++;   //尺子前面缩短
    		}
    		
    	}
    	if(min!=1000010) //若有满足答案
    		printf("%d\n",min);
    	else 
    		printf("0\n");

**二分**

double s=开始,e=结尾,mid;
    	while(1)
    	{
    		mid=(s+e)/2.0;
    		if(满足条件)
    		{//或者while里面写(左<=右)
    			break;
    		}
    		else if(结果小于预想答案)
    		{
    			s=mid（按照情况+1或者不加）;
    		}
    		else
    		{
    			e=mid（按照情况-1或者不加）;
    		}
    	}
    	printf("%.4lf\n",mid);

**辗转相除法**

int gcd(int x, int y)  //547ms
    {
    	int z;
    	while (y > 0)
    	{
    		z = x%y;
    		x = y;
    		y = z;
    	}
    	return x;
    }
    int gcd2(int a, int b)  //544ms
    {
    	return b == 0 ? a : gcd(b, a%b);
    }

**水仙花数**

三位的水仙花数共有4个：153，370，371，407；
    四位的四叶玫瑰数共有3个：1634，8208，9474；
    五位的五角星数共有3个：54748，92727，93084；
    六位的六合数只有1个：548834；
    七位的北斗七星数共有4个：1741725，4210818，9800817，9926315；
    八位的八仙数共有3个：24678050，24678051，88593477

**并查集**

int a[10005];
    int find(int x)//查找自己的老大
    {
    	if (a[x] == x) return x;
    	else return a[x] = find(a[x]);
    }
    void mix(int x, int y)//合并
    {
    	if (find(x) != find(y))
    	{
    		a[find(x)] = find(y);
    	}
    }
    主函数：
    1.	for (i = 1; i <= 10000; i++)//初始化自己是自己的老大
    		a[i] = i;
    2. for (i = 1; i <= max; i++)//合并后需路径压缩
    	{
    		find(i);
    	}
    3. if (find(e) == find(r))			puts("Y");
    		else	puts("N");//如果老大一样，就是一个集合

**日期差公式**

int day_diff(int year1, int month1, int day1, int year2, int month2, int day2)
    {//年月日  年月日  日期差公式 求相差几天
    	int y2, m2, d2, y1, m1, d1;
    	m1 = (month1 + 9) % 12;
    	y1 = year1 - m1 / 10;
    	d1 = 365 * y1 + y1 / 4 - y1 / 100 + y1 / 400 + (m1 * 306 + 5) / 10 + (day1 - 1);
    
    	m2 = (month2 + 9) % 12;
    	y2 = year2 - m2 / 10;
    	d2 = 365 * y2 + y2 / 4 - y2 / 100 + y2 / 400 + (m2 * 306 + 5) / 10 + (day2 - 1);
    	return (d2 - d1);
    }

**组合大小计算**

#include<iostream>
    #include<time.h>
    using namespace std;
    double zuhe(int n, int m)
    {
    	double sum = 1;
    	int i;
    	for (i = 0; i < n; i++)
    	{
    		if (n - i>m) sum *= n - i;
    		if (n - m - i > 1) sum /= n - m - i;//顺带抵消，防止爆double
    	}
    	return sum;
    }
    
    double zuhe2(int n,int r)
    {
    	double s = 1;
    	int i;
    	for (i = 1; i <= r; i++)
    		s = s*(n - i + 1) / i;
    	return s;
    }
    
    int main()
    {
    	int n, m;
    	while (cin >> n >> m)
    	{
    		cout << zuhe(n, m) << endl;//506 ms
    		cout << zuhe2(n, m) << endl;//866 ms
    	}
    	return 0;
    }

**分割问题**

直线分割平面: 任意两条直线都要相交，且任意三条直线不能有同一个交点
    即f(n) = f(n - 1) + n     或  f(n) = 1/2 * (n*n + n)  + 1
    平面分空间: F(n) = (n * n * n + 5 * n + 6) / 6;
    另: 平方项的通项公式 1^2+2^2+3^2+……+n^2=n(n+1)(2n+1)/6
    立方差公式: n^3-(n-1)^3 = =2*n^2+(n-1)^2-n

**最大连续子序列和**

int a[100003];
    int longziliehe(int n)
    {
    	int maxsum = 0;
    	int thissum = 0;
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &a[i]);
    		thissum += a[i];
    		if (thissum >= maxsum) maxsum = thissum;
    		if (thissum < 0) thissum = 0;
    	}
    	return maxsum;
    }

**LIS(最长上升子序列)**

1.o(n*logn)
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int a[500020];//初始数组
    int dp[500020];//最后的LIS数组
    int lis(int n)
    {
    	memset(dp, 0, sizeof(dp));
    	dp[1] = a[1];
    	int len = 1;
    	for (int i = 2; i <= n; i++)
    	{
    		int wei = lower_bound(dp + 1, dp + 1 + len, a[i]) - dp;
    		if (wei > len)
    		{
    			len++;
    			dp[wei] = a[i];
    		}
    		else
    		{
    			dp[wei] = a[i];
    		}
    	}
    	return len;
    }
    int main()
    {
    	int n, i, j;
    cout << "请输入需要求LIS的数组长度" << endl;
    cin >> n;
    cout << "数组长度输入完毕，请依次输入数组元素" << endl;
    	for (i = 1; i <= n; i++)
    	{
    		scanf("%d", &a[i]);
    	}
    	int max = lis(n);
    	cout << "该数组的LIS数组长度为" << max << endl;
    	cout << "该数组的最优LIS数组为" << endl;
    	for (i = 1; i <= max; i++)
    	{
    		cout << dp[i] << " ";
    	}
    	cout << endl;
    	return 0;
    }
    
    2.	o(n^2)
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int a[500020];
    int dp[500020];
    int lis(int n)
    {
    	memset(dp, 0, sizeof(dp));
    	dp[1] = 1;
    	int max = 1;
    	for (int i = 2; i <= n; i++)
    	{
    		for (int j = 1; j < i; j++)
    		{
    			if (a[j]<a[i] && dp[j] + 1> dp[i])
    			{
    				dp[i] = dp[j] + 1;
    				if (dp[i] > max) max = dp[i];
    			}
    		}
    	}
    	return max;
    }
    int main()
    {
    	int n, i, j, k;
    	while (cin >> n)
    	{
    		for (i = 1; i <= n; i++)
    		{
    			scanf("%d", &a[i]);
    		}
    		int max = lis(n);
    		cout << max << endl;
    	}
    	return 0;
    }

**LCS(最长公共子序列)**

1.	滚动数组
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int map[2][10005];
    string str1, str2;
    int len1, len2;
    void LCS(int x, int y)
    {
    	for (int i = 0; i <= x; i++)
    	{
    		for (int j = 0; j <= y + 1; j++)
    		{
    			if (i == 0 || j == 0) 
    { map[i % 2][j] = 0; continue; }
    			if (str1[i - 1] == str2[j - 1])
    			{
    			map[i % 2][j] = map[(i - 1) % 2][j - 1] + 1;
    			}
    			else
    			{
    map[i % 2][j] = max(map[(i - 1) % 2][j], map[i % 2][j - 1]);
    			}
    		}
    	}
    }
    int main()
    {
    	while (cin >> str1 >> str2)
    	{
    		len1 = str1.length();
    		len2 = str2.length();
    		LCS(len1, len2);
    		printf("%d\n", map[len1 % 2][len2]);
    	}
    	return 0;
    }
    2.o(n+m)
    #include<cstdio>
    #include<string>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int map[10005][10005];
    string str1, str2;
    int len1, len2;
    int max(int x, int y)
    {
    	if (x > y) return x;
    	return y;
    }
    
    
    int main()
    {
    	while (cin >> str1 >> str2)
    	{
    		len1 = str1.length() - 1;
    		len2 = str2.length() - 1;
    		for (int i = 0; i <= len1 + 1; i++)
    		{
    			for (int j = 0; j <= len2 + 1; j++)
    			{
    				if (i == 0 || j == 0)
    				{ 
    					map[i][j] = 0;
    					continue; 
    				}
    				if (str1[i - 1] == str2[j - 1])
    				{
    			map[i][j] = map[i - 1][j - 1] + 1;
    				}
    				else
    				{
    map[i][j] = max(map[i - 1][j], map[i][j - 1]);
    				}
    			}
    		}
    	printf("%d\n", map[len1 + 1][len2 + 1]);
    	}
    	return 0;
    }

**大数a+b**

#include<iostream>
    #include<string.h>
    using namespace std;
    int i, a[1000], b[1000];
    char s1[1000], s2[1000];
    int sum(char *s1, char *s2)
    {
    int len, len1 = strlen(s1), len2 = strlen(s2), t;
    memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
    	for (i = 0; i<len1; i++)   
     //字符转换成数字，倒序存放，方便求和
    		a[i] = s1[len1 - 1 - i] - '0';
    	for (i = 0; i<len2; i++)
    		b[i] = s2[len2 - 1 - i] - '0';
    	len = len1>len2 ? len1 : len2;
    	for (t = i = 0; i <= len; i++)
    	{
    		a[i] += (b[i] + t);   
     //把数组b里的数字加到a数组里  
    		t = a[i] / 10;    //t为进位数  
    		a[i] %= 10;
    	}
    	return a[len] == 0 ? len - 1 : len;//判断求和之后的长度的len还是len-1   
    }
    int main()
    {
    	int i;
    	while (~scanf("%s%s",s1,s2))
    	{
    		int len = sum(s1, s2);
    		for (i = len; i >= 0; i--)
    		{
    			printf("%d", a[i]);
    		}
    		puts("");
    	}
    	return 0;
    }

import java.math.BigInteger;
    import java.util.Scanner;
    public class Main 
    {
    	public static void main(String args[])
    	{
    		Scanner in = new Scanner(System.in);
    		while(in.hasNext())
    		{
    			BigInteger a= in.nextBigInteger();
    			BigInteger b= in.nextBigInteger();
    			System.out.println(a + " + " + b + " = " + a.add(b));
    		}
    	}
    }

**求第k个排列(阶乘法)**

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    vector<int>a;
    
    
    
    long long jc(int x)//阶乘的递归算法
    {
    	if (x < 2) return 1;
    	return x*jc(x - 1);
    }
    
    
    
    
    void shengcheng(int n)//生成1到n的排列，在a数组中
    {
    	a.clear();
    	for (int i = 0; i < n; i++)
    		a.push_back(i + 1);
    }
    
    
    
    int maxjc(int n,int k)
    //求小于等于k的最大的阶乘数 n为排列最大阶乘
    {
    	for (int i = n; i>0; i--)
    	{
    		if (jc(i) <= k) return i;
    	}
    	return -1;
    }
    
    void makepailie(int n,int k)//求第k个排列
    {
    	int kk = k;//用于后面输出
    	k--;//这里需要减去一
    	int t = maxjc(n, k);
    //求出小于等于k的最大的阶乘数
    	queue<int>q;
    	for (int i = 1; i < n - t; i++)
    	{
    		q.push(i);
    		a.erase(a.begin());
    	}
    	while (t>=0)
    	{
    		int zheng = k / jc(t);
    		int yu = k % jc(t);
    		q.push(a[zheng]);
    		a.erase(a.begin() + zheng);
    		k %= jc(t);
    		t--;
    	}
    	cout << " 1 到";
    	printf("%2d ", n);//控制格式
    	cout << "的第";
    	printf(" %2d ", kk);//控制格式
    		cout<< "个排列为 : ";
    	while (!q.empty())
    	{
    		cout << "  " << q.front();
    		q.pop();
    	}
    	cout << endl;
    }
    
    int main()
    {
    	int n, i, k;
    	//------------------------------------------------
    	//功能1： 输入n ，输出 1到n 的全排列
    	while (cin >> n)
    	{
    		for (i = 1; i <= jc(n); i++)
    		{
    			shengcheng(n);
    			makepailie(n, i);
    		}
    	}
    	//------------------------------------------------
    	//功能2： 实现1到n 的第K个排列 
    	while (cin >> n >> k)
    	{
    		shengcheng(n);
    		makepailie(n, k);
    	}
    	//------------------------------------------------
    	return 0;
    }

**最短路1. Dijkstra算法**

hdu 2544 最短路贪心手法  先把除1以外的距离初始化为无穷大
    先从1开始 利用1可以连接到其他顶点的边 更新距离数组d[]，把1确定下来  1到1距离为0已固定
    在取非固定点的最小值 同样利用这个点可以连接到其他顶点的边 更新距离数组d[]...... 以此类推
    这样循环n次  即可求出1到n的最短路径  如果不连通  当某一个find函数返回-1  即可判断该图不连通
    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    int n, m;
    bool b[102];//判断最短距离是否确定， 已确定为true 否则为假
    int d[102];//保存1到各个节点的距离 若b数组相应值为true 则必为最短路 否则为临时最短路
    #define inf 10000000
    int find()//找到所有距离的最小值
    {
    	int i, j = -1, min = inf;
    	for (i = 1; i <= n; i++)
    	{
    		if (b[i]==false && d[i] < min)
    		{
    			j = i;
    			min = d[i];
    		}
    	}
    	return j;
    }
    int main()
    {
    	int i, j;
    	int q, w, e;
    	while (cin >> n >> m)
    //输入点数n  和 边数 m
    	{
    		vector<pair<int, int> >v[102];
    //用vector + pair 模拟二维数组 即三个变量的对应关系
    		if (n == 0 && m == 0) break;
    		while (m--)
    		{
    			pair<int, int>p;//pair为辅助容器
    			scanf("%d%d%d", &q, &w, &e);
    			p.first = w;
    			p.second = e;
    			v[q].push_back(p);
    // q 到 w 的 边长 为 e
    			p.first = q;
    			v[w].push_back(p);
    // w 到 q 的 边长 为 e
    		}
    		fill(b, b + 102, false); 
    //初始化函数  节点全部初始化为未访问
    		fill(d, d + 102, inf);
    //距离全部初始化为无穷大
    		d[1] = 0; // 1到1的距离为0
    		for (i = 1; i <= n; i++)
    		{
    			j = find();
    			b[j] = true;
    for (vector<pair<int, int> >::iterator it = v[j].begin(); it != v[j].end(); it++)
    {
    //此循环为对j到其他结点遍历  更新最短边
    if (d[it->first] > d[j] + it->second)//如果可以通过中间点使路变的更短
    {
    d[it->first] = d[j] + it->second;
    }
    	}
    }
    		cout << d[n] << endl;
    //输出1到n的最短距离 
    	}
    	return 0;
    }
    
    测试数据
    9 15
    1 2 6
    1 3 3
    1 4 1
    2 3 2
    3 4 2
    4 5 6
    2 5 1
    4 6 10
    5 6 4
    5 7 3
    5 9 6
    5 8 2
    8 9 3
    6 7 2
    7 9 4
    答案：11

**最短路2. Floyd算法**

hdu 2544 最短路 Floyd算法 总结
    
    状态  ：Accepted  31MS  1848K
    基本思想：点A到点B无非是A直接到B 和 A通过若干个点再到B 这两种可能
    对于每一个点 都当一遍中间点 判断a[j][i] + a[i][k] < a[j][k]
    最后的a数组即可表示最短路径  a[i][j]代表i到j的最短路径 
    
    
    时间复杂度为o(n^3) 
    
    
    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    int n, m;
    int a[105][105];
    //a数组直接保存每个点之间的最短距离
    #define inf 10000000
    
    
    
    
    
    
    
    
    
    
    
    
    
    int main()
    {
    	int i, j, k;
    	int q, w, e;
    	while (cin >> n >> m)
    //输入点数n  和 边数 m
    	{
    		if (n == 0 && m == 0) break;
    		for (i = 0; i < 105; i++)
     //全部初始化为无穷大
    		{
    			for (j = 0; j < 105; j++)
    			{
    				a[i][j] = inf;
    			}
    		}
    		while (m--)
    		{
    			scanf("%d%d%d", &q, &w, &e);
    			a[q][w] = e;//q到w的距离为e
    			a[w][q] = e;//w到q的距离为e
    		}
    //Floyd算法 o(n^3) 暴力循环判断点i是否可以作为中间点
    		for (i = 1; i <= n; i++)
    		{
    			for (j = 1; j <= n; j++)
    			{
    				for (k = 1; k <= n; k++)
    				{
    if (a[j][i] + a[i][k] < a[j][k])
    //如果i当中间点可以缩短路径长度
    {
    	a[j][k] = a[j][i] + a[i][k];
    }
    				}
    			}
    		}
    		cout << a[1][n] << endl;
    //输出1到n的最短距离 
    	}
    	return 0;
    }

**最小生成树prim算法**

/*
    算法思路：
    首先就是从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，
    权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，
    并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，
    然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：
    （V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：
    {a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合U。
    2018/12/6   最小生成树   Prim算法
    */
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int inf = 10000000;
    const int N = 1002;
    int G[N][N];//G数组 保存 边长
    int d[N];
    //d数组  保存所有点离树的最短距离
    int n, m;
    bool vis[N];
     // vis数组 保存 判断这个点是否放入树中 
    int prim()
    {
    	fill(d, d + N, inf);//初始化无穷大
    	d[1] = 0;
    	int ans = 0;//初始化答案为0
    
    
    
    
    
    	for (int i = 1; i <= n; i++)
    //i层循环 找所有连通到的边中最短的
    	{
    		int u = -1;//找单次的最短边
    		int min = inf;
    		for (int j = 1; j <= n; j++)
    		{
    			if (vis[j] == false && d[j]<min)//遍历求出 没有进入树的节点 离树的最短距离
    			{
    				u = j;
    				min = d[j];
    			}
    		}
    		if (u == -1)//如果所有边都无穷大，说明不连通，就返回错误
    			return -1;
    		vis[u] = true;//该点入树
    		ans += d[u];//距离总和加上U点离树的距离
    		for (int v = 1; v <= n; v++)
    		{//这里是更新没有入树的节点离树的最短距离
    			if (vis[v] == false && G[u][v] != inf&&G[u][v]<d[v])
    				d[v] = G[u][v];
    		}
    	}
    	return ans;
    }
    int main()
    {
    	int u, v, c;
    	cin >> n >> m;
    	fill(G[0], G[0] + N*N, inf);
    	for (int i = 1; i <= m; i++)
    	{
    		cin >> u >> v >> c;
    		G[u][v] = G[v][u] = c;
    	}
    	int ans = prim();
    	if (ans == -1)//如果不连通
    		cout << "-1" << endl;
    	else
    		cout << ans << endl;
    	return 0;
    }

**凸包**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #define PI 3.1415926535
    using namespace std;
    struct node
    {
    	int x, y;
    };
    node vex[1000];//存入的所有的点
    node stackk[1000];//凸包中所有的点
    int xx, yy;
    bool cmp1(node a, node b)//排序找第一个点
    {
    	if (a.y == b.y)
    		return a.x<b.x;
    	else
    		return a.y<b.y;
    }
    int cross(node a, node b, node c)//计算叉积
    {
    	return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
    }
    double dis(node a, node b)//计算距离
    {
    	return sqrt((a.x - b.x)*(a.x - b.x)*1.0 + (a.y - b.y)*(a.y - b.y));
    }
    bool cmp2(node a, node b)//极角排序另一种方法，速度快
    {
    	if (atan2(a.y - yy, a.x - xx) != atan2(b.y - yy, b.x - xx))
    		return (atan2(a.y - yy, a.x - xx))<(atan2(b.y - yy, b.x - xx));
    	return a.x<b.x;
    }
    bool cmp(node a, node b)//极角排序
    {
    	int m = cross(vex[0], a, b);
    	if (m>0)
    		return 1;
    	else if (m == 0 && dis(vex[0], a) - dis(vex[0], b) <= 0)
    		return 1;
    	else return 0;
    }
    int main()
    {
    	int t, L;
    	while (~scanf("%d", &t), t)//总共t个点
    	{
    		int i;
    		for (i = 0; i<t; i++)
    		{
    			scanf("%d%d", &vex[i].x, &vex[i].y);//输入每个点的x和y坐标
    		}
    		if (t == 1)//如果只有一个点 凸包周长为0
    			printf("%.2f\n", 0.00);
    		else if (t == 2)
    			printf("%.2f\n", dis(vex[0], vex[1]));//如果只有两个点 周长是两点距离
    		else
    		{
    			memset(stackk, 0, sizeof(stackk));
    			sort(vex, vex + t, cmp1);//排序找第一个点
    			stackk[0] = vex[0];//用数组模拟栈
    			xx = stackk[0].x;
    			yy = stackk[0].y;
    			sort(vex + 1, vex + t, cmp2);//极角排序
    			stackk[1] = vex[1];//将凸包中的第两个点存入凸包的结构体中
    			int top = 1;//最后凸包中拥有点的个数
    			for (i = 2; i<t; i++)
    			{
    				while (i >= 1 && cross(stackk[top - 1], stackk[top], vex[i])<0)
    					//i>=1防止越界  如果在右边 把栈顶元素出栈
    					top--;
    				stackk[++top] = vex[i];//控制<0或<=0可以控制重点，共线的，具体视题目而定。
    			}
    			double s = 0;
    			for (i = 1; i <= top; i++)   //计算凸包的周长
    				s += dis(stackk[i - 1], stackk[i]);
    			s += dis(stackk[top], vex[0]);//最后一个点和第一个点之间的距离
    			printf("%.2lf\n", s);
    		}
    	}
    }

**深搜dfs**

void dfs(ll shu, int fei0, int changdu)//在搜索时需变化的量
    {
    	//满足条件返回
    	//越界返回 
    	//明显不符合条件返回 如距离奇偶性
    	//已经找到目标  返回
    	for (int i = 1; i <= 9; i++)
    	{
    		dfs(shu * 10 + i, fei0 + 1, changdu + 1);//继续深搜下去
    	}
    }

**广搜bfs**

void bfs(int x)
    {
    	queue<int>q1;//1.先创建队列
    	q1.push(x);//2.放入初始条件
    	while (!q1.empty())//3.开始循环广搜
    	{
    		int t = q1.front();
    		q1.pop();//4.顶部删掉
    		for (vector<int>::iterator it = v[t].begin(); it != v[t].end(); it++)
    		{//5.把顶部能牵连到的元素压入队列
    			if (a[*it] == false)
    				q1.push(*it);
    		}
    	}//6.全部循环结束后，如果需要返回值就返回
    }

**母函数或多重背包**

#include<iostream>
    #include<cstring>
    using namespace std;
    struct node
    {
    	int fen, num;
    };
    int dp[41];
    int main()
    {
    	int T;
    	scanf("%d", &T);
    	while (T--)
    	{
    		node a[10];
    		memset(dp, 0, sizeof(dp));
    		int n,  m;
    		scanf("%d%d", &m, &n);
    		int i, j, w;
    		for (i = 0; i < n; i++)
    			scanf("%d%d", &a[i].fen, &a[i].num);//输入每种物品的价值 和 物品数量
    		dp[0] = 1;//初始化dp数组
    		for (i = 0; i < n; i++)//枚举物品种类
    		{
    			for (j = m; j >= a[i].fen; j--)//枚举背包容量，01背包，要从大到小推，不然会重复加
    			{
    				for (w = 1; w <= a[i].num; w++)
    		//枚举这个物品的个数，如果当前枚举到的价值能放入此物品的话，就加上之前的价值
    				{
    					if (j >= a[i].fen*w)
    		//a[i].fen*w是w个物品能产生的价值，然后j-a[i].fen*w就是去掉a[i].fen*w的价值，加起来递推
    					{
    						dp[j] += dp[j - a[i].fen*w];
    					}
    					else break;
    				}
    			}
    		}
    		printf("%d\n", dp[m]);//m个物品的时候所能产生的价值
    	}
    	return 0;
    }

**01背包**

for (i = 1; i <= n; i++)
    {
    	for (j = v; j >= a[i].cost; j--)
    	{
    		if (f[j] < f[j - a[i].cost] + a[i].val)
    			f[j] = f[j - a[i].cost] + a[i].val;
    	}
    }

**完全背包**

for (int i = 1; i <= n; i++)
    {
    	for (int j = w[i]; j <= v; j++)
    	{
    		dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
    	}
    }

**多重背包**

for (int i = 0; i<n; i++)
    {      
    	for (int k = 0; k<num[i]; k++)
    	{            
    		for (int j = cc; j >= v[i]; j--)
    		{   
    			dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
    		}
    	}
    }

状压DP

#include <iostream>
    #include <string>
    #include <cstring>
    #include <stack>
    #include <algorithm>
    using namespace std;
    题意：有n门课，每门课有截止时间和完成所需的时间，如果超过规定时间完成，每超过一天就会扣1分，问怎样安排做作业的顺序才能使得所扣的分最小
    思路：因为最多只有15门课程，可以使用二进制来表示所有完成的状况
    例如5，二进制位101，代表第一门和第三门完成了，第二门没有完成，那么我们可以枚举1~1<<n便可以得出所有的状态
    然后对于每一门而言，其状态是t = 1<<i，我们看这门在现在的状态s下是不是完成，可以通过判断s&t是否为1来得到
    当得出t属于s状态的时候，我们便可以进行DP了，在DP的时候要记录路径，方便之后的输出
    const int inf = 1 << 30;
    struct node
    {
    	string name;
    	int dead, cost;
    } a[50];
    struct kode
    {
    	int time, score, pre, now;
    } dp[1 << 15];
    int main()
    {
    	int t, i, j, s, n, end;
    	cin >> t;
    	while (t--)
    	{
    		memset(dp, 0, sizeof(dp));
    		cin >> n;
    		for (i = 0; i<n; i++)
    			cin >> a[i].name >> a[i].dead >> a[i].cost;//每门课的名字、最晚完成时间、花费时间
    		end = 1 << n;//n-1指的是每门课都完成的情况
    		for (s = 1; s<end; s++)//暴力遍历
    		{
    			dp[s].score = inf;//先初始化为无穷大    是最少扣的分数
    			for (i = n - 1; i >= 0; i--)
    			{
    				int tem = 1 << i;//右往左数第i+1位数
    				if (s & tem)//如果右往左数第i+1位数为1   即i+1事件已经完成
    				{
    					int past = s - tem;//不可能为负 past代表当前事件发生之前的状态
    					int st = dp[past].time + a[i].cost - a[i].dead;
    //转移方程 要花的时间=前面要的时间+当前花的时间-最晚时间
    					if (st<0)//如果当前不会被扣分 则等于0
    						st = 0;
    					if (st + dp[past].score<dp[s].score)//更新取最小值
    					{
    						dp[s].score = st + dp[past].score;//当前要扣的分
    						dp[s].now = i;//当前dp最后执行的事件位置
    						dp[s].pre = past;//执行前的二进制状态
    						dp[s].time = dp[past].time + a[i].cost;
    					}
    				}
    			}
    		}
    		stack<int> S;
    		int tem = end - 1;
    		cout << dp[tem].score << endl;//输出总的最少扣分
    		while (tem)
    		{
    			S.push(dp[tem].now);//最后做的事件下表 入栈
    			tem = dp[tem].pre;//转到前面的事件
    		}
    		while (!S.empty())
    		{
    			cout << a[S.top()].name << endl;
    			S.pop();
    		}
    	}
    	return 0;
    }

**线段树**

#include<iostream>
    #include<cstring>
    using namespace std;
    int n, p, a, b, m, x, y, ans;
    struct node
    {
    	int l, r, w, f;
    }tree[400001];
    inline void build(int k, int ll, int rr)//建树 
    {
    	tree[k].l = ll, tree[k].r = rr;
    	if (tree[k].l == tree[k].r)
    	{
    		scanf("%d", &tree[k].w);
    		return;
    	}
    	int m = (ll + rr) / 2;
    	build(k * 2, ll, m);
    	build(k * 2 + 1, m + 1, rr);
    	tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    inline void down(int k)//标记下传 
    {
    	tree[k * 2].f += tree[k].f;
    	tree[k * 2 + 1].f += tree[k].f;
    	tree[k * 2].w += tree[k].f*(tree[k * 2].r - tree[k * 2].l + 1);
    	tree[k * 2 + 1].w += tree[k].f*(tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1);
    	tree[k].f = 0;
    }
    inline void ask_point(int k)//单点查询
    {
    	if (tree[k].l == tree[k].r)
    	{
    		ans = tree[k].w;
    		return;
    	}
    	if (tree[k].f) down(k);
    	int m = (tree[k].l + tree[k].r) / 2;
    	if (x <= m) ask_point(k * 2);
    	else ask_point(k * 2 + 1);
    }
    inline void change_point(int k)//单点修改 
    {
    	if (tree[k].l == tree[k].r)
    	{
    		tree[k].w += y;
    		return;
    	}
    	if (tree[k].f) down(k);
    	int m = (tree[k].l + tree[k].r) / 2;
    	if (x <= m) change_point(k * 2);
    	else change_point(k * 2 + 1);
    	tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    inline void ask_interval(int k)//区间查询 
    {
    	if (tree[k].l >= a&&tree[k].r <= b)
    	{
    		ans += tree[k].w;
    		return;
    	}
    	if (tree[k].f) down(k);
    	int m = (tree[k].l + tree[k].r) / 2;
    	if (a <= m) ask_interval(k * 2);
    	if (b>m) ask_interval(k * 2 + 1);
    }
    inline void change_interval(int k)//区间修改 
    {
    	if (tree[k].l >= a&&tree[k].r <= b)
    	{
    		tree[k].w += (tree[k].r - tree[k].l + 1)*y;
    		tree[k].f += y;
    		return;
    	}
    	if (tree[k].f) down(k);
    	int m = (tree[k].l + tree[k].r) / 2;
    	if (a <= m) change_interval(k * 2);
    	if (b>m) change_interval(k * 2 + 1);
    	tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    int main()
    {
    	printf("请输入线段树的大小n\n");
    	scanf("%d", &n);//n个节点 
    	printf("请输入n个数，分别是1到n的初始值\n");
    	build(1, 1, n);//从1开始做下标 ,建立1到n的线段树
    	printf("建树完成\n请输入操作线段树的次数m\n");
    	scanf("%d", &m);//m种操作 
    	printf("请输出相应指令\n1 单点查询\n2 单点修改\n3区间查询\n4区间修改\n");
    	for (int i = 1; i <= m; i++)
    	{
    		scanf("%d", &p);
    		ans = 0;
    		if (p == 1)
    		{
    			printf("单点查询,输出第x个数 \n请输入x\n");
    			scanf("%d", &x);
    			ask_point(1);//单点查询,输出第x个数 
    			printf("第%d个数是%d\n", x, ans);
    		}
    		else if (p == 2)
    		{
    			printf("对第x个数加上y,请输入X和Y\n");
    			scanf("%d%d", &x, &y);
    			change_point(1);//单点修改
    			printf("修改完成\n");
    		}
    		else if (p == 3)
    		{
    			printf("查询[a,b]区间的和，请输入a和b\n");
    			scanf("%d%d", &a, &b);//区间查询 
    			ask_interval(1);
    			printf(" %d 到 %d 的和为 %d\n", a, b, ans);
    		}
    		else
    		{
    			printf("对第[a,b]中所有数都加上y,请输入a,b和y\n");
    			scanf("%d%d%d", &a, &b, &y);//区间修改 
    			change_interval(1);
    			printf("修改完成\n");
    		}
    	}
    }

共计27个算法/数据结构 加 三块头文件函数

制作时间：2019.4

[Link 1]: https://download.csdn.net/download/qq_41464123/12157508
[20190418172512582.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/7a37739e61de432c974beaf2c1ea5b13.png