在ACM中使用C++

Posted on Edited on

今天又双叒叕来水博客了……（不务正业）

令人尖叫的STL

algorithm 系列

fill, fill_n 填充数组

1
2
fill(a, a+n, INF);
fill_n(a, n, INF);

unique, unique_copy 对排序后数组去重

1
2
3
sort(a, a+n);
unique_copy(a, a+n, b, 重载==);
unique(a, a+n, 重载==);

reverse, reverse_copy 镜像翻转数组

1
2
reverse_copy(a, a+n, b);
reverse(a, a+n);

rotate, rotate_copy 数组轮换

1
2
3
int a[] = {1,2,3,4,5,6};
rotate_copy(a, a+2, a+6, b); // b == {3, 4, 5, 6, 1, 2}
rotate(a, a+5, a+6); // a == {6, 1, 2, 3, 4, 5}

random_shuffle 随机打乱数组

1
random_shuffle(a, a+n);

partial_sort 数组一次性取前k小

时间复杂度$n \log m$

1
partial_sort(a, a+k, a+n, 重载<);

partition, partition_copy 元素分成两组

1
2
3
4
Point* mid = partition(p, p+n, [o1, o2](const Point& a) {
        return (o2-o1).det(a-o1) > 0;
    });
// 以直线(o1, o2)为界将平面上的点划分成两组

还有stable_partition版本

merge, inplace_merge 归并数组

1
2
3
// 要求分别有序
merge(a, a+aLen, b, b+bLen, c, 重载<); // 非原地合并
inplace_merge(a, a+mid+1, a+aLen, 重载<); // 原地合并

equal_range 找到存在区间

1
2
3
sort(a, a+n);
// 等价于使用lower_bound和upper_bound
pair<int*, int*> bounds = equal_range(a, a+n, 10, 重载<);

make_heap O(n)建堆

1
make_heap(a, a+n, 重载<);

sort_heap 对堆排序

1
2
make_heap(a, a+n, 重载<);
sort_heap(a, a+n, 重载<);

push_heap 堆加入一个元素

1
2
a[n++] = 666;
push_heap(a, a+n, 重载<);

pop_heap 堆删除顶端元素

1
pop_heap(a, a+n--, 重载<);

lexicographical_compare 字典序小于

1
2
if (lexicographical_compare(s1, s1+len1, s2, s2+len2))
    printf("s1 < s2\n");

next_permutation, prev_permutation 求下一排列

1
2
3
int a[] = {1, 2, 3, 4, 5};
prev_permutation(a, a+5);
next_permutation(a, a+5);

Containers 系列

用到烂的知识点就不多提了。这里只写容易忘的。

bitset

构造函数

  1. bitset<size_t N> foo(int);
  2. bitset<size_t N> foo(std::string);

特性

  1. 长度在编译期确定
  2. 高位在左，低位在右
  3. 重载的方括号可以直接读取、操作位

常用函数

  1. size_t count() 返回1的个数
  2. bool test(size_t pos) 返回非引用的foo[pos]
  3. bool any() 是否有1
  4. bool none() 是否全0
  5. bool all() 是否全1
  6. bitset& set() 全部位设置为1
  7. bitset& set(size_t pos, bool val=true) 设置某个位
  8. bitset& reset() 全部设置为0 （也可有参数pos）
  9. bitset& flip() 反转全部位 （也可有参数pos）
  10. string to_string(char zero, char one) 按要求转化为string
  11. unsigned long to_ulong() 转化为UL
  12. ULL to_ullong 转化为ULL （C++11）

map

构造函数

  1. map<type1, type2> mymap;
  2. map<type1, type2> mymap({})

特性

  1. 内部用平衡树实现
  2. 不允许重复的Key
  3. 访问必须用迭代器 map<type1, type2>::iterator it;
  4. it->first 是Key，不可更变，it->second 是Value，可以修改。
  5. 查找元素必须用it = mymap.find(Key)，失败则返回mymap.end();

常用函数

  1. 重载方括号，若Key不存在则建立Key对应的默认构造Value。返回Value的引用。
  2. insert() 比较复杂，常用例子：mp.insert(pair<char, int>('a', 1));
  3. iterator begin() 指向头元素的迭代器 （rbegin()指向最后一个元素）
  4. iterator end() 指向尾元素的后一个迭代器（rend()指向头元素的前一个迭代器）
  5. iterator find(Key) 返回Key对应的迭代器，失败则返回end()。
  6. clear() 清空所有键值对，size归零。
  7. size_type erase (const key_type& k); 删除Key对应的键值对，返回删除个数
  8. iterator erase (const_iterator position); 删除迭代器指向的键值对，返回紧接下一个键值对的迭代器。
  9. iterator erase (const_iterator first, const_iterator last); 删除迭代器指向的左闭右开区间的键值对，返回紧接着下一个键值对的迭代器（或end()）。
  10. 注意，C++98中erase()不会返回迭代器，而是返回void
  11. iterator lower_bound (const key_type& k); 所在上界迭代器
  12. iterator upper_bound (const key_type& k); 所在下界迭代器

set

结点只有一个元素，不允许重复的红黑树。

常用函数

  1. 迭代器begin(), end(), rbegin(), rend().
  2. 容量empty(), size();
  3. 插入
    • pair<iterator, bool> insert(const value_type& val); 同时有非const的右值引用版本。
    • 返回的pair包括一个指向被插入值的迭代器，bool指明是否真的发生了插入操作。（如果元素被来就存在，就为false）
  4. 删除
    • iterator erase(const_iterator position); 删除指定迭代器位置的元素。返回紧接着的下一个元素的迭代器。
    • iterator erase(const_iterator first, cosnt_iterator last); 删除指定迭代器的左闭右开区间的元素。返回紧接着的下一个元素的迭代器。
    • size_type erase(const value_type& val); 删除指定的值。 返回被删除的元素个数（0或1）。
  5. 交换 swap(set& x); 交换两个类型相同的set。
  6. 清空 clear();
  7. 查找 iterator find(const value_type& val);
  8. 计数 size_type count(const value_type& val) const;
  9. 上下界（左闭右开）
    • iterator lower_bound (const value_type& val);
    • iterator upper_bound (const value_type& val);
    • pair<iterator,iterator> equal_range (const value_type& val); 包括了下界和上界。

C标准库 系列

assert 断言

1
2
3
4
5
6
#include <cassert>

assert(this->ch[0]->fa == this);
assert(this->ch[1]->fa == this);
#define NDEBUG
// NDEBUG 标记可删除assert

isdigit 判断字符是否十进制数

1
2
3
4
#include <cctype>

while (!isdigit(c=getchar()))
    if (c=='-') minus = true;

泯灭人性的数据类型

内存使用

类型 字节数 估计范围
int 4 ±2e9
short 2 ±3e4
char 1 保有127
float 4 37数量级，7位
double 8 307数量级，15位
long double 16 4931数量级，20位
long long 8 9e18
__int128_t 16 8.5e37

计算struct内存时要小心！最好使用sizeof的方式计算内存。

scanf和printf

类型 符号
unsigned int %u %o(8进制) %x(16进制)
unsigned long long %llu
double 入%lf，出%f
long double %Lf
__int128_t 不可用

读入行

gets()已经被删除。

读入int之类的操作不会吃掉行末，这会导致下一个getline(st, size)得到空串。

保险起见，应当自定义读入行。