编译器
用大括号给数组赋初始值就会导致编译出来的 exe 文件包含这个数组的空间。
简单来说就是 int a[N]={}; 会让可执行文件不运行的时候也占据这个数组的内存，会导致编译出来的可执行文件过大。
因此大的数组不要用大括号赋初值。
关键字
template 函数模板
C++ 中的模板特性会引发代码膨胀，因为为不同数据类型生成的函数或类的代码会根据使用次数而复制多份。内联函数
inline也是类似，简单的函数被频繁内联会导致代码在多处重复，增加了文件大小。
template <typename T> void read(T &x){...}
调用时可以写成 read(x) 或 read<int>(x)。
template <typename T> T read(){...}
调用时写 int x=read<int>()。
static
表示变量为全局变量。
inline 内联函数
格式参照：
inline <函数类型> <函数名> (参数){
函数语句;
}
众所周知，函数调用需要花费栈空间。
使用 inline 函数时，编译器可能会将调用函数的语句直接替换为函数内内容，从而节省栈空间。但是会增加可执行文件内存占用。
注意：
inline 关键字仅适合简单函数（指非常短小的函数）使用，不适合存在大量循环和递归的函数使用。
示例：
template <typename T>
inline void write(T x){
static int st[36];
int top=0;
if(x<0) putchar('-'),x=-x;
do{
st[top++]=x%10,x/=10;
}while(x);
while(top) putchar(st[--top]+'0');
}
结构体
初始化
struct node{
int x,y;
node ():x(0),y(0){}//默认构造函数，无参数
node (int _x,int _y):x(_x),y(_y){}//构造函数，有参数
};
int main(){
//三种初始化方式
node a;//a={0,0}
node b(1,2);//b={1,2}
node c{2,3};//c={2,3}
}
重载运算符
在类内重载：
struct node{
int x,y;
bool operator < (const node& b)const{
return y < b.y;
}
};
在类外重载：
struct node{
int x,y;
};
bool operator < (const node& a,const node& b) {return a.y<b.y;}
bool operator > (const node& a,const node& b) {return b<a;}
bool operator <= (const node& a,const node& b) {return !(b<a);}
bool operator >= (const node& a,const node& b) {return !(a<b);}
bool operator == (const node& a,const node& b) {return !(a<b)&&!(b<a);}
STL
STL 函数
-
reverse：翻转数组、字符串。reverse(v.begin(), v.end()) 或 reverse(a + begin, a + end)。 -
unique：去除容器中相邻的重复元素。unique(ForwardIterator first, ForwardIterator last)，返回值为指向 去重后 容器结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现完整容器去重。 -
lower_bound：在一个有序序列中进行二分查找，返回指向第一个 大于等于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。lower_bound(v.begin(),v.end(),x)。 -
upper_bound：在一个有序序列中进行二分查找，返回指向第一个 大于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。upper_bound(v.begin(),v.end(),x)。 -
next_permutation：将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。next_permutation(v.begin(), v.end())或next_permutation(v + begin, v + end)。 -
prev_permutation：将当前排列更改为 全排列中的上一个排列。用法同next_permutation。
bitset
bitset<1000> bs;
pb_ds 库
卡常小技巧
输入输出优化
1. 关闭同步流
注：写了以下代码后不可再用 scanf 和 printf，使用 cin 和 cout 效率甚至更快。
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
2. 快读快写
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
inline void read(T &sum){
sum=0;
T fl=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) (ch=='-')&&(fl=-1);
for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
sum=sum*fl;
}
template <typename T>
inline void write(T x){
static int st[36];
int top=0;
if(x<0) putchar('-'),x=-x;
do{
st[top++]=x%10,x/=10;
}while(x);
while(top) putchar(st[--top]+'0');
}
template <typename T>
inline void write(T x,char ch){
write(x);
putchar(ch);
}
3. C 风格输入输出
一般来讲，scanf 和 printf 足矣。
关键字的使用
可以使用 inline 加速。
register 已弃用。
循环
循环展开比较玄学，这里不讲。
可以写在一个循环里的就不要写成两个循环。
初始化
memset 比 for 快很多。
对拍详解
需要调试的程序
#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int main(){
freopen("in.in","r",stdin);
freopen("std.txt","w",stdout);
int a,b;
cin>>a>>b;
pf("%d\n",a+b);
}
暴力程序/样例
#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int main(){
freopen("in.in","r",stdin);
freopen("baoli.txt","w",stdout);
int a,b;
cin>>a>>b;
//暴力代码
int ans=a+b;
pf("%d\n",ans+1);
}
数据生成器
#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int main(){
freopen("in.in","w",stdout);
srand(time(0));
int a=rand()%100+1,b=rand()%100+1;
pf("%d %d\n",a,b);
}
对拍程序
#include<bits/stdc++.h>
#include<windows.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int main(){
while(1){
system("shuju.exe");
system("baoli.exe");
system("std.exe");
if(system("fc std.txt baoli.txt")){//比较是否相等，如不等，返回1
break;
}
Sleep(900);//等待0.9s
}
}
随机化函数
rand()
srand(seed);
int x=rand()%n+1;
seed 可以是一个常数如 114514 也可以是时间 time(0)。
注意，rand() 函数在 windows 系统下返回的取值范围为 \([0,2^{15}-1]\)，在 linux 系统下返回的取值范围为 \([0,2^{31}-1]\)。
mt19937
mt19937 rd(seed);
pf("%lld\n",rd()%N+1);
用法基本同 rand()。
mt19937 的效率比 rand() 更高，随机数的范围同 unsigned int 的范围，即 \([0,2^{32}-1]\)。
类似地，mt19937_64 的取值范围是 unsigned long long 的范围，即 \([0,2^{64}-1]\)。
随机排列 shuffle
mt19937 rd(time(0));
shuffle(a+1,a+n+1,rd);
计时函数
clock_t st=clock();
clock_t en=clock();
if(en-st>1.98*CLOCKS_PER_SEC) break;
一种基于随机化的方法
#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int main(){
srand(520);
clock_t start=clock();
while(1){
int x=rand()%100;
pf("%d\n",x);
//利用 x 做一些操作
//防止超时
clock_t end=clock();
if(end-start>1.98*CLOCKS_PER_SEC) break;
}
}