C++算法 模版代码 详细介绍（CSP考试专用）
·
C++算法 模版代码
PS：大部分模版代码知识点都有例题 + 链接🔗！请放心食用！
TIP ： 此为CSP-J/S初/复赛复习专用
废话不多说，直接开始今天的内容！
1、高精度算法
1.1 高精度加法：
例题：信息学奥赛一本通 - 1168：大整数加法
1.2 高精度减法：
1.3 高精度乘法：
1.4 高精度除法（高精 / 低精）
2、最大公因数 & 最小公倍数
2.1 最大公因数 - 递归解法
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
2.2 最大公因数 - 非递归解法
用辗转相除法即可
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
2.3 最大公因数 - 内置函数(__gcd())
代码非常简单，加上 numeric 头文件就可以了
cout << __gcd(a, b) << endl;
2.4 最小公倍数
#include <iostream>
using namespace std;
int gcd(int x, int y)
{
if(y == 0) return x;
return gcd(y, x - y);
}
int main()
{
int n, m, y;
cin >> n >> m;
y = gcd(max(n, m), min(n, m));
cout << n * m / y << endl; //n和m的乘积除以最大公约数=最小公倍数
return 0;
}
3、深度优先搜索（DFS）
我这里就不深究了，拿一道八个方向的模板题练练手即可！
例题：东方博宜 - 1435. 数池塘（八方向）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, s;
char a[100][100];
ll fx[8] = {0, 0 , 1 , -1 , -1 , -1 , 1 , 1};
ll fy[8] = {1, -1 , 0 , 0 , -1 , 1 , 1 , -1};
void dfs(ll x, ll y)
{
a[x][y] = '.';
ll tx, ty;
for (ll i = 0; i < 8; i++)
{
tx = x + fx[i];
ty = y + fy[i];
if (a[tx][ty] == 'W')
{
dfs(tx, ty);
}
}
}
int main()
{
cin >> n >> m;
for (ll i = 1; i <= n; i++)
{
for (ll j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
for (ll i = 1; i <= n; i++)
{
for (ll j = 1; j <= m; j++)
{
if (a[i][j] == 'W')
{
s++;
dfs(i, j);
}
}
}
cout << s << endl;
return 0;
}
4、广度优先搜索（BFS）
例题：东方博宜 - 1433. 走出迷宫的最少步数2
用STL中的queue实现即可
#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[200][200];
int fx[4] = {0, 1, 0, -1};
int fy[4] = {1, 0, -1, 0};
struct Node{
int x, y, dist;
};
int bfs(int s1, int s2, int e1, int e2)
{
queue<Node> q;
q.push({s1, s2, 0});
while (!q.empty())
{
Node current = q.front();
q.pop();
if (current.x == e1 && current.y == e2)
{
return current.dist;
}
for (int i = 0; i < 4; i++)
{
int tx = current.x + fx[i];
int ty = current.y + fy[i];
if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && (a[tx][ty] == '.' || a[tx][ty] == 'T'))
{
a[tx][ty] = '#';
q.push({tx, ty, current.dist + 1});
}
}
}
}
int main()
{
int s1, s2, e1, e2;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
if (a[i][j] == 'S')
{
s1 = i;
s2 = j;
}
if (a[i][j] == 'T')
{
e1 = i;
e2 = j;
}
}
}
cout << bfs(s1, s2, e1, e2) << endl;
return 0;
}
5、素数筛
5.1 埃氏筛
例题 ：洛谷 - P3383 【模板】线性筛素数
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN = 1e8 + 10;
vector<ll> primes;
vector<bool> is_prime(MAXN, true);
void esieve(ll n){
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= sqrt(n); i++){
if (is_prime[i]){
for (int j = i * i; j <= n; j += i){
is_prime[j] = false;
}
}
}
for (int i = 2; i <= n; i++){
if (is_prime[i]) primes.push_back(i);
}
return;
}
int main(){
//输入输出加速代码
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, q;
cin >> n >> q;
ll x;
esieve(n);
while (q--){
cin >> x;
cout << primes[x - 1] << endl;
}
return 0;
}
5.2 线性筛（欧拉筛）
例题 ：洛谷 - P3383 【模板】线性筛素数
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
//标记素数（用bool数组防止占用内存）
vector<bool> f(1000010);
//存储所有的素数
vector<ll> primes(1000010);
ll n, k;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
//特判
f[0] = f[1] = true;
//循环遍历每个数，逐个判断
for (ll i = 2; i <= n; i++) {
//如果i是素数，存储
if (!f[i]) {
k++;
primes[k] = i;
}
//每个合数，只能被自己的最小值因子筛除
//j循环的是primes数组
//筛的是 i * primes[j] 中的数
for (ll j = 1; i * primes[j] <= n; j++) {
//将该数筛掉
f[i * primes[j]] = true;
//一定要break！
//如果i % primes[j] == 0
//i * primes[j + 1] % primes[j] == 0
if (i % primes[j] == 0) break;
}
}
cout << k << endl;
return 0;
}
6、动态规划DP（背包问题🎒）
6.1 01背包
例题：东方博宜 - 1282. 简单背包问题
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//一维数组滚动优化
//dp[j] = max(dp[j], dp[j - w] + v);
ll maxw, n;
cin >> maxw >> n;
ll w, v;
vector<ll> dp(maxw + 1, 0);
for (ll i = 1; i <= n; i++) {
cin >> w >> v;
for (ll j = maxw; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[maxw] << endl;
return 0;
}
6.2 完全背包
例题：东方博宜 - 1780. 采灵芝
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t, m;
cin >> t >> m;
ll w, v;
vector<ll> dp(t + 1, 0);
for (ll i = 1; i <= m; i++) {
cin >> w >> v;
//正序循环
for (ll j = w; j <= t; j++) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[t] << endl;
return 0;
}
6.3 多重背包
此问题为多重背包二进制优化版本的！
例题：1889. 多重背包（2）
#include <iostream>
#include <vector>
using namespace std;
vector<int> v(20010), w(20010), dp(2010);
int n, m, vi, wi, si, k;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> wi >> vi >> si;
int t = 1;
while (t <= si){
k++;
v[k] = t * vi;
w[k] = t * wi;
si -= t;
t *= 2;
}
if (si > 0){
k++;
v[k] = si * vi;
w[k] = si * wi;
}
}
//01背包
for (int i = 1; i <= k; i++){
for (int j = m; j >= w[i]; j--){
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[m] << endl;
return 0;
}
6.4 混合背包
转化为01背包即可
例题：1905. 混合背包
#include <iostream>
#include <vector>
using namespace std;
vector<int> v(20000), w(20000), s(20000), dp(1010);
int vi, wi, si, k, n, m;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> vi >> wi >> si;
if (si > 0){
int t = 1;
while (t <= si){
k++;
v[k] = t * vi;
w[k] = t * wi;
s[k] = -1; //转换为01背包
si -= t;
t *= 2;
}
if (si > 0){
k++;
v[k] = si * vi;
w[k] = si * wi;
s[k] = -1; //01背包
}
} else {
k++;
w[k] = wi;
v[k] = vi;
s[k] = si;
}
}
//计算
for (int i = 1; i <= k; i++){
if (s[i] == -1){
for (int j = m; j >= v[i]; j--){
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
} else {
for (int j = v[i]; j <= m; j++){
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
cout << dp[m] << endl;
return 0;
}
请关注我，我会继续更新这篇文章的！
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
11
0- 0
已为社区贡献1条内容
所有评论(0)