基础

语言

两个部分：算法设计和算法实现

优秀的code style：直接且明确

不同于传统编程，因为不需要后续维护，只需要正确而且简单即可，节约时间非常重要，因为时间有限

#include <bits/stdc++.h>
using namespace std;
int main(){
    //solution comes here
}

include这行将整个标准库包括，可以直接使用iostream、vector、algorithm中的库函数和方法。

输入输出可能成为程序的瓶颈，使用\n进行换行往往比endl要快，因为使用endl需要缓冲操作。

使用c语言的输入输出printf和scanf往往也快一点，但使用起来没那么简单。

使用getline()直接输入一行：

string s;
getline(cin,s);

如果输入的数据数量未知：

while(cin>>x){
    //code
}

使用文件重定向输入输出：

freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

最常用的类型为int，32位。int的范围不够可以选择long long的64位。

注意数据转换时可能隐藏的陷阱：

int a = 123456789;
long long b = a*a;
cout<<b<<"\n"; //-1757895751

这里先在int的范围内进行了乘法运算，发生了溢出，然后在赋值运算处进行类型转换，解决这一问题：

int a = 123456789;
long long b = (long long)a*a;
cout<<b<<"\n";

使用模运算处理一些大数运算，例如计算n!的余数，如果直接计算出n!可能发生溢出，则在每次乘积之后进行一次模运算，以免数据过大。

long long x = 1;
for (int i = 2; i <= n; ++i){
    x = (x*i)%m;
}
cout<< x%m << "\n";

计算精度问题引起的问题：

0.3*3+0.1 != 1

因此对于浮点数，使用==进行比较会产生意料之外的问题：

if (abs (a-b) < 1e-9){
    // a and b are equal
}

使用绝对值差小于一个很小的数来代替==进行比较。

缩短代码是一个实用的技巧，因为需要尽量快速的完成任务。

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair

定义之后：

v.push_back(make_pair(y1,x1));
v.push_back(make_pair(y2,x2));
int d = v[i].first+v[i].second;

可以写为：

v.PB(MP(y1,x1));
v.PB(MP(y2,x2));
int d = v[i].F+v[i].S;

也可以用宏定义函数：

#define REP(i,a,b) for (int i=a;i <= b; ++i)

for (int i=1; i < n; ++i){
    search(i);
}
//
REP(i,1,n){
    search(i);
}

由于是直接替换，所以可能造成一些问题，例如：

#define SQ(a) a*a
//a的平方
cout << SQ(3+3) << "\n"; //3+3*3+3 = 15

#define SQ(a) (a)*(a)
cout << SQ(3+3) << "\n"; //(3+3)*(3+3) = 36 结果正确

\sum_{k=1}^nk^p=1^p+2^p+\cdots+n^p

交并补差运算

向上取整 $\lceil x \rceil$

向下取整 $\lfloor x \rfloor$

ceil 表示天花板，即向上取整，floor表示地板，即向下取整

最大值max()

最小值min()

阶乘、斐波那契 ——递归