1.快速排序
AcWing 785.快速排序：https://www.acwing.com/problem/content/787/
题目描述
给定你一个长度为 n 的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n个整数，表示排好序的数列。
数据范围
1≤n≤100000
代码如下
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}2.二分查找
洛谷P2249 【深基13.例1】查找：https://www.luogu.com.cn/problem/P2249
题目描述
输入 n 个不超过 109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。
输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
输出一行，m 个整数，以空格隔开，表示答案。
数据范围
1≤n≤106，0≤ai，q≤109，1≤m≤105
代码如下
#include<cstdio>
using namespace std;
int n,m,q,a[1000005];
int find(int x) //二分查找
{
int l=1,r=n;
while (l<r)
{
int mid=l+(r-l)/2;
if (a[mid]>=x) r=mid;
else l=mid+1;
}
if (a[l]==x) return l; //找都了就输出他的位置
else return -1; // 没找到输出-1
}
int main()
{
scanf("%d %d",&n,&m); //读入
for (int i=1 ; i<=n ; i++)
scanf("%d",&a[i]); //还是读入
for (int i=1 ; i<=m ; i++)
{
scanf("%d",&q);
int ans=find(q); //看看查找的结果
printf("%d ",ans); //输出
}
return 0;
}3.二分答案
洛谷P1873 [COCI 2011/2012 #5] EKO / 砍树：https://www.luogu.com.cn/problem/P1873
题目描述
伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,10 和 17，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 H，使得他能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。
输入格式
第 1 行 2 个整数 N 和 M，N 表示树木的数量，M 表示需要的木材总长度。
第 2行 N 个整数表示每棵树的高度。
输出格式
1个整数，表示锯片的最高高度。
数据范围
对于 100% 的测试数据，1≤N≤106，1≤M≤2×109，树的高度 <109，所有树的高度总和 >M。
代码如下
#include<bits/stdc++.h>
using namespace std;
long long n,bz,s=0,mid,leftt,longest,trees[1000008];
int main()
{
scanf("%lld%lld",&n,&bz);
for(int i=1;i<=n;i++)
{
scanf("%lld",&trees[i]);
longest=max(longest,trees[i]);//找到最长木材
}
while(leftt<=longest)
{
mid=(leftt+longest)/2; //从中间点开始作为伐木机高度
s=0;
for(int i=1;i<=n;i++)
if(trees[i]>mid) //树的高度大于伐木机高度
s+=trees[i]-mid; //高的部分累加
if(s<bz) //木材不足
longest=mid-1;//在左边搜 减小高度增加木材
else
leftt=mid+1;//在右边搜 增加高度减小木材
}
cout<<leftt-1;
return 0;
}4.素数筛
洛谷P5736 【深基7.例2】质数筛：https://www.luogu.com.cn/problem/P5736
题目描述
输入 n 个不大于 105 的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。
输入格式
第一行输入一个正整数 n，表示整数个数。
第二行输入 n 个正整数 ai，以空格隔开。
输出格式
输出一行，依次输出 ai 中剩余的质数，以空格隔开。
数据范围
1≤n≤100，1≤ai≤105
代码如下
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
bool isprime(int x){//判断是否素数
if(x<=1) return false;//如果小于2，一定不是素数
for(int i=2;i<=sqrt(x);i++){//为什么要到sqrt(x)呢，因为如果有一个大于sqrt(n)的数可以被n整除，那么必有一个数n/i也可以被n整除且小于i
if(x%i==0) return false;//如果可以整除，那么不是素数
}
return true;//是素数
}
int main(){
int n,a;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
if(isprime(a)){
cout<<a<<" ";//是素数，就输出
}
}
return 0;
}5.整数数位分解
题目描述
输入一个数x，从个位开始输出每一位对应的值。
输入描述
输入一个数x。
输出描述
从个位开始输出每一位。
代码如下
#include<iostream>
using namespace std;
int a[10010],cnt=0;
void solve(int x)
{
while(x)
{
a[cnt++]=x%10;
x/=10;
}
}
int main()
{
int n;
cin>>n;solve(n);
for(int i=0;i<cnt;i++)
{
cout<<a[i]<<" ";
}
return 0;
}6.质因数分解
题目描述
输入一个数，从小到大输出这个数的所有因数。
输入描述
输入一个数n。
输出描述
从小到大输出n的因数。
代码如下
#include<iostream>
using namespace std;
int a[10010],cnt=0;
void solve(int x)
{
for(int i=1;i<=x;i++)
{
if(x%i==0)
{
a[cnt++]=i;
}
}
}
int main()
{
int n;
cin>>n;solve(n);
for(int i=0;i<cnt;i++)
{
cout<<a[i]<<" ";
}
}7.gcd（最大公约数）&lcm（最小公倍数）
最大公约数gcd（the Greatest Common Divisor）
求gcd常用欧几里得算法( 辗转相除法 )
- 递归式: gcd(a,b) = gcd(b,a%b)
- 递归边界: gcd(a,0) = a
int gcd( int a, int b )
{
return b ? gcd(b,a%b) : a;
}证明：
设 a = kb + r, 则 r = a - kb.
设d为a和b的一个公约数, 那么由 r = a - kb, 得d也是r的一个约数.
因此d是b和r的公约数.
又由 r = a%b, 得d是b和a%b的公约数.
因此d既是a和b的公约数, 又是b和a%b的公约数.
题目：求两个整数最大公约数，即每次将较大的数变成大数减去小数的值。
运用三目运算符“a?b:c”，若a为真，则返回b值，否则返回c值。
#include<bits/stdc++.h>
using namespace std;
int a,b;
int gcd(int x,int y)
{
return y=0 ? x : gcd(y ,x%y); //如果y的值为0，则返回x的值，否则返回gcd(y,x%y);
}
int main()
{
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}最小公倍数lcm（the Least Common Multiple）
int lcm( const int a, const int b )
{
return a / gcd(a,b) * b;
}最小公倍数的求解在最大公约数的基础上运行. 当得到a和b的最大公约数d之后, 可以马上得到a和b最小公倍数是ab / d.
由于ab在实际运算中可能会溢出,因此更恰当的写法是a / d \* b.由于d是a的约数,所以a/d一定可以整除.
8.前缀和
引例
给出5个数（1，3，7，5，2），求对应位的前缀和。
#include<iostream>
using namespace std;
int main()
{
const int n = 5;
int arr[n] = { 1,3,7,5,2 };
int sum[n];
sum[0] = arr[0];
for (int i = 1; i < n; i++)sum[i] = sum[i - 1] + arr[i];
for (int i = 0; i < n; i++)cout << sum[i] << " ";
return 0;
}输出：
1 4 11 16 18自定义get_sum函数get_sum(int l,int r)
例如，给定5个数（1，3，7，5，2），求2-4，0-3，3-4位的前缀和。
#include<iostream>
using namespace std;
#define get_sum(l,r)(l?sum[r]-sum[l-1]:sum[r])
int main()
{
const int n = 5;
int arr[n] = { 1,3,7,5,2 };
int sum[n];
sum[0] = arr[0];
for (int i = 1; i < n; i++)sum[i] = sum[i - 1] + arr[i];
cout << get_sum(2, 4) << endl;
cout << get_sum(0, 3) << endl;
cout << get_sum(3, 4) << endl;
}输出：
14
16
7get_sum()函数也可这样定义：
#include<iostream>
using namespace std;
const int n = 5;
int sum[n];
int get_sum(int l, int r)
{
if (l != 0)return sum[r] - sum[l - 1];
else return sum[r];
}
int main()
{
int arr[n] = { 1,3,7,5,2 };
sum[0] = arr[0];
for (int i = 1; i < n; i++)sum[i] = sum[i - 1] + arr[i];
cout << get_sum(2, 4) << endl;
cout << get_sum(0, 3) << endl;
cout << get_sum(3, 4) << endl;
}sum[0]=arr[0]; 类似数列第一项S1=a1
sum[i]=sum[i-1]+arr[i]; 类似数列an=Sn-Sn-1
9.差分
引例
给定5个数（1，3，7，5，2），定义一个函数add(int l,int r,int v) 使第l到第r位加v，输出最终数列。
#include<iostream>
using namespace std;
int d[6] = { 0 };
void add(int l, int r, int v)
{
d[l] += v;
d[r + 1] -= v;
}
int main()
{
int arr[5] = { 1,3,7,5,2 };
add(2, 4, 5);
add(1, 3, 2);
add(0, 2, -3);
for (int i = 1; i < 5; i++)d[i] += d[i - 1];
for (int i = 0; i < 5; i++)
{
arr[i] += d[i];
cout << arr[i] << " ";
}
memset(d, 0, sizeof(d));
return 0;
}输出：
-2 2 11 12 710.dfs全排列（n选m）
引例
例：输入一个数n，输出n的全排列（假如有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。将这3张扑克牌分别放入3个盒子一共有几种不同的放法呢？）
基本模型：
void dfs(int step){
判断边界
尝试每一种可能 for(i=1;i<=n;i++){
继续下一步 dfs(step+1)
}
返回
}代码如下：
#include<stdio.h>
int a[10],book[10],n;
//这里还有需要注意的地方C语言全局变量默认为0
void dfs(int step){ //此时在第step盒子面前，需要往里面放第i张扑克牌
int i;
if(step==n+1){ //这里说明前面的n个盒子已经放好了，这是dfs结束的标志
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("\n");
return ;
/*
注意这个 return 它的作用不是返回主函数，而是返回上一级的dfs函数
例：如果此时是 dfs(5),遇到这个 return 就会回到上一级的 dfs函数
也就是dfs(4),但此时dfs(4)的大部分语句已经执行了，只需要接着执行 book[i]=0
然后继续进入for循环进入下一次的 dfs函数，直到结束。
*/
}
for(int i=1;i<=n;i++){
if(book[i]==0){ //说明i号扑克牌还在手里，需要放入step号盒子
a[step]=i;//将i号扑克牌放到第step个盒子中
book[i]=1;//此时i号扑克牌已经被使用
dfs(step+1);
/*注意这里是自己调用自己，表示此时走到了第step+1个盒子面前*/
book[i]=0;
/*book[i]=0表示dfs调用结束了，换句话说就是扑克牌已经全部放完了
需要按照顺序将扑克牌收回，重新放，也就是前面所说的
*/
}
}
return;//这里表示这一级别的dfs函数已经结束了，返回上一级 dfs函数
}
int main(){
scanf("%d",&n);
dfs(1); //dfs函数的开始
return 0;
}C++代码如下：
#include<iostream>
using namespace std;
int a[10],book[10],n;
void dfs(int step)
{
int i;
if(step==n+1)
{
for(i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++)
{
if(book[i]==0)
{
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return ;
}
int main()
{
cin>>n;
dfs(1);
return 0;
}牛客竞赛[NOIP2002]选数：https://ac.nowcoder.com/acm/problem/16706
题目描述
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为： 3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。 现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3＋7＋19＝29）。
输入描述
输入格式为：n , k（1<=n<=20，k＜n） x1,x2，…,xn （1<=xi<=5000000）
输出描述
输出格式为：一个整数（满足条件的种数）。
代码如下
#include<iostream>
using namespace std;
int n,k,arr[25],ans=0;
bool prime(int x) //素数判断
{
for(int i=2;i*i<=x;i++)
{
if(x%i==0)return 0;
}
return 1;
}
void dfs(int m,int sum,int xu) //m为选的个数，sum为选数的和
{
if(m==k) //如果选够了k个数，那么进行判断
{
if(prime(sum))ans++; //若判断为素数，则ans++
return ;
}
for(int i=xu;i<n;i++)dfs(m+1,sum+arr[i],i+1); //xu的用处是保证不降原则，后面进行深搜
return ;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)cin>>arr[i];
dfs(0,0,0);
cout<<ans;
}11.floyd最短路
最短路 单源最短路 所有权都是正数 朴素Dijkstra算法 O(n^2)
堆优化版Dijkstra算法 O(mlogn)
存在负权边 Bellman-Ford O(nm)
SPFA 一般O(m),最坏O(nm)
多源汇最短路 Floyd算法 O(n^3)AcWing 854.Floyd求最短路：https://www.acwing.com/problem/content/856/
题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1≤n≤200,1≤k≤n2,1≤m≤20000, 图中涉及边长绝对值均不超过 10000。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210,INF=1e9;
int n,m,Q;
int d[N][N];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
cin>>n>>m>>Q;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)d[i][j]=0;
else d[i][j]=INF;
while(m--)
{
int a,b,w;
cin>>a>>b>>w;
d[a][b]=min(d[a][b],w);
}
floyd();
while(Q--)
{
int a,b;
cin>>a>>b;
if(d[a][b]>INF/2)puts("impossible");
else cout<<d[a][b]<<endl;
}
}12.邻接表+dijkstra最短路
AcWing 849. Dijkstra求最短路I ：https://www.acwing.com/problem/content/851/
题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,1≤m≤105,图中涉及边长均不超过10000。
解题思路
1.初始化距离：dist[1]=0，dist[i]=+∞
2.迭代：for循环，i从0~n; s:当前以确定最短距离的点
找到不在s中的距离最近的点——>t
把t加到s里面
用t更新其他点的距离
稠密图：邻接矩阵 稀疏图：邻接表
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=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;
st[t]=true;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
int t=dijkstra();
cout<<t<<endl;
}13.邻接表+堆优化dijkstra
AcWing 850. Dijkstra求最短路II：https://www.acwing.com/problem/content/852/
题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×105,图中涉及边长均不小于 0，且不超过 10000。数据保证：如果最短路存在，则最短路的长度不超过 109。
解题思路
1.初始化距离：dist[1]=0，dist[i]=+∞
2.迭代：for循环，i从0~n; s:当前以确定最短距离的点
找到不在s中的距离最近的点——>t n2 n
把t加到s里面 O(1)总共n次 n
用t更新其他点的距离 m次(m是边的数量) mlogn
稠密图：邻接矩阵 稀疏图：邻接表
堆 手写堆 n个数
优先队列 m个 mlogn#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=150010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>>heap;
heap.push({0,1});
while(heap.size())
{
PII t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver]) continue;
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>distance+w[i])
{
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=dijkstra();
cout<<t<<endl;
}14.01背包
AcWing 2. 01背包问题：https://www.acwing.com/problem/content/2/
题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000，0<vi,wi≤1000
解题思路
f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
result=max{f[n][0~v]}
f[i][j]:
1.不选第i个物品，f[i][j]=f[i-1][j];
2.选第i个物品,f[i][j]=f[i-1][j-v[i]];
f[i][j]=max{1. 2.}
f[0][0]=0;#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int f[N][N];
int v[N],w[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
int res=0;
for(int i=0;i<=m;i++)res=max(res,f[n][i]);
cout<<res<<endl;
}15.高精度加法
AcWing 791.高精度加法：https://www.acwing.com/problem/content/793/
题目描述
给定两个正整数（不含前导 0），计算它们的和。
输入格式
共两行，每一行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤100000
#include<iostream>
#include<vector>
using namespace std;
const int N= 1e6+10;
//C=A+B
vector<int> add(vector<int> &A,vector<int> &B)
{
vector<int> C;
int t=0;
for(int i=0; i<A.size()||i<B.size();i++)
{
if(i<A.size())t+=A[i];
if(i<B.size())t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(1);
return C;
}
int main()
{
string a,b;
vector<int> A,B;
cin>>a>>b; //a="123456"
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');//A={6,5,4,3,2,1}
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
auto C=add(A,B);
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
return 0;
}16.高精度乘法
AcWing 793.高精度乘法：https://www.acwing.com/problem/content/795/
题目描述
给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B 的值。
数据范围
1≤A的长度≤100000,0≤B≤10000
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &A,int b)
{
vector<int> C;
int t=0;
for(int i=0;i<A.size()||t;i++)
{
if(i<A.size())t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
auto C=mul(A,b);
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
return 0;
}17.BF字符串匹配
题目描述
给定主串S，判断模式串F是否是S的子串，如果是则返回T在S中出现的第一个位置，否则返回0。
算法思想
使用暴力算法解题，从主串S的第一个字符开始和模式串T的第一个字符进行比较，若相等则比较二者后续字符，否则，主串回溯到第二个字符，模式串回溯到第一个字符；继续比较，不匹配，主串回溯到第三个字符，模式串回溯到第一个字符。重新上述过程，直到模式串T中的字符全部比较完毕，说明匹配成功；否则匹配失败。
#include <iostream>
using namespace std;
int BF(char *S,char *T){
int i=0,j=0;
while(S[i]!='\0'&&T[j])
{
if(S[i]==T[j])
{
i++;
j++;
}
else
{
i=i-j+1;//主串回溯到上次回溯位置的下一个位置
j=0;//模式串回溯到第一个位置
}
}
if(T[j]=='\0')
return i-j+1; //返回T在S中第一次出现的位置
else return 0;
}
int main(){
char S[50]={'a','b','a','c','b','a','b','c'};
char T[50]={'b','a','b','c'};
cout<<BF(S,T)<<"\n";
return 0;
}18.BFS迷宫问题
AcWing 844.走迷宫 ：https://www.acwing.com/problem/content/846/
题目描述
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
int g[N][N];
int d[N][N];
PII q[N*N];
int bfs()
{
int hh=0,tt=0;
q[0]={0,0};
memset(d,-1,sizeof d);
d[0][0]=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x >=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
{
d[x][y]=d[t.first][t.second]+1;
q[++tt]={x,y};
}
}
}
return d[n-1][m-1];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
cout<<bfs()<<endl;
return 0;
}19.Kruskal求最小生成树
AcWing 859. Kruskal算法求最小生成树：https://www.acwing.com/problem/content/description/861/
题目描述
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤105,1≤m≤2∗105,图中涉及边的边权的绝对值均不超过 1000。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010;
int n,m,p[N];
struct EDGE
{
int a,b,w;
}edge[M];
//结构体排序我还是更习惯这样，清晰，小的在前面；
bool cmp(EDGE a,EDGE b)
{
return a.w<b.w;
}
//并查集，正好在图论这儿复习了，p[x]里面存的是x的父亲，如果p[x]的父亲就是他自己，那说明他是祖宗
int find(int x) // 并查集。find的功能是找父亲。
{
if (p[x] != x) p[x] = find(p[x]);//不是祖宗，就找父亲的父亲。
return p[x];
}
int main()
{
cin>>n>>m;
for(int i= 0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
//这样表示明显比这样方便（
//edge[i].a=x,edge[i].b=y,edge[i].w=z;
edge[i]={x,y,z};
}
//结构体排序，自己写一下cmp
sort(edge,edge+m,cmp);
//打表找bug时用的，忽略。for(int i =0 ; i< m;i++) printf("%d\n",edge[i].w);
//万物伊始，每个人都是祖宗
for(int i =0;i<n;i++) p[i]=i;
int res=0,cnt=0;//非全局变量使用前看来要初始化。res是权值，cnt是边数
//kruskal算法：从最小的边开始画，直到把整个图画通。
for(int i =0;i<m;i++)
{
int a =edge[i].a,b=edge[i].b,w=edge[i].w;
a=find(a),b=find(b);
if(a!=b)
{
p[a]=b;
res+=w;
cnt++;
}
}
//连接n个点至少需要n-1条边，如果不够，那肯定是不连通
if(cnt<n-1) puts("impossible");
else printf("%d",res);
}20.Prim求最小生成树
AcWing 858. Prim算法求最小生成树：https://www.acwing.com/activity/content/problem/content/924/
题目描述
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤500,1≤m≤105, 图中涉及边的边权的绝对值均不超过 10000。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边
void prim()
{
memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
int res= 0;
dt[1] = 0;//从 1 号节点开始生成
for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
{
int t = -1;
for(int j = 1; j <= n; j++)//每个节点一次判断
{
if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
t = j;
}
//2022.6.1 发现测试用例加强后，需要判断孤立点了
//如果孤立点，直返输出不能，然后退出
if(dt[t] == 0x3f3f3f3f) {
cout << "impossible";
return;
}
st[t] = 1;// 选择该点
res += dt[t];
for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
{
if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
{
dt[i] = g[t][i];//更新距离
pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
}
}
}
cout << res;
}
void getPath()//输出各个边
{
for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。
{
cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
}
}
int main()
{
memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
cin >> n >> m;//输入节点数和边数
while(m --)
{
int a, b, w;
cin >> a >> b >> w;//输出边的两个顶点和权重
g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
}
prim();//求最下生成树
//getPath();//输出路径
return 0;
}