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

2023-08-31 14:11:24 浏览数 (1)

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

标准库

说明

assert

断言

count

统计某字符个数

find

查找

next_permutation

全排序

_builtin_popcount

计算无符号整数有多少个1

bitset

二进制位集合

assert

  • 定义条件，不满足的时候，发生运行时错误，debug时能使用。
  • assert(条件)，不满足时候，发生运行时错误，例如N≤20的时候执行，其他的都抛出错误
  • 引入头文件：cassert
代码语言：javascript复制
#include <iostream>
#include <cassert>
using namespace std;

int N, X, cnt, a[10009];

int main() {
    // 例1: 列举满足a[i]   a[j] = X  (i, j) [i < j] 的个数
    // N > 10000的时候执行时间不满足，则发生错误

    cin >> N >> X;
    for (int i = 1; i <= N; i  ) cin >> a[i];
    assert(N <= 10000);

    for (int i = 1; i <= N; i  ) {
        for (int j = i   1; j <= N; j  ) {
            if (a[i]   a[j] == X) cnt  ;
        }
    }
    
    cout << cnt << endl;
    return 0;
}

count

  • 数组或者vector的某个区间元素中，包含几个x的函数
  • 数组：count(a l, a r, x)
  • vector：count(v.begin(), v.end(), x)
  • 时间复杂度：O(r−l)
代码语言：javascript复制
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // 例1: 数组a中含有1的个数，2的个数（输出4, 3）
    int a[10] = {1, 2, 3, 4, 1, 2, 3, 1, 2, 1};
    cout << count(a, a   10, 1) << endl;
    cout << count(a, a   10, 2) << endl;

    // 例2: 输入b[1], b[2], ..., b[N]、之后输入Q个
    // 对于、b[l], b[l 1], ..., b[r] 的中x有几个的输出
    int b[1009], N, Q;
    cin >> N;
    
    for (int i = 1; i <= N; i  ) cin >> b[i];
    
    cin >> Q;
    
    for (int i = 1; i <= Q; i  ) {
        int l, r, x;
        cin >> l >> r >> x;
        cout << count(b   l, b   r   1, x) << endl;
    }
    return 0;
}

find

  • 数组或者vector的某个区间元素中，是否含有x，含有的时候返回索引的函数
  • 数组：find(a l, a r, x)
    • 不包含x的时候，a r的迭代器
    • 包含x的时候，返回a[i] = x的迭代器
  • vector：find(a.begin(), a.end(), x)，函数返回的是迭代器
  • 函数：find返回的是迭代器，想知道最初出现的位置：find(a l, a r, x) - a
  • 时间复杂度：O(r−l)
代码语言：javascript复制
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // 例1: 输入a[1], a[2], ..., a[N] 之后输入：Q个
    // 对于输入(l, r, x) 、在a[l], a[l 1], ..., a[r]中，x不存在的时候，返回：-1
    // 不是的时候，返回位置
    int N, Q, a[1009];
    cin >> N;
    for (int i = 1; i <= N; i  ) cin >> a[i];
    cin >> Q;
    for (int i = 1; i <= Q; i  ) {
        int l, r, x;
        cin >> l >> r >> x;
        int f = find(a   l, a   r   1, x) - a;
        if (f == r   1) cout << "-1" << endl; // 不存在的时候
        else cout << f << endl; // 存在的时候
    }
    return 0;
}

next_permutation

介绍
  • next_permutation：当前排列的下一个排列
  • prev_permutation：当前排列的上一个排列
  • 使用：next_permutation，类似while循环感觉
  • vector：next_permutation(a.begin(), a.end())
  • 时间复杂度：O(N)
  • 数组的时候
代码语言：javascript复制
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
  int r[] = {1, 2, 3};

  do
  {
    for (int i = 0; i < 3; i  )
    {
      cout << r[i] << " ";
    }
    cout << endl;
  } while (next_permutation(r, r   3));

  return 0;
}

输出结果

代码语言：javascript复制
1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

示例代码

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

int N, A[12][12], B[12], perm[12], ans = 2000000000;

int main() {
    // N个城市，从城市i到j需要时间A[i][j]分钟
    // 所有的城市都去一次需要多长时间？
    // A[i][j] = A[j][i], A[i][i] = 0
    cin >> N;
    for (int i = 1; i <= N; i  ) {
        for (int j = 1; j <= N; j  ) cin >> A[i][j];
    }
    
    for (int i = 0; i < N; i  ) B[i] = i   1;

    do {
        int sum = 0;
        for (int i = 0; i < N - 1; i  ) {
            sum  = A[B[i]][B[i   1]];
        }
        ans = min(ans, sum);
    } while(next_permutation(B, B   N));

    cout << ans << endl;
    return 0;
}

_builtin_popcount

  • 整数用二进制表示的时候，返回二进制数中1的个数
  • gcc可以使用，Visual Studio 2019 不能使用
  • 例如：十进制数：42, 二进制：101010 ，则返回：3
代码语言：javascript复制
#include <iostream>
using namespace std;

int main() {
    // 例1: 把x转换二进制x，计算二进制数数中1的个数
    long long x;
    cin >> x;
    cout << __builtin_popcountll(x) << endl;
    return 0;
}

bitset

  • 表示位集合的数据结构，N位的2进制数
  • 能高速进行位运算
定义变量
代码语言：javascript复制
// 例1：定义长度：250000的位集合（250000位的二进制数）
bitset<250000> bs1;

// 例2: 长度为8的二进制数位集合，用整数初始化
bitset<8> bs2(131); // 10000011 

// 例3: 长度8的位集合，用2进制数初始化
bitset<8> bs3("10000011"); // 10000011

// 例4：和例3没什么变化，只是增加位集合的长度
bitset<2000> bs4("10000011");

程序

说明

a = (a ^ b)

同int类型，位运算（and, or, xor）

a.set(x)

a的第x个值变为1

a.reset(x)

a的第x个值变为0

a[i]

获取a的第i个值

a.count()

a的所有位，返回1的个数，和__builtin_popcount(x)相同

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

int main() {
    // 例1: 计算A or B
    string A; cin >> A;
    string B; cin >> B;

    bitset<2000> A1(A);
    bitset<2000> B1(B);
    bitset<2000> ans = (A1 | B1);

    bool flag = false;
    for (int i = 1999; i >= 0; i--) {
        if (ans[i] == 1) flag = true;
        if (flag == true) cout << ans[i];
    }
    cout << endl;
    return 0;
}

参考资料

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

END

stl 二进制 函数 集合 数组

0 人点赞