【小码匠自习室】CSP-J/S复赛准备：STL复习（一）

2022-12-06 10:56:14 浏览数 (1)

【小码匠自习室】CSP-J/S复赛准备：STL复习（一）

  • 头文件和命名空间
    • 命名空间
    • 万能头文件
    • 指定引入头文件
  • 介绍篇
    • abs：返回x的绝对值
    • sin/cos/tan：三角函数
    • string：文字列
  • 入门
    • min/max
    • swap
    • __gcd
    • rand：需要确认
    • clock：待确认
    • reverse
    • sort
  • 参考资料

C 中提供很多标准库，本篇文章着重介绍竞赛中常用的标准库和算法。

注：本文部分内容源于厳選！C アルゴリズム実装に使える 25 の STL 機能【前編】，针对日文进行了翻译

头文件和命名空间

命名空间

代码语言：javascript复制
using namespace std;

万能头文件

代码语言：javascript复制
#include <bits/stdc  .h>

指定引入头文件

  • 标准iostream 头文件说明#include标准iostream对象和操作
  • 容器 头文件说明补充#include <vector>可变大小一维数组 #include <deque>双端队列 #include <forward_list>单向链表 #include <list>双向链表 #include <map>关联数组关联容器multimap在次头文件中#include <set>集合关联容器multiset在次头文件中#include <unordered_map>哈希关联数组 #include <unordered_set>哈希集合 #include <queue>队列priority_queue在此头文件中#include <stack>栈 #include <array>固定大小一维数组 #include <bitset>bool数组
  • 对应C标准库头文件 头文件说明补充#include <cmath>标准数学函数 #include <cstdlib>C风格分配随机数 #include <ctime>C风格日期和时间工具 #include <cstdio>printf() I/O函数族 #include <cassert>断言宏 #include <cstring>C风格字符串函数
  • 其他常用 头文件说明补充#include <string>字符串 #include <chrono>时间工具 #include <ios>iostream基类 #include <iostream>标准iostream对象和操作 #include <algorithm>泛型算法 #include <tuple>元组 #include <iterator>迭代器及其支持 #include <complex>复数及其运算 #include <random>随机数发生器

介绍篇

标准库

说明

abs

绝对值函数

sin/cos/tan

三角函数

string

字符串

abs：返回x的绝对值

  • abs(-16) = 16
  • abs(8) = 8
代码语言：javascript复制
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    // 例如1: 输入2个小数a 、 b、计算a-b的绝对值，并用小数输出
    double a, b;
    cin >> a >> b;
    printf("%.12lfn", abs(a - b));
    return 0;
}

sin/cos/tan：三角函数

  • 引入头文件：#include <cmath>

函数

说明

sin(x)

sin (x) 以 double类型返回 sin (x) 的值。 例如，sin (π / 6) = 0.5。

cos(x)

cos (x) 以 double类型返回 cos (x) 的值。 例如，cos (π / 6) = 0.866025 ...

tan(x)

tan (x) 以 double类型返回 tan (x) 的值。 例如，tan (π / 6) = 0.577350

代码语言：javascript复制
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    printf("%.12lfn", sin(30));

    double pi = 3.141592653589793238;
    double x;
    cin >> x;
    printf("%.12lfn", sin(x / 180.0 * pi));
    printf("%.12lfn", cos(x / 180.0 * pi));
    printf("%.12lfn", tan(x / 180.0 * pi));
    return 0;
}

string：文字列

  • S、T是字符串，c是char类型字符

程序

说明

string S

定义string类型变量

cin >> S;

接受输入文字列

cout << S;

输出文字列

S[i]

获取S的第i个文字

S = T;

文字列S和T相连，例如：S="a" T="bc" 连接后，则S="abc"

S = c;

文字列S和char类型的c连接，例如：S = "qiit", c = 'a'的时候，连接后，则S = "qiita"

S.size()

返回S的长度

S.substr(l)

返回文字列的第l个字母之后的部分文字列字符串

S.substr(l, r)

返回文字列的第l个到l r-1的部分文字列字符串

代码语言：javascript复制
#include <iostream>
#include <string>
using namespace std;

int main() {
    // 连接输入的2个文字列
    string a, b;
    cin >> a >> b;
    string c = a   b;
    if (c.size() <= 10) cout << c << endl;
    else cout << c.substr(0, 10) << endl;

    // 输入文字列的偶数位的文字都替换成：z
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i  = 2) s[i] = 'z';
    cout << s << endl;
    return 0;
}

入门

标准库

说明

min/max

最大值、最小值

swap

值交换

__gcd

最大公约数

rand

随机数

clock

时间计数器

reverse

数组逆序配列

sort

排序

min/max

  • 返回复数值得最大或者最小的值

程序

说明

min(a, b)

返回2个值中最小的值

max(a, b)

返回2个值中最大的值

min({a1, a2, ..., an})

返回{a1, a2, ..., an} 中最小的值

max({a1, a2, ..., an})

返回{a1, a2, ..., an} 中最大的值

*min_element(c l, c r)

返回{c[l], c[l 1], ..., c[r-1]}中最小的值

*max_element(c l, c r)

返回{c[l], c[l 1], ..., c[r-1]}中最大的值

  • min_element和max_element函数返回的是迭代器，所以取值的前头：
代码语言：javascript复制
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // 例1: 获取103, 168, 103中最大值，输出 : 168
    cout << max({103, 168, 103}) << endl;

    // 例2: 获取{c[1], c[2], ..., c[N]}中的最小值
    int N, c[100009], minx = 2147483647;
    cin >> N;
    for (int i = 1; i <= N; i  ) cin >> c[i];
    for (int i = 1; i <= N; i  ) minx = min(minx, c[i]);
    cout << minx << endl;

    // 例3: 获取{c[1], c[2], ..., c[N]}中最小值（从第2个元素开始）
    cout << *min_element(c   1, c   N   1) << endl;
    return 0;
}

swap

  • 交换2个变量的值
代码语言：javascript复制
#include <iostream>
using namespace std;

int main() {
    // 例1：输入2个变量 a, b，交换a, b的值并输出
    int a, b;
    cin >> a >> b;
    swap(a, b);
    cout << a << " " << b << endl;

    // 例2: 根据冒泡排序、把{c[1], c[2], ..., c[N]} 从小到打排序，并输出
    int N, c[1009];
    cin >> N;
    for (int i = 1; i <= N; i  ) cin >> c[i];
    for (int i = 1; i <= N; i  ) {
        for (int j = 1; j <= N - i; j  ) {
            if (c[j] > c[j   1]) swap(c[j], c[j   1]);
        }
    }
    for (int i = 1; i <= N; i  ) cout << c[i] << endl;
    return 0;
}

__gcd

  • 注意：比赛中是否可以使用带下划线_方法
  • 返回2个数的最大公约数
  • gcc提供了__gcd函数
    • __gcd(8, 16) = 8
    • __gcd(234, 217) = 1
代码语言：javascript复制
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // 例1： 输入2个整数 a, b，并计算a,b的最大公约数和最小公倍数
    int a, b;
    cin >> a >> b;
    cout << __gcd(a, b) << endl;   // 输出最大公约数
    cout << a / __gcd(a, b) * b << endl;   // 输出最小公倍数
    return 0;
}

rand：需要确认

  • 生成随机数

程序

说明

rand()

返回0~2-1内的随机数

srand((unsigned)time(NULL));

在main函数头部加上此语句，每次生成的随机数都不同

^{31}

-1内的随机数srand((unsigned)time(NULL));在main函数头部加上此语句，每次生成的随机数都不同

代码语言：javascript复制
#include <iostream>
#include <ctime>
using namespace std;

int main() {
    srand((unsigned)time(NULL));

    // 例1: 输出1到6以下的随机整数
    cout << rand() % 6   1 << endl;

    // 例2: 90%的输出："Yay!"、10%的输出：":("
    if (rand() % 10 <= 8) cout << "Yay!" << endl;
    else cout << ":(" << endl;
    return 0;
}

clock：待确认

  • 计算时间函数

程序

说明

clock()

返回从程序执行到现在经过的整数值

CLOCKS_PER_SEC

常量，根据环境，1秒等于多少是不同？？？

  • 实际经过的秒数：clock()/CLOCKS_PER_SEC表示
  • 需要引入头文件：ctime
代码语言：javascript复制
#include <iostream>
#include <ctime>
using namespace std;

int main() {
    // 例1：统计执行的时间
    int ti = clock();
    for (int i = 1; i <= 100000; i  ) cout << i << endl;
    printf("Execution Time: %.4lf secn", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}

reverse

  • 数组的值逆序
  • 时间复杂度： O(N)
  • 字符串想逆序的时候：reverse(str.begin(), str.end())

程序

说明

reverse(a, a N)

逆序排序：a[0], a[1], ..., a[N-1]例如、a = {2, 1, 4, 3, ...} 的时候， 执行：reverse(a, a 3) 、则返回a = {4, 1, 2, 3, ...}

reverse(a l, a r)

逆序排序：a[l], a[l 1], ..., a[r-1]

代码语言：javascript复制
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // 例1: 数组 a 第2-6的元素你序排序，输出{8, 3, 2, 6, 4, 1, 7, 5}
    int a[8] = {8, 3, 7, 1, 4, 6, 2, 5};
    reverse(a   2, a   7);
    for (int i = 0; i < 8; i  ) cout << a[i] << endl;

    // 例2：输入{b[0], b[1], ..., b[N-1]}，逆序排序后输出。
    int N, b[1009];
    cin >> N;
    for (int i = 0; i < N; i  ) cin >> b[i];
    reverse(b, b   N);
    for (int i = 0; i < N; i  ) cout << b[i] << endl;
    return 0;
}

sort

  • 数组的某个区间排序
  • 时间复杂度：O(NlogN)

程序

说明

sort(a, a N);

对于a[0], a[1], ..., a[N-1] ，从小到大排序

sort(a l, a r);

对于a[l], a[l 1], ..., a[r-1] ，从小到大排序

sort(a, a N, greater< int >());

对于a[0], a[1], ..., a[N-1] ，从大到小排序排序的数据int类型：greater< int >()排序的数据double类型：greater< double >()

代码语言：javascript复制
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    // 例1：数组a的第1到4元素从大到小排序，排序后结果：{8, 7, 4, 3, 1, 6, 2, 5}
    int a[8] = {8, 3, 7, 1, 4, 6, 2, 5};
    sort(a   1, a   5, greater<int>());
    for (int i = 0; i < 8; i  ) cout << a[i] << endl;

    // 例2：输入{b[0], b[1], ..., b[N-1]}、从小到大排序并输出
    int N, b[100009];
    cin >> N;
    for (int i = 0; i < N; i  ) cin >> b[i];
    sort(b, b   N);
    for (int i = 0; i < N; i  ) cout << b[i] << endl;
    return 0;
}

参考资料

  • 厳選！C アルゴリズム実装に使える 25 の STL 機能【前編】
    • https://qiita.com/e869120/items/518297c6816adb67f9a5
  • 厳選！C アルゴリズム実装に使える 25 の STL 機能【後編】
    • https://qiita.com/e869120/items/702ca1c1ed6ff6770257

END

对象存储 海外加速 编程算法 c++

0 人点赞