常用头文件
POJ 不允许使用万能头文件(支持万能头文件的是 G++ 和 Clang++)
1 |
C++ 关流
用 C 语言可不能关流
1 | ios::sync_with_stdio(false),cin.tie(0); |
快读模板
平民版快读
1 | inline int read(){//快读 |
神级快读挂
1 | inline char nc() { |
时间复杂度比较
阶数 | 函数名 |
---|---|
O(1) | 常数函数 |
O(logn) | 对数函数 |
O(nlognlogn) | nlognlogn 函数 |
O(n) | 线性函数 |
O(nlogn) | nlogn 函数 |
O(n2) | 二次函数 |
O(n3) | 三次函数 |
O(2n) | 指数函数 |
测评姬运行速度
一般算法的时间复杂度决定了能否在规定时间内通过,那么 1000ms 测评姬能执行多少次运算呢?在竞赛中,一般的测评姬 1000ms 能大约进行 5e8 次计算
时间复杂度 | 数据范围 |
---|---|
O(n) | 1e8 |
O(nlogn) | 1e6 |
O(nsqrt(n)) | 1e5 |
O(n2) | 5000 |
O(n3) | 300 |
O(2n) | 25 |
O(n!) | 11 |
数据类型的范围
数据类型 | 范围 | 占用空间 | 最大值 |
---|---|---|---|
char | -128~+127 | 1 Byte | |
short | -32767~+32767 | 2 Bytes | 3e4 |
unsigned short | 0 ~ 65536 | 2 Bytes | 6e4 |
int | -2147483648 ~ +2147483647 | 4 Bytes | 2e9 |
unsigned int(long) | 0 ~ 4294967295 | 4 Bytes | 4e9 |
long long | -9223372036854775808 ~ +9223372036854775807 | 8 Bytes | 9e18 |
double | 1.7e308 | 8 Bytes |
Typora快捷键总结
快捷键 | 作用 | 快捷键 | 作用 |
---|---|---|---|
Ctrl + 1 | 一阶标题 | Ctrl + B | 字体加粗 |
Ctrl + 2 | 二阶标题 | Ctrl + I | 字体倾斜 |
Ctrl + 3 | 三阶标题 | Ctrl + U | 下划线 |
Ctrl + 4 | 四阶标题 | Ctr l+ Fn + Home | 返回Typora顶部 |
Ctrl + 5 | 五阶标题 | Ctrl + Fn + End | 返回Typora底部 |
Ctrl + 6 | 六阶标题 | Ctrl + T | 创建表格 |
Ctrl + L | 选中某句话 | Ctrl + K | 创建超链接 |
Ctrl + D | 选中某个单词 | Ctrl + F | 搜索 |
Ctrl + E | 选中相同格式的文字 | Ctrl + H | 搜索并替换 |
Alt + Shift + 5 | 删除线 | Ctrl + Shift + I | 插入图片 |
Ctrl + Shift + K | 代码块 | Ctrl + Shift + M | 公式块 |
Ctrl + Shift + ` | 代码行 | Ctrl + N | 新建文件 |
0x3f 和 memset
一般题的数据范围是小于 1e9 的,而 0x3f3f3f3f
在十进制下是 1e9 数量级,所以可以将 0x3f3f3f3f
作为 inf
使用并且不用担心爆精度( inf
+ inf
还在 1e9 数量级内)并且和 0xfffffff
是相同的数量级。-inf
建议用 0xcfcfcfcf
memset
是 C 语言的一个复制函数,它是将每个字节复制所以并不能随心所欲的赋值,只能赋三个数:0
,-1
,0x3f
,因为这第三个数恰好和十进制的数单位字节相同
注意 long long
赋值不能用这个,因为占用内存更大,转换为十进制后值不是你现象的那样
所以用 0x3f3f3f3f
前提就是数组和声明都是 int
型
之前一直以为 long long
是用 8 个 3f,但是后来发现没有科学依据,只能自己定义范围了,如果是 long long
型还非要赋值那就只能手动赋值了
C++ 和 G++ 区别
C 和 GCC 也是这个区别不过是针对于 C 语言的
C++ | G++ |
---|---|
C++ 是一门计算机编程语言 | G++ 不是语言,是一款编译器中编译 C++ 程序的命令 |
C++ 是 VC++ ,是微软出的编译器 | G++ 是 GNU 的那个 C++ 编译器,也是 Dev-CPP 自带的编译器和 NOI 系列赛官方的编译器 |
C++ 要求严格,非标准语言会 RE | G++ 宽松但是效率慢可能会 TLE |
还有就是为什么有时候会出现一个过的了另一个就 WA ?因为编译器对于语言的优化不一样,尽量避免编译器容易混淆的代码
总结:
-
输出
double
类型时,如果采用 G++ 提交,scanf
采用%lf
,prinf
采用%f
,否则会报错 -
使用 GCC/G++ 的提醒:对于 64 位整数,
long long int
和__int64
都是支持并且等价的。但是在读和写的时候只支持scanf("%I64d", ...)
和printf("%I64d", ...)
不支持"%lld"
是因为 MinGW 下的 GCC 和 G++ 使用的 msvcrt.dll 动态链接库并不支持 C99 标准 -
G++/GCC 使用
scanf
、printf
时注意引用<stdio.h>
,只引用<iostream>
不识别 -
提交 C 语言代码最好使用 G++,G++ 兼容 C 和 C++。C 的代码可以用 GCC 也可用 G++ 提交,而 C++ 的代码不能够用 GCC 提交,只能用 G++。因此最好一个通过不了的两个都试试,编译器的问题有的时候不好找(尤其是遇到
long long
类型的和double
的输入输出的时候)
区间左闭右开的好处
一直很奇怪为什么 STL 函数需要的迭代区间都是左闭右开的,尤其是查找函数写成全闭区间不是更好吗?这里说一下区间左闭右开的好处
-
对于查找函数取中间元素
mid=(begin+end)/2
如果区间元素的个数是奇数个那么mid
永远指向的是中间的元素,如果区间元素是偶数个那么mid
永远指向的是后半段区间的首元素。这样在二分查找等一些算法的实现上特别有优势。mid
的另一种写法是mid=begin+(begin-end)/2
比如区间的下标是
0,1,2,3
是偶数个,那么begin=0,end=4
,所以mid=(begin+end)/2=(0+4)/2=2
正好是后半段首元素。再看区间下标是0,1,2,3,4
是奇数个,那么begin=0,end=5
,所以mid=(begin+end)/2=(0+5)/2=2
此时2正好是中间的元素。
在任意合理的区间[begin,end)
上,总是有mid=(begin+end)/2
把区间分成[begin,begin+mid)
和[mid,end)
两个部分 -
方便迭代器快速的进行终止判别。只需要一个
begin==end
(或者begin>=end
)条件就能终止迭代判断 -
方便快速统计元素区间的个数,
元素的个数=end-begin
,如果是全闭区间那么元素个数=end-begin+1