常用基本变量类型

int a = 2e9;
long long b = 9e18;
double c = 3.1415926535;
char d = 'X';
bool e = true;

基本运算符

算数运算符：+ - * / %
关系运算符：< <= > >= == !=
逻辑运算符：&&并且 ||或者 !取反
位运算：&按位与 |按位或 ^异或 ~按位取反 <<左移 >>右移

数组

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;	// 1000010
int a[N];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	
	return 0;
}

格式化输出

double x;
printf("%.2lf", x);		// 保留2位小数

数学函数

max(a, b)	// 求较大值
min(a, b)	// 求较小值
abs(a)		// 求绝对值
double x = 3.14;
int a = (int)x;	// 截尾取整（删去小数部分）floor()
int b = (int)(x + 0.5)	// 四舍五入 round()
int c = (int)(x + 0.99999999999) // 向上取整 ceil()
double sqrt(double x)		// 算数平方根
double pow(double a, double k)	// 求a的k次方

字符串

char[]

char s[] = "ABC" 等价于 char s[] = {'A', 'B', 'C', '\0'}
char s[100010];
cin >> s;	// 输入一个字符串，下标从0开始
cin >> (s + 1);		// 下标从1开始
int n = strlen(s + 1);	// 求字符串长度
strcmp(a, b)	// 按照字典序比较大小
如果a<b返回负数，a>b返回正数，相等返回0
strcpy(a, b)	// copy
把字符串b复制一份，赋值给a
strcat(a, b)	// 连接
把b字符串连接到a字符串的末尾

string

string s;
cin >> s;
s.size();	// 字符串长度
for (int i = 0; i < s.size(); i ++) {
	s[i]是一个char
}
s.substr(i, len); // 从下标i开始的连续的长度为len的子串
string s = "abcde";
cout << s.substr(2, 2) << endl;
结果是de

自定义函数

int main函数return 0表示程序正常结束

有返回值的函数

返回值类型 函数名(参数1, 参数2 ...) {
	函数体 
	return 返回值 
}

没有返回值的函数

void fun() {
      for (int i = 1; i <= 5; i ++) {
          for (int j = 1; j <= 5; j ++) {
              cout << '*';
          }
          cout << endl; 
      }
}

判断素数 $O(\sqrt n)$

bool is_prime(int n) {
	if (n < 2) return false;
    for (int i = 2; i * i <= n; i ++)
    	if (n % i == 0) return false;
	return true;
}

strlen $O(|s|)$

int strlen(char s[]) {
	int i = 0;
	while (s[i]) i ++;
	return i;
}

strcmp $O(min(|a|, |b|))$

char a[] = "AAA\0";
char b[] = "AAAA\0";
int strcmp(char a[], char b[]) {
	for (int i = 0; a[i] || b[i]; i ++) {	// 循环条件是两个字符串都未结束 
		if (a[i] < b[i]) return -1;
		if (a[i] > b[i]) return 1;
	}
	return 0; 
}

strcpy $O(|b|)$

void strcpy(char a[], char b[]) {
    int i = 0;
    while (b[i]) {
        a[i] = b[i];
        i ++;
    }
    a[i] = 0;
}

strcat $O(|a| + |b|)$

void strcat(char a[], char b[]) {
	int n = strlen(a), i = 0;
	while (b[i]) {
	    a[n + i] = b[i];
	    i ++;
	}
	a[n + i] = 0;
}

判断回文数 $O(lg(n))$

bool is_huiwen(int n) {
    int x = n, y = 0;
    while (n) {
        y = y * 10 + n % 10;
        n /= 10;
    }
    return x == y;
}

判断闰年 $O(1)$

bool leap(int year) {
    if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) return true;
    return false;
}

两点之间直线距离 $O(1)$

$dist = \sqrt {(x_1 - x_2)^2 + (y_1 - y_2) ^ 2}$

double dist(double x1, double y1, double x2, double y2) {
	double x = x1 - x2, y = y1 - y2;
	return sqrt(x * x + y * y);
}

排序算法

STL $O(nlogn)$

// 对下标[0, n - 1]排序
sort(a, a + n);
// 对下标[1, n]排序
sort(a + 1, a + n + 1);

选择排序 $O(n^2)$

void select_sort(int a[], int n) {
	for (int i = 1; i <= n; i ++)
		for (int j = i; j <= n; j ++)
			if (a[j] < a[i]) swap(a[i], a[j]); 
}

冒泡排序 $O(n^2)$

void bubble_sort(int a[], int n) {
    for (int i = 1; i <= n; i ++)
    	for (int j = 1; j <= n - i; j ++)
    		if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}

结构体排序

题目链接：https://www.luogu.com.cn/problem/T435902

struct Student {
    char name[11], num[11];
    int a, b, c, sum;
};

Student e[N];

// 如果return true就会把a排在前面，否则把b排在前面
bool cmp(Student a, Student b) {
	if (a.sum != b.sum) return a.sum > b.sum;
	return strcmp(a.num, b.num) < 0;
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) { 
		cin >> e[i].num >> e[i].name >> e[i].a >> e[i].b >> e[i].c;
		e[i].sum = e[i].a + e[i].b + e[i].c;
	}
	
	// 对下标为[1, n]的区间排序
	sort(e + 1, e + n + 1, cmp);
	
	for (int i = 1; i <= n; i ++)
		printf("%6s %10s %3d %3d %3d %3d\n", e[i].num, e[i].name, e[i].a, e[i].b, e[i].c, e[i].sum);
	return 0;
}

递归

阶乘 $O(n)$

int fact(int n) {
	if (n <= 1) return 1; 
	return n * fact(n - 1);
}

汉诺塔 $O(2^n)$

void move(char a, char b) {
	printf("move %c -> %c\n", a, b);
}

// 把a上的n个盘子移动到c，通过b 
void hanoi(char a, char b, char c, int n) {
	if (n == 1) move(a, c);
	else {
		hanoi(a, c, b, n - 1);	// 把a上的n-1个盘子移动到b，通过c
		move(a, c);
		hanoi(b, a, c, n - 1);	// 把b上的n-1个盘子移动到c，通过a
	}
}

int main() {
	int n;
	cin >> n;
	hanoi('A', 'B', 'C', n);
	return 0;
}

归并排序 $O(nlogn)$

• 可以顺便求【逆序对数量】

void merge_sort(int l, int r) {
    if (l >= r) return;
    
    int mid = (l + r) / 2;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] < a[j]) b[k ++] = a[i ++];
        else b[k ++] = a[j ++];
    }
    while (i <= mid) b[k ++] = a[i ++];
    while (j <= r) b[k ++] = a[j ++];
    
    for (int i = l; i <= r; i ++) a[i] = b[i];
}

快速排序 $O(nlogn)$

• 可以 $O(n)$ 求第 $k$ 小数

mt19937 rnd(time(0));
int a[N];
void quick_sort(int l, int r) {
    if (l >= r) return;
    
    int x = a[rnd() % (r - l + 1) + l], i = l - 1, j = r + 1;
    while (i < j) {
        do i ++; while (a[i] < x);
        do j --; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    
    quick_sort(l, j), quick_sort(j + 1, r);
}

组合型枚举 $O(2^n)$

int n, m; 			// 1~n里选m个有多少种方案 
int stk[N], tt;		// stk栈，下标[1, tt]的区间是栈里的元素，tt是栈里的元素个数 
void dfs(int u) {	// dfs(u)表示该考虑u选不选了 
	if (tt == m) {	// 如果选够m个了，输出结果 
		for (int i = 1; i <= tt; i ++) printf("%3d", stk[i]);
		puts("");
		return;
	}
	if (u > n) return;	// 超过n的数不考虑 
	stk[ ++ tt] = u;	// 选中u，u入栈 
	dfs(u + 1);			// 在选中u的情况下，考虑下一个数 
	tt --;				// 不选中u，栈顶出栈 
	dfs(u + 1);			// 在不选中u的情况下，再考虑下一个数 
}
int main() {
	cin >> n >> m;
	dfs(1);
    return 0;
}