1、万能头文件
#include <bits/stdc++.h>
2、最大公约数与两数之间求和公式
1、最大公约数
int gcd(int a
,int b
)
{
return b
== 0? a
:gcd(b
,a
%b
);
}
2、两数之间求和公式
int Sn(int a
, int b
)
{
return (a
+b
)*(b
-a
+1)/2;
}
3、进制间的转换
1、十进制转 n 进制
短除法
void conversion(int a
,int n
)
{
if(a
<= 0)
{
cout
<< 0;
return;
}
stack
<int> aa
;
while(a
)
{
aa
.push(a
%n
);
a
/=n
;
}
while(!aa
.empty())
{
int t
= aa
.top();
if(t
> 9)
{
char c
= t
-10 + 'A';
cout
<< c
;
}else
cout
<< t
;
aa
.pop();
}
}
2、n 进制转换其他十进制
n进制的数值每个位数的数
* n
^ (根据所在的位置,小数点往左从
0 开始
) 的累加和
4、利用stringstream进行类型转换
1、
int 转 string
#include<sstream>
void i2s(int number
, string
&str
)
{
stringstream ss
;
ss
<< number
;
ss
>> str
;
}
ps
:可以用于
int、
double、
float 转string类型
2、string 转
int
int s2i(int number
,string
& str
)
{
stringstream ss
;
ss
<< str
;
ss
>> number
;
return number
;
}
5、快速幂计算
long long fastPower(long long base
,long long power
)
{
long long result
= 1;
while(power
> 0)
{
if(power
&1) result
= result
*base
%1000;
power
>>= 1;
base
= base
*base
%1000;
}
return result
;
}
6、快速排序
int partition(int arr
[],int i
, int j
)
{
while(i
< j
)
{
while(i
< j
&& arr
[i
] <= arr
[j
]) j
--;
if(i
< j
) swap(arr
[i
],arr
[j
]);
while(i
< j
&& arr
[i
] <= arr
[j
]) i
++;
if(i
< j
) swap(arr
[i
],arr
[j
]);
}
return i
}
void quick_sort(int arr
[], int low
, int high
)
{
if(low
< high
)
{
int piovt
= partition(arr
,low
,high
);
quick_sort(arr
,low
,piovt
-1);
quick_sort(arr
,piovt
+1,high
);
}
}
7、并查集
主要用于查找判断两个节点之间是否存在联系。
所以主要是两个操作:
1、查找根结点。
2、判断并处理
整个模板可以分为三部分:初始化、查找、处理
#include <bits/stdc++.h>
int id
[1000];
int size
[1000];
int find(p
)
{
while(p
!= id
[p
])
{
id
[p
] = id
[id
[p
]];
p
= id
[p
];
}
return p
;
}
void Union(int p
, int q
)
{
int i
= find(p
);
int j
= find(q
);
if(i
== j
) return ;
if(size
[i
] <= size
[j
])
{
id
[i
] = j
;
size
[j
] += size
[i
];
}else
{
id
[j
] = i
;
size
[i
] += size
[j
];
}
}
int main()
{
for(int i
= 0; i
< 1000; i
++)
{
id
[i
] = i
;
size
[i
] = 1;
}
}
8、斐波那契问题
兔子繁殖问题
{1,1,2,3,5,8,13…
}
关键点:第三年之后每年的兔子数等于前一年兔子数
+前两年兔子数
最遍历的解法为:通过循环递推出每年的兔子数,使用递归时间复杂度较复杂
9、多源点最短路径:Floyd
关于图的问题,都少不了对数据的初始化
Floyd的核心代码
: 主要利用中间点 K 的改变更新图中 i 到 j 的最短路径
for(int k
= 1; k
<= N
; k
++)
for(int i
= 1; i
<= N
; i
++)
for(int j
= 1; j
<= N
; j
++)
map
[i
][j
] = min(map
[i
][j
],map
[i
][k
]+map
[k
][j
]);
可能考到的问题:最短路径、可删除边、最小环
缺点:
10、单源点最短路径:Dijkstra
双循环依次更新开始源点到各源点的距离
void dijkstra(int k
)
{
dis
[k
] = 0;
for(int i
= 0; i
< N
; i
++)
{
int temp
= -1;
int aaa
= inf
;
for(int j
= 0; j
< N
; j
++)
{
if( !vis
[j
] && dis
[j
]< aaa
)
{
aaa
= dis
[j
];
temp
= j
;
}
}
if(temp
== -1) return;
vis
[temp
] = 1;
for(int j
= 0; j
< N
; j
++)
{
if(!vis
[j
])
{
if(dis
[j
] > dis
[temp
] + map
[temp
][j
])
{
dis
[j
] = dis
[temp
] + map
[temp
][j
];
}
}
}
}
}
11、动态规划
动态规划解题步骤
1、问题抽象化
2、建立模型
3、寻找约束条件
4、判断是否满足最优性原理
5、找大问题与小问题的递推关系式
6、填表
7、寻找解组合
12、01背包问题
01背包:从 n 个物品中选中 m 个物品放入背包中,使得背包容量不超过 w 并且价值最大(每个物品都是完整的)
核心代码
: w
[i
] 物品重量;dp
[i
][j
] i 物品,j重量;v
[i
] 价值 ;index
[i
] 记录最优解
找出最大价值(填表)
for(int i
= 1; i
<= n
; i
++)
for(int j
= 1; j
<= w
; j
++)
if(j
< w
[i
])
dp
[i
][j
] = dp
[i
-1][j
];
else
dp
[i
][j
] = max(dp
[i
-1][j
],dp
[i
][j
-w
[i
]] + v
[i
]);
最优解回溯:找出选中的物品
void findMax(
int i
, int j)
{
if(i
>= 0)
{
if(dp
[i
][j
] == dp
[i
-1][j
])
{
index
[i
] = 0;
findMax(i
-1,j
);
}else if(j
- w
[i
] >= 0 && dp
[i
][j
] == dp
[i
-1][j
-w
[i
]] + v
[i
]){
index
[i
] = 1;
findMax(i
-1,j
-w
[i
]);
}
}
}
13、最小生成树
#include <iostream>
#include <algorithm>
using namespace std
;
const int inf
= 1000;
int map
[100][100];
typedef struct
{
int lowcost
;
int adjvex
;
}Element
;
void Prim(int n
,int w
)
{
int temp
;
Element El
[10];
for(int i
= 0; i
< n
; i
++)
{
El
[i
].lowcost
= map
[w
][i
];
El
[i
].adjvex
= w
;
}
El
[w
].lowcost
= 0;
for(int i
= 0; i
< n
-1;i
++)
{
int min
= 1000;
temp
= 100;
for(int j
= 0; j
< n
; j
++)
{
if(El
[j
].lowcost
!= 0 && El
[j
].lowcost
< min
)
{
min
= El
[j
].lowcost
;
temp
= j
;
}
}
cout
<< El
[temp
].adjvex
<< "------" << temp
<< endl
;
El
[temp
].lowcost
= 0;
for(int j
= 0; j
< n
; j
++)
{
if(map
[temp
][j
] < El
[j
].lowcost
)
{
El
[j
].lowcost
= map
[temp
][j
];
El
[j
].adjvex
= temp
;
}
}
}
}
int main(int argc
, char** argv
) {
int n
,m
;
int a
,b
,c
;
while(cin
>>n
>>m
)
{
for(int i
= 0; i
< n
; i
++)
for(int j
= 0; j
< n
; j
++)
if(i
== j
) map
[i
][j
] = 0;
else map
[i
][j
] = inf
;
for(int i
= 0; i
< m
; i
++)
{
cin
>> a
>> b
>> c
;
map
[a
][b
] = map
[b
][a
] = c
;
}
Prim(n
,0);
}
system("pause");
return 0;
}
14、考前重点复习
最短路径问题:关于单源点Dijkstra与多源点Floyd 算法的区别与选择。 单源点:只记录从开始结点到各结点之间最短的路径, 通过与dfs算法的结合可以解决 最短路径 + 最小权值 + 路过的结点等问题的组合。 使用一维数组进制记录,dfs需要二维数组 多源点:使用二维数组记录各结点之间的最短路径。
最小生成树与最短路径的区别: 最短路径求的是到结点的最小距离 而最小生成树求的是整个树的权值最小 prim算法就是从根结点出发遍历出与它相连的最小权值的结点,再通过找到的结点更新。从这方面来看与Dijkstra算法很相似。
Dijkstra + dfs 的结合。 prim typedef struct