C++算法基础

做算法题时，往往需要一些最基础的“编程常识”，可以提高解题效率。本篇博客将常见的C++编程解题知识进行记录。

数据范围

• int。记住一点：int存储数据绝对值数量级不超过$10^9$，而long long存储数据绝对值数量级不超过$10^{18}$。
  • INT_MAX：最大的int类型整数。
  • INT_MIN：最小的int类型整数。
• float, double。记住一点：遇到浮点数，尽量使用double。
• string。

符号常量

• 宏

  #define PI 3.14159，#define P pair<int, int>

• typedef关键字

  typedef pair<int, int> P;，typedef long long LL

memset与fill

memset(array, element, buffer)，位于头文件<stdio.h>中，将数组array中大小为buffer的区域全部置为同一个元素element（通常为0或者-1），常见用法为memset(arr, 0, sizeof(arr))，将数组arr初始化为全零。

fill(array, element, buffer)，element为1，但是执行速度没有memset快。

结构体初始化

结构体也有自己的构造函数，请注意：

typedef struct s {
    string name;
    int age;
    s(string name, int age): name(name), age(age) {}
} Student;

如果按照上述写法给结构体编写了显式的构造函数，那么就不能不经初始化定义一个结构体了，因为默认的构造函数s() {}被覆盖。因此，完整的、容错性最好的写法如下。

typedef struct s {
    string name;
    int age;
    s() {} // 显式编写空的构造函数，防止被覆盖
    s(string name, int age): name(name), age(age) {}
} Student;

输入输出

常用C++中的输入输出操作符cin和cout。

• cin读取缓冲区，直到遇到空白符
• getline(cin, str)，其中str为string容器，它读取缓冲区，直到遇到换行符，因此很适合读取一整行的输入
• cout将缓冲区输出

行末空格符处理

有些算法题要求控制行末不允许出现空格符，比较坑，因为可能导致格式错误，处理方法也很简单，在循环内部加一个判断分支即可（比较繁琐）。

int i;
for(i=0; i<arr.size(); i++) {
    if(i != arr.size()-1)	cout<<arr[i]<<" ";
    else	c
}