C++算法基础

竞赛 / 算法 / 基础知识
Word count: 3.6k   |   Reading time≈ 14 min

C++算法基础

std：Cstd是指C编程语言的标准库（Standard Library），它包含了一系列的函数和类。

STL：C的STL指的是标准模板库（Standard Template Library），它是C标准库的一部分，提供了一组通用的模板类和函数，用于实现常见的数据结构和算法。

std算法

__gcd()

计算整数 m 与 n 的最大公约数。

返回值

若 m 与 n 均为零则返回零。否则返回 |m| 与 |n| 的最大公约数。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;

int main() {
	cout<<__gcd(15, 81)<<"\n";    // 输出  3
    cout<<__gcd(0, 44)<<"\n";     // 输出  44
    cout<<__gcd(0, 0)<<"\n";      // 输出  0
    cout<<__gcd(-6, -15)<<"\n";   // 输出  -3
    cout<<__gcd(-17,289)<<"\n";   // 输出  -17
    cout<<__gcd(17,-289)<<"\n";   // 输出  17
	return 0;
}
max_element()

寻找范围 [first, last) 中的最大元素。

  1. 用 operator< 比较元素。

  2. 用给定的二元比较函数 comp 比较元素。

返回值

指向范围 [first, last) 中最大元素的迭代器。若范围中有多个元素等价于最大元素，则返回指向首个这种元素的迭代器。若范围为空则返回 last 。

示例：

1
2
3
4
// 最大
ll id=max_element(b+1,b+n2+1)-b;
// 最小
ll id=min_element(a+1,a+n1+1)-a;
sort()

默认情况下sort函数使用小于号运算符来比较元素大小。因此可以通过以下方式来重写排序规则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct choc {
	int price;// 巧克力价格
	int len;// 保质期到
	int cnt;// 巧克力数量
	bool operator < (const choc&b) { // 重载<符号的原因是sort默认就是使用<符号来实现排序的
		if(price == b.price)return len>b.len;// 价格相等，则按保质期的长度降序
		return price<b.price;// 按价格升序
	}
} a[N];
signed main() {
	int x, n;
	cin>>x>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i].price>>a[i].len>>a[i].cnt;
	}
	sort(a+1, a+1+n);// 根据新规则排序
	return 0;
}
next_permutation()

变换范围 [first, last) 为来自所有按相对于 operator< 或 comp 的字典序的下个排列。若这种排列存在则返回 true ，否则变换范围为首个排列（如同用 std::sort(first, last) ）并返回 false 。

返回值

若新排列按字典序大于旧者则为 true 。若抵达最后重排并重置范围为首个排列则为 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <string>
#include <iostream>
 
int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));// 当前排列的下一个排列
}
/*
aab
aba
baa
*/

C++重载

operator <

重载：

1
2
3
4
5
6
struct s_node{
    int id; long long n_dis;   //id：结点；n_dis：这个结点到起点的距离
    s_node(int b,long long c){id=b; n_dis=c;}
    bool operator < (const s_node & a) const
    { return n_dis > a.n_dis;}
};

在使用 < 运算符时，如果我们有两个 s_node 类型的变量 x 和 y，则应该将它们作为参数传递给运算符函数，例如 x<y 将调用 < 运算符，并把 x 作为隐含的 this 参数传递进去，把 y 作为 a 参数传递进去，从而比较 x 和 y 的大小关系。

C++数组

数组的初始化

在C++中，定义一个数组后，数组中的元素不会自动初始化为0。如果你想要将所有元素初始化为0，可以使用以下两种方法：

  1. 使用memset函数。该函数可以将一块内存空间按字节赋值为某个指定的值。例如，要将一个大小为n+1乘以k+1的二维数组dp中的所有元素都初始化为0，可以使用如下代码：

    1
    memset(dp, 0, sizeof(dp));

  2. 对数组进行显式初始化。例如，要将dp数组中的所有元素都初始化为0，可以使用如下代码：

    1
    2
    3
    4
    5
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp[i][j] = 0;
        }
    }

C++类

string类

- 构造函数

string(count, char)是C++中的一个构造函数，它可以创建一个由重复字符构成的字符串。其中，第一个参数表示字符的个数，第二个参数表示要重复的字符。

例如，如果我们调用string(3, 'A')，就会创建一个由三个’A’字符构成的字符串"AAA"。如果我们调用string(5, 'B')，就会创建一个由五个’B’字符构成的字符串"BBBBB"。

- 成员函数

  • find()：find() 是一个字符串方法，它可以在一个较大的字符串中查找指定的子字符串，并返回该子字符串被找到的位置。如果没有找到该子字符串，则会返回 npos（表示“无位置”）。

  • substr()：可用于从string 类型的字符串中提取子字符串；其中，pos参数表示要提取子字符串的开始位置，len参数表示要提取的字符数。默认情况下，pos为0，len为s.size() - pos。

类型转换

int 类型

范围：-2.147483648 × 10^9~2.147483647 × 10^9

long long 类型

范围：-9.223372036854776 × 10^18~9.223372036854776 × 10^18

__int128 类型

__int128 就是占用128字节的整数存储类型。由于是二进制，范围就是 −2127 ~ 2127−1，如果使用了 unsigned __int128，则范围变成 0 ~ 2128，即约39位数！

INF

1
const long long INF = 0x3f3f3f3f3f3f3f3fLL;  //这样定义INF的好处是: INF <= INF+x 防止溢出

string转double

std::stod() 函数

转译 string str 中的浮点值。

string转int

std::stoi() 函数

转译字符串 str 中的有符号整数值。

舍弃所有空白符（以调用 isspace() 鉴别），直到找到首个非空白符，然后取尽可能多的字符组成底 n （其中 n=base ）的整数表示，并将它们转换成一个整数值。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <string>
 
int main()
{
    std::string str1 = "45";
    std::string str2 = "3.14159";
    std::string str3 = "31337 with words";
    std::string str4 = "words and 2";
 
    int myint1 = std::stoi(str1);
    int myint2 = std::stoi(str2);
    int myint3 = std::stoi(str3);
    // 错误： 'std::invalid_argument'
    // int myint4 = std::stoi(str4);
 
    std::cout << "std::stoi(\"" << str1 << "\") is " << myint1 << '\n';
    std::cout << "std::stoi(\"" << str2 << "\") is " << myint2 << '\n';
    std::cout << "std::stoi(\"" << str3 << "\") is " << myint3 << '\n';
    //std::cout << "std::stoi(\"" << str4 << "\") is " << myint4 << '\n';
}
/*
std::stoi("45") is 45
std::stoi("3.14159") is 3
std::stoi("31337 with words") is 31337
*/

C++位运算

算术右移

在汇编语言中，对于算术右移(高位补符号位)，如果最高位为1，则补1，否则补0， 如将10000000算术右移7位，应该变成11111111；

逻辑右移

对于逻辑右移7位，则不考虑符号位，变为00000001，这点就是算术右移和逻辑右移的区别。

算术左移

对于算术左移，在右边补0：比如 00101011算术左移一位:01010110

逻辑左移

对于逻辑左移，同样是在右边补0，如：00010111逻辑左移两位：01011100

⭕️左移一般将低位补0。但右移可以是逻辑右移（高位补0）或算术右移（高位补符号位）。

将一个值左移N位相当于乘以2N。同理，算术右移N位，相当于除以2N。\textcolor{red}{将一个值左移N位相当于乘以2^N。同理，算术右移N位，相当于除以2^N。}

左移与右移

  1. 左移 <<
    取两个数字，左移第一个操作数的位，第二个操作数决定要移动的位置。换句话说，左移动一个整数 x 和一个整数 y（x<<y）等价于x乘以2y。

  2. 右移 >>

取两个数字，向右移动第一个操作数的位，第二个操作数决定移动的位置。同样地，右平移（x>>y）等价于x除以2y。

C++输入输出

输出精度控制？（好像没效果）

std::setprecision(int n)：

控制输出浮点数的有效数字位数为n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <iomanip>
#include <cmath>
#include <limits>
int main()
{
    const long double pi = std::acos(-1.L);
    std::cout << "default precision (6): " << pi << '\n'
              << "std::setprecision(10): " << std::setprecision(10) << pi << '\n'
              << "max precision:         "
              << std::setprecision(std::numeric_limits<long double>::digits10 + 1)
              << pi << '\n';
}
//结果：
default precision (6): 3.14159
std::setprecision(10): 3.141592654
max precision:         3.141592653589793239

C语言输出精度控制（推荐）

对于有格式要求的输入输出，使用C语言的输入(scanf)和输出(printf)更加简便 。

1、格式控制符

格式控制符 %02d 指定每个数值的宽度为2，不足两位则在前面补0；

1
printf("%d-%02d-%02d", aa, bb, cc);// 格式控制符 %02d 指定每个数值的宽度为2，不足两位则在前面补0

关闭C++与C标准输入输出的同步

1
ios_base::sync_with_stdio(false);

cin.tie(0)

cin.tie(0)是一条C代码，它的作用是取消 cin 对 cout 的同步。在 C 中，当我们使用 cin 输入数据时，程序会默认先输出缓冲区中的内容，然后再等待用户输入。而这个输出操作可能会对程序的性能造成一定的影响，特别是当我们需要大量输入数据时。

为了避免这种性能问题，我们可以使用 cin.tie(nullptr) 或 cin.tie(0) 将 cin 与输出流分离。其中，tie() 函数是一个 I/O 流绑定函数，用于将两个流关联在一起，而参数为 nullptr 或 0 的 tie() 函数则表示取消绑定。

因此，cin.tie(0) 的作用就是取消 cin 和 cout 的绑定，使得输入操作和输出操作不再同步进行，从而提高程序的运行效率。

cout.tie(0)

cout.tie(0)也是一条C代码，和cin.tie(0)类似，它的作用是取消 cout 对 cin 的同步。在 C 中，当我们使用 cout 输出数据时，程序会默认先将缓冲区中的内容输出到屏幕上，然后再等待用户输入。而这个输出操作可能会对程序的性能造成一定的影响，特别是当我们需要大量输出数据时。

为了避免这种性能问题，我们可以使用 cout.tie(nullptr) 或 cout.tie(0) 将 cout 与输入流分离。其中，tie() 函数是一个 I/O 流绑定函数，用于将两个流关联在一起，而参数为 nullptr 或 0 的 tie() 函数则表示取消绑定。

因此，cout.tie(0) 的作用就是取消 cout 和 cin 的绑定，使得输出操作和输入操作不再同步进行，从而提高程序的运行效率。

EOF（End Of File）

通常在文本的最后存在此字符表示资料结束。

示例代码：

1
while(scanf("%d", &a[cnt])!=EOF)cnt++;

当上面的程序运行时，如果不加" != EOF"，那么这个程序就是个死循环，会一直运行下去；加上" != EOF"后该程序就不是死循环了，如果在终端不进行输入该程序会自动结束(while的意思就是说当当前输入缓存还有东西时就一直读取，直到输入缓存中的内容为空时停止)。

在Terminal中输入完成之后按下CTRL+Z、Enter即可等价于EOF：

image-20230406010938399

C++数学相关

曼哈顿距离

曼哈顿距离也称为**城市街区距离或 L1 距离**，它是在欧几里德空间中两点之间的距离度量方法之一。曼哈顿距离是指从一个点到另一个点沿着网格线走的最短距离，即沿着水平和垂直方向行走的距离之和。

例如，在二维平面上，点 A (x1, y1) 到点 B (x2, y2) 的曼哈顿距离为 |x1 - x2| + |y1 - y2|。

曼哈顿距离常用于计算机科学、统计学、数据挖掘等领域中，特别是在路线规划、图像处理、聚类分析等方面的应用比较广泛。

等差等比数列

1、等差数列

一个等差数列是指一个数列中每个相邻的数之间有着相同的差值。下面分别介绍等差数列的通式和求和公式。

等差数列通式：
假设等差数列的第一项为a1，公差为d，则它的第n项an可以表示为：
an = a1 + (n-1)d

例如，如果一个等差数列的第一项是2，公差是3，那么它的第5项就可以用上述公式计算得到：
a5 = 2 + (5-1)×3 = 14

等差数列求和公式：
对于一个有限项的等差数列，我们可以使用下面的公式来求和：
Sn = n/2 × (a1 + an)

其中，Sn表示该等差数列的前n项和。例如，如果一个等差数列的前10项分别是2、5、8、11、14、17、20、23、26和29，则可以使用上述公式计算它们的和：
S10 = 10/2 × (2 + 29) = 155

2、等比数列

一个等比数列是指一个数列中每个相邻的数之间有着相同的比值。下面分别介绍等比数列的通式和求和公式。

等比数列通式：
假设等比数列的第一项为a1，公比为q，则它的第n项an可以表示为：
an = a1 × q^(n-1)

例如，如果一个等比数列的第一项是2，公比是3，那么它的第5项就可以用上述公式计算得到：
a5 = 2 × 3^(5-1) = 162

等比数列求和公式：
对于一个有限项的等比数列，我们可以使用下面的公式来求和：
Sn = (a1 × (1-q^n)) / (1-q)

其中，Sn表示该等比数列的前n项和。例如，如果一个等比数列的前5项分别是2、6、18、54和162，则可以使用上述公式计算它们的和：
S5 = (2 × (1-3^5)) / (1-3) = 242

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信