ACM竞赛中vector与bitset的使用详解

"这篇资料主要介绍了ACM竞赛中常用的两种数据结构——`vector`和`bitset`，以及大数乘法的相关概念。" 在ACM/ICPC算法竞赛中，`vector`和`bitset`是两个非常重要的工具，它们分别属于STL（Standard Template Library，标准模板库）中的序列容器和位集容器。 `vector`是一种动态数组，它提供了类似数组的功能，但可以在运行时调整大小。在C++中，`vector`提供了多种操作方法： 1. `vector<int>a(0);` 初始化一个空的`vector`，包含0个`int`元素。 2. `vector<vector<int>>a(0);` 初始化一个二维的`vector`数组，所有子`vector`均为空。 3. `std::vector<int>a(4);` 初始化一个含有4个默认值（通常是0）的`int`元素的`vector`。 4. `std::vector<int>::iterator it;` 定义一个指向`vector`的迭代器，用于遍历或操作`vector`的元素。 5. `it = &a[2];` 获取`vector`中第三个元素的地址。 6. `it = a.insert(it, 23123);` 在迭代器指向的位置插入一个元素，这里是在第三个位置插入23123。 7. `insert(it, 7, 23233);` 插入多个相同元素，这里在第三个位置插入7个23233。 8. `erase(it);` 删除迭代器指向的元素，这里是删除第三个元素。 9. `std::vector<int>::reverse_iterator ri;` 定义一个反向迭代器，用于倒序遍历`vector`。 10. `v.empty()` 检查`vector`是否为空。 11. `v.size()` 返回`vector`的元素数量。 12. `v.push_back(t)` 在`vector`末尾添加元素`t`。 13. `v.pop_back()` 移除`vector`的最后一个元素。 14. `v1 = v2` `vector`的赋值操作，将`v2`的值复制给`v1`。 15. `v1 == v2` 比较两个`vector`是否相等。 16. `cout << v.front(); cout << v.back();` 输出`vector`的第一个和最后一个元素。 `bitset`则是一个用来存储和操作二进制位的高效容器，常用于位操作和空间优化： 1. `string s("1110"); bitset<8> c(s);` 使用字符串初始化`bitset`，`c`的值为00001110。 2. `bitset<8> c(4);` 直接用十进制数初始化`bitset`，`c`的值为00000100。 3. `bitset<8> c(s, 1, 3);` 从字符串`s`的第二个字符开始取3位，`c`的值为110。 4. `bitset<8> c(s, s.size() - 3);` 从字符串`s`的倒数第三位开始取到最后，`c`的值为110。 5. `b.any()` 和 `b.none()` 分别检查`bitset`是否有1（任何位置）或全为0。 6. `b.count()` 返回`bitset`中1的个数，`b.size()` 返回`bitset`的总位数。 7. `b[pos]` 和 `b.test(pos)` 分别用于访问和测试`bitset`的指定位置。 在处理大数乘法时，通常会涉及到高精度计算，可以使用自定义的算法，如Karatsuba乘法、Toom-Cook算法或者基于`vector`的模拟乘法。这些算法通过分治策略分解大数，降低计算复杂度，以适应ACM竞赛中对效率的要求。 理解和熟练运用`vector`和`bitset`对于解决ACM竞赛中的问题至关重要，它们提供了高效且灵活的数据管理手段，而大数乘法则是处理大规模整数运算的基础。