（一）排序

①选择排序 \(O(n^2)\)

②冒泡排序 \(O(n^2)\)

③快速排序 sort \(O(nlog n)\)

④归并排序 \(O(nlog n)\)

⑤桶排序（基数排序）

（二）科学记数法

\(x=aeb+c=a\times 10^b+c\)

（三）取模运算公式

A \((a\pm b)\% p=(a\%p \pm b\%p)\%p\)

B \((a\times b)\% p=(a\%p \times b\%p)\%p\)

当 \(a-b<0\)，那就使\(((a-b)\%p+p)\%p\)

其中 \(-p-1 \leq (a-b)\%p<0\)

推广：对斐波那契数列的第\(n\)项取模等于\(k\)的数，有\(f(n)\%1000=(f(n-1)\%1000+f(n-2)\% 1000)\%1000\)：

于是，记录\(f'(n-1)=(f(n-1)\%1000\)和\(f'(n-2)=(f(n-2)\%1000\) ，则：\(f(n)\%1000=(f'(n-1)+f'(n-2))\%1000\)

对第\(f(i)\)项，与\(f(i-j_{1})\)和\(f(i-j_{2})\)有关（已知\(j_{1},j_{2}\)）使用递推

斐波那契数列通项公式
\(f(n)=\frac{1}{\sqrt{5}}\left [ (\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right ]\)

质数
19260827
27631

（四）递推

楼梯有\(n\)阶台阶,周旷达上楼时可以一步上1阶,也可以一步上2阶 ,也可以一步上3阶， 编程计算周旷达共有多少种不同的走法。（对一质数27631取模）
\(f(n)=f(n-1)+f(n-2)+f(n-3)\)
删去加粗部分，公式变为 \(f(n)=f(n-1)+f(n-2))\)：

（五）递归

见斐波那契数列
Liuziwen-斐波那契数列

（六）C++二分函数

include

在一个从小到大排好的有序序列中找到第一个大于x的数的位置

upper_bound(起点，终点，x)
起点终点和sort相同（a+1，a+n+1）

在一个从小到大排好的有序序列中找到第一个大于等于x的数的位置

lower_bound(起点，终点，x)

小于？upper_bound(起点，终点，x，cmp)

（七）快速幂

pow（a，b）推出 \(a^b,1.5^{2.1}\)
求 \(a^b\%p\)（a，b，p都在int里）
\(a^b=(a^{\frac {b}{2}})^2 \times a(b\%2!=0)\)（7/3=2）

（八）全排序

给你1-n 输出所有的排列方式（有\(n!\)种排列）

（九）树状数组与线段树

对于一个数组a，读入n组l，r.对于每一组询问，输出 \(\sum_{i=l}^{r}a_{i}=a_{l}+a_{l+1}+...+a_{r}\)

数据范围：记数组大小为\(W\)

\(n \leq 10^6,W\leq 10^6\)

前缀和

第一行，一个n

接下来一行，n个a

接下来一行，一个m

接下来m行，格式如：

1 p x （表示第p位数改为x）

2 l r （求\(\sum_{i=l}^{r}a_{i}\)）

线段树 ，二叉树（完全二叉树）叶子

树状数组

对于一个数x，二进制最低位“1”的位权叫做lowbit

int lowbit(int x){
    return x&(-x);
} 

（十）模拟

约瑟夫问题 P1996LG：

n个人围成一个圈，从第一个人开始报数，报到m时这个人出列，下一个人从1重新开始报数，按照上述规则直到所有人出列。依次输出出列的人的编号。

（十一）栈（表达式）

中缀表达式 3*（5+2）

前缀表达式* 3 + 5 2

后缀表达式 3 5 2 + *

（十二）数据结构：

（1）栈

FIFO

#include <stack>
stack<int> stk;
stk.push(x)
x=stk.top()
stk.pop//栈顶部元素出去
stk.size
stk.empty

（2）队列

#include <queue>
queue <int> a;
q.push(x)
q.front
q.pop
q.size
q.empty

（3）不定长数组vector

 
#include <vector>
vector<int> a;
v.push_back
v[i] 第i位元素
v.size
v.empty
v.clear//清空
v.erase(i)//第i位元素擦除
i=v.begin+x
v.insert(i,x)

（4）映射map

#include <map>
map<int,int> mp;
mp[5]=3;
mp[220]=2;
mp<string,int>
string s=name;
int x=15;
mp[s]=x;
//pair
struct hhh{int first;int second}
pair(1,2)---first=1,second=2
x=pair(1,2)
x.first
printf("%d%c",tm[i]," \n"[i==n])

（5）优先队列

priority_queue
priority_queue<int> pqt;  // 大根堆
priority_queue<int,vector<int>,greater<int> > q; //小根堆

（十三）贪心

（十四）动态规划

（十五）lazy标记

关于树状数组

P3368 【模板】树状数组2

某一个区间每个数都加上x

求某一个x的值

P3374 【模板】树状数组1

某一个数加上x

求某段区间数的和

P3372 【模板】线段树1

某区间每个数加上x

求某段区间数的和

P3373【模板】线段树2

某区间每一个数乘上x

某区间每一个数加上x

求出某区间所有数的和

假期Noip笔记

原文：https://www.cnblogs.com/liuziwen0224/p/11992452.html