跳转至

常用内容

约 959 个字 预计阅读时间 3 分钟

C语言/C++数据类型有效范围表

类型 位 范围
char 1 个字节 -128 到 127 或者 0 到 255
unsigned char 1 个字节 0 到 255
signed char 1 个字节 -128 到 127
int 4 个字节 -2147483648 到 2147483647
unsigned int 4 个字节 0 到 4294967295
signed int 4 个字节 -2147483648 到 2147483647
short int 2 个字节 -32768 到 32767
unsigned short int 2 个字节 0 到 65,535
signed short int 2 个字节 -32768 到 32767
long int 8 个字节 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
signed long int 8 个字节 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
unsigned long int 8 个字节 0 到 18,446,744,073,709,551,615
float 4 个字节 精度型占4个字节（32位）内存空间，+/- 3.4e +/- 38 (~7 个数字)
double 8 个字节 双精度型占8 个字节（64位）内存空间，+/- 1.7e +/- 308 (~15 个数字)
long long 8 个字节 双精度型占8 个字节（64位）内存空间，表示 -9,223,372,036,854,775,807 到 9,223,372,036,854,775,807 的范围
long double 16 个字节 长双精度型 16 个字节（128位）内存空间，可提供18-19位有效数字。
wchar_t 2 或 4 个字节 1 个宽字符

比赛常用的非标准头文件

#include <bits/stdc++.h>

#include <bits/stdc++.h>是一个非标准的头文件，主要由 GNU C++ 编译器（g++）提供。它的设计目的是为了方便竞赛编程，允许程序员通过一个指令包含所有标准库头文件。这个头文件包含了几乎所有C++标准库的头文件，从而减少了在编写代码时需要手动包含多个头文件的麻烦。

由于它是非标准的，使用这个头文件在实际项目中并不推荐，因为它会增加编译时间和文件依赖。这个头文件通常只在编程竞赛和练习中使用，以提高开发速度和方便性。常见的包含内容有：

<iostream>用于输入输出、<vector>用于动态数组、<algorithm>用于常见算法、<cmath>用于数学函数、<string>用于字符串操作、<map>和<unordered_map>用于映射容器、<set>和<unordered_set>用于集合容器、<queue>和<stack>用于队列和栈、<deque>用于双端队列以及其他常用的STL头文件

根据数据范围猜算法

各种数据量下 ，可选用的算法的时间复杂度如下表：

数据量\时间复杂度 \(O(log_{2}{N})\) \(O(\sqrt{N})\) \(O(N)\) \(O(Nlog_{2}{N})\) \(O(N^2)\) \(O(N^3)\) \(O(2^N)\) \(O(N!)\)
\(n \le 10\) 可用 可用 可用 可用 可用 可用 可用 可用
\(n \le 30\) 可用 可用 可用 可用 可用 可用 可用 不可用
\(n \le 100\) 可用 可用 可用 可用 可用 可用 不可用 不可用
\(n \le 10^3\) 可用 可用 可用 可用 可用 不可用 不可用 不可用
\(n \le 10 ^ 5\) 可用 可用 可用 可用 不可用 不可用 不可用 不可用
\(n \le 10 ^ 7\) 可用 可用 可用 不可用 不可用 不可用 不可用 不可用
\(n \le 10 ^ 9\) 可用 可用 不可用 不可用 不可用 不可用 不可用 不可用
\(n \le 10 ^ {18}\) 可用 不可用 不可用 不可用 不可用 不可用 不可用 不可用

各种常见算法的时间复杂度

时间复杂度 算法
\(O(N!)\) 递归、 DFS、 DFS+剪枝
\(O(2^N)\) 递归、 DFS、 DFS+剪枝
\(O(N^3)\) 动态规划、记忆化搜索、floyd（多源最短路）
\(O(N^2)\) 动态规划、记忆化搜索、dijkstra（单源最短路）、prim（最⼩⽣成树）
\(O(Nlog_{2}{N})\) 快排、归并、heap（堆）、set（红⿊树）、⼆分、拓扑排序、堆优化的dijkstra、堆优化的prim、线段树
\(O(N)\) 双指针、滑动窗口 、单调栈和单调队列、搜索（BFS+DFS）、并查集
\(O(\sqrt{N})\) 判断质数
\(O(log_{2}{N})\) 辗转相除法（最大公约数） ，快速幂