常用头文件

POJ 不允许使用万能头文件(支持万能头文件的是 G++ 和 Clang++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>

C++ 关流

用 C 语言可不能关流

1
ios::sync_with_stdio(false),cin.tie(0);

快读模板

平民版快读

1
2
3
4
5
6
7
inline int read(){//快读
int s=0,w=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')w=-1;
for(;isdigit(c);c=getchar())s=(s<<1)+(s<<3)+(c^48);
return s*w;
}

神级快读挂

1
2
3
4
5
6
7
8
9
10
11
inline char nc() {
static char buf[1000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

template <typename _Tp> inline void read(_Tp&sum) {
char ch = nc(); sum = 0;
while (!(ch >= '0'&&ch <= '9')) ch = nc();
while (ch >= '0'&&ch <= '9') sum = (sum << 3) + (sum << 1) + (ch - 48), ch = 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-10x3f,因为这第三个数恰好和十进制的数单位字节相同

注意 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 采用 %lfprinf采用 %f,否则会报错

  • 使用 GCC/G++ 的提醒:对于 64 位整数,long long int__int64 都是支持并且等价的。但是在读和写的时候只支持 scanf("%I64d", ...)printf("%I64d", ...)
    不支持 "%lld" 是因为 MinGW 下的 GCC 和 G++ 使用的 msvcrt.dll 动态链接库并不支持 C99 标准

  • G++/GCC 使用 scanfprintf 时注意引用 <stdio.h>,只引用 <iostream> 不识别

  • 提交 C 语言代码最好使用 G++,G++ 兼容 C 和 C++。C 的代码可以用 GCC 也可用 G++ 提交,而 C++ 的代码不能够用 GCC 提交,只能用 G++。因此最好一个通过不了的两个都试试,编译器的问题有的时候不好找(尤其是遇到 long long 类型的和 double 的输入输出的时候)

区间左闭右开的好处

一直很奇怪为什么 STL 函数需要的迭代区间都是左闭右开的,尤其是查找函数写成全闭区间不是更好吗?这里说一下区间左闭右开的好处

  1. 对于查找函数取中间元素 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) 两个部分

  2. 方便迭代器快速的进行终止判别。只需要一个 begin==end(或者 begin>=end)条件就能终止迭代判断

  3. 方便快速统计元素区间的个数,元素的个数=end-begin,如果是全闭区间那么 元素个数=end-begin+1