# 常用算法

# 内容总览

打钩的是讲到的,其他的是算法竞赛中建议学习的,不在下面列出的在比赛中基本用不到。

(很多函数的功能很简单,自己都能快速写出来,但是使用函数可以让代码可读性变得更高,这在比赛中是至关紧要的)

  • 算法库 Algorithm
    • [ ] count()
    • [ ] find()
    • [ ] fill()
    • [x] swap()
    • [x] reverse()
    • [ ] shuffle() C++ 11
    • [x] unique()
    • [x] sort()
    • [x] lower_bound() / upper_bound()
    • [x] max() / min()
    • [ ] max_element() / min_element()
    • [ ] prev_permutation() / next_permutation()
  • 数学函数 cmath
    • [x] abs()
    • [x] exp()
    • [x] log() / log10() / log2()
    • [x] pow()
    • [x] sort()
    • [ ] sin() / cos() / tan()
    • [ ] asin() / acos() / atan()
    • [ ] sinh() / cosh() / tanh()
    • [ ] asinh() / acosh() / atanh() C++ 11
    • [x] ceil() / floor()
    • [x] round() C++ 11 (四舍五入)
  • 数值算法 numeric
    • [ ] iota() C++
    • [ ] accumulate()
    • [x] gcd() C++17
    • [x] lcm() C++17
  • 伪随机数生成 random
    • [ ] mt19937
    • [ ] random_device()

# swap()

交换两个变量的值

用法示例

template<class T>
void swap(T& a, T& b);
1
2
int a = 0, int b = 1;
swap(a, b);
// now a = 1, b = 0

int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
swap(arr[4], arr[6]);
// now arr = {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}
1
2
3
4
5
6
7

注意事项

这个swap参数是引用的,不需要像C语言一样取地址。

# sort()

使用快速排序给一个可迭代对象排序

用法示例

template<class Randomit, class Compare>
void sort(Randomit first, Randomit last, Compare comp);
1
2

默认排序从小到大

vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end());
// arr = [0, 1, 1, 1, 8, 9, 9]
1
2
3

如果要从大到小,则需要传比较器进去

vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end(), greater<int>());
// arr = [9, 9, 8, 1, 1, 1, 0]
1
2
3

如果是特殊比较,就需要自己写比较器

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.second != b.second) //第二个值从小到大
        return a.second < b.second;
    return a.first > b.first;
}

int main()
{
    vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};
    sort(arr.begin(), arr.end(), cmp);
    // arr = [(0, 0),(8, 1), (2, 9), (1, 9)]
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# lower_bound() / upper_bound()

已升序排序的元素中,应用二分查找检索指定元素,返回对应元素迭代器位置找不到则返回尾迭代器

  • lower_bound():寻找x\geq x的第一个元素位置
  • upper_bound():寻找>x> x的第一个元素位置

怎么找x\leq x<x< x的第一个元素呢?

  • >x> x 的第一个元素的前一个元素(如果有)便是 x\leq x 的第一个元素

  • x\geq x 的第一个元素的前一个元素(如果有)便是 <x< x 的第一个元素

返回的是迭代器,如何转成下标索引呢?减去头迭代器即可。

用法示例

template<class Forwordit, class T>
Forwordit lower_bound(Forwordit first, Forwordit last, const T& value);
1
2
vector<int> arr{0, 1, 1, 1, 8, 9 ,9};
vector<int>::iterator it = lower_bound(arr.begin(), arr.end(), 7);
int idx = it - arr.begin();
//idx = 4;
1
2
3
4

我们通常写成一行

vector<int> arr{0, 1, 1, 1, 8, 9 ,9};
int idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin();
1
2

# reverse()

使一系列元素反序

template<class T>
T reverse(T first, T last);
1
2

注意:[first, last)

vector<int> arr{0, 1, 1, 1, 8, 9 ,9};
reverse(arr.begin(), arr.end());
// arr = [9, 9, 8, 1, 1, 1, 0]

reverse(arr.begin()+2, arr.begin()+5);
// arr = [9, 9, 1, 1, 8, 1, 0]
1
2
3
4
5
6

# max() / min()

获取最大值或最小值

min(1, 2); // 比较两个数

min(min(1, 3), 2); //比较三个数

min({1, 3, 2, 4}); //C++ 11及以后
1
2
3
4
5

# unipue()

消除数组的重复相邻元素,数组长度不变,但是有效数据缩短,返回的是有效数据位置结尾迭代器

例如:[1,1,4,5,1,4][1,4,5,1,4,?][1,1,4,5,1,4]\to[1,4,5,1,4,?],?位置为返回的迭代器指向。

template<class Forwardit>
Forwardit unipue(Forwardit first, Forwardit last);
1
2

用法示例

单独使用 unique 并不能达成去重效果,因为它只消除相邻的重复元素。但是如果序列有序,那么它就能去重了。

但是它去重后,序列尾部会产生一些无效数据:[1,1,2,4,4,4,5][1,2,4,5,?,?,?][1,1,2,4,4,4,5]\to[1,2,4,5,?,?,?],函数返回第一个?位置,为了删掉这些无效数据,我们需要结合 erase.

最终,给 vector 去重的写法便是:

vector<int>arrt{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end()); //排序
arr.erase(unique(arr.begin(), arr.end()), arr.end()); //将无效数据删除
1
2
3

# 数学函数

所有函数均支持int / long long / float / double / long double

公式 示例
f(x)=xf(x)=\|x\| abs(-1.0)
f(x)=exf(x)=e^x exp(2)
f(x)=lnxf(x)=\ln x log(3)
f(x,y)=xyf(x,y)=x^y pow(2, 3)
f(x)=xf(x)=\sqrt x sqrt(2)
f(x)=xf(x)=\left\lceil x\right\rceil ceil(2.1)
f(x)=xf(x)=\left\lfloor x \right\rfloor floor(2.1)
f(x)=<x>f(x)=<x> round(2.1)

注意事项

由于浮点误差,有的数学函数的行为可能与预期不符,导致WA。如果操作数都是整型,那么用下面的写法会更稳妥

  • ab\left\lfloor \frac{a}{b} \right\rfloor
    • 别用:floor(1.0 * a / b)
    • 要用:a / b
  • ab\left\lceil \frac{a}{b} \right\rceil
    • 别用:ceil(1.0 * a / b)
    • 要用:(a + b - 1) / b (ab=a+b1b\left\lceil \frac{a}{b} \right\rceil=\left\lfloor \frac{a+b-1}{b} \right\rfloor)
  • a\left\lfloor \sqrt a \right\rfloor
  • aba^b
  • log2a\left\lfloor \log_2a \right\rfloor
    • 别用:log2(a)
    • 要用:__lg (不规范)/ bit_width(C++ 20 可用)

# gcd() / lcd()

(C++ 17)返回最大公因数 / 最小公倍数

int x = gcd(8, 12); // 4
int y = lcm(8, 12); // 24
1
2

如果不是C++ 17,但是是GUN编译器(g++),那么可以用内置函数__gcd()

当然,gcd() / lcd()函数也挺好写,直接写也行(欧几里得算法):

int gcd(int a, int b)
{
    if(!b)
        return a;
    return gcd(b, a % b);
}

int lcd(int a, int b)
{
    return a / gcd(a, b) * b;
}
1
2
3
4
5
6
7
8
9
10
11
上次更新时间:: 2/16/2025, 2:07:31 PM