排序
一.快速排序
int a[N];
void sort_1(int l,int r)//分治
{
if(l>=r) return;
int x=a[l+r>>1];
int i=l-1,j=r+1;
while(i<j)//将a分为 <=x 和 >=x 的两个小数组
{
do i++;while(a[i]<x)//do-while循环,i和j一定会自增,使得循环会继续下去
do j--;while(a[j]>x)//while循环,i和j特殊情况下不自增,循环卡死
if(i<j)swap(a[i],a[j]);
}
sort_1(l,j);sort_1(j+1,r);//递归处理两个小数组
return;
}
二.归并排序
int temp[N],a[N];
void merge_sort(int l,int r)//分治 + 归并
{
if(l>=r)return;
int mid=l+r>>1;
sort_2(l,mid);sort_2(mid+1,r);
int k=0,i=l,j=mid+1;//递归处理子问题 a[l..mid], a[mid+1..r]
while(i<=mid&&j<=r)//主体合并
{
if(a[i]<a[j])temp[k++]=a[i++];
else temp[k++]=a[j++];
}
while(i<=mid)tmp[k++]=a[i++];//收尾
while(j<=r)tmp[k++]=a[j++];
for(i=l,j=0;i<=r;i++,j++)a[i]=temp[j];//复制回来
return;
}
模拟堆
//小堆的父节点小于他的儿子，大堆的父节点大于他的儿子 这里是小堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], s;
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)从前往后交换
{
int t=u;;//t存储三个结点中存在的最小的结点的下标，初始化为当前结点u
if(u*2<=s&&h[u*2]<h[t])t=u*2;
if(u*2+1<=s&&h[u*2+1]<h[t])t=u*2+1;
if(u!=t)//使其符合小根堆性质
{
swap(h[u],h[t]);
down(t);
}
return;
}
void up(int u//从后往前交换
{
while (u / 2 && h[u] < h[u / 2])//u/2向下取整，为父节点
{
heap_swap(u, u / 2);
u >>= 1;
}
}
void insert(int u);s//插入 将插入的元素放入最小根的底端然后进行up操作
{
h[++s]=u;
hp[s]=++idx;
ph[idx]=s;
up(s);
}
void delt(int k)//删除 将删除元素t 与 最后一个元素交换 然后down(t) up(t)排查
{
int u=hp[k];
h_swap(hp[k],s--);
up(u);
down(u);
}
for (int i = n / 2; i; i--)down(i);//从n/2开始 n/2*2=n 建堆
二分模板
bool check(int x)//{/* ... */}
int bserch(int l, int r)
{
while (l+1<r)//递归处理子问题，用while循环来实现
{
int mid = l + r >> 1;//分解成子问题
if (check(mid)) l = mid;//向左边找
else r=mid-1;//向右边找
}
return l;
}
前缀和与查分
一维前缀和
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
一维差分
给区间[l, r]中的每个数加上cB[l] += c, B[r + 1] -= c
二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
双指针算法
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
离散化
vector<int> alls; // 存储所有待离散化的值
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());// 去掉重复元素
区间合并
typedef pair<int,int> PII ;
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());//按左端点排序
int st = -2e9, ed = -2e9;//ed代表区间结尾，st代表区间开头
for (auto seg : segs)//遍历
if (ed < seg.first)////情况1：两个区间无法合并
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second)//情况2：两个区间可以合并，且区间1不包含区间2，区间2不包含区间1,合并
if (st != -2e9) res.push_back({st, ed});////考虑循环结束时的st,ed变量，此时的st,ed变量不需要继续维护，只需要放进res数组即可。
segs = res;
}
单调栈
常见模型：找出滑动窗口中的最大值/最小值
int stk[N], tt,n;
int main()
{
while (n -- )
{
while (tt && stk[tt] >= x) tt -- ;//如果栈顶元素大于当前待入栈元素，则出栈
stk[ ++ tt] = x;//入栈
}
单调队列
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
哈希
开放寻址法
const int N=200003;//一般会开成两倍的空间，且设为质数以减少数据的冲突
const int null = 0x3f3f3f3f;// 作为无穷大
int h[N];
int find(int x)//开放寻址法
{
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x)////冲突情况:当前位置不为空，并且不为x
{
k++;
if(k==N)k=0;////末尾，从头开始
}
return k; // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
}
memset(h,0x3f,sizeof h);
字符哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
const int N=1e5+10,P=131;// P = 131 或 13331 Q=2^64，在99%的情况下不会出现冲突
unsigned long long h[N],p[N];//h[i]前i个字符的hash值
char str[N];
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
unsigned get(int l,int r)//区间和公式 h[l,r]=h[r]-h[l-1]×P^(r-l+1)
{
return h[r]-h[l-1]*p[r-l+1]; //左移
}
树与图的存储
邻接矩阵
g[a][b]//存储边a->b
邻接表
int h[N], e[N], ne[N], idx;//双向边*2
//h头节点，e编号，ne下一节点下标
void add(int a, int b) {//连接a,b
e[idx] = b, ne[idx] = h[a], h[a] = idx++;//采用头插法
}
memset(h,-1,sizeof h);//先赋值为-1
DFS
int h[N], e[N], idx, ne[N];
bool st[N];// 需要标记数组st[N]
void dfs(int u) {
st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
dfs(j);
}
}
}
BFS
int h[N], e[N], idx, ne[N];
bool st[N];
int q[N];//模拟队列
int bfs()
{
int hh=0,tt=0;//头节点 尾节点
while(hh<=tt)//当我们的队列不为空时
{
int t=q[hh++];//取出队列头部节点
for(int i=h[t];i!=-1;i=ne[i])//遍历t节点的每一个邻边
{
int j=e[i];
if(st[j]==-1)
{
q[++tt]=j;//把j结点 压入队列
}
}
}
}
Dijkstra
typedef pair<int, int> PII;
const int N = 150010;
int h[N], e[N], ne[N], w[N],idx;
int dist[N];
bool st[N];
int n, m;
int dijkstra()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
heap.push({ 0, 1 });// // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
while(heap.size())
{
PII k = heap.top(); // 取不在集合S中距离最短的点
heap.pop();
int ver = k.second, distance = k.first;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i]; //// i只是个下标，e中在存的是i这个下标对应的点。
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j], j });
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
线性筛素数
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2至n遍历
{
if(!st[i])primes[cnt++]=i;//存储素数
for(int j=0;primes[j]<=n/i;i++)//primes[j]*i<=n
{
st[primes[j]*i]=true;//primes[j]是primes[j]*i的最小质因数
if(i%primes[j]==0)break;// prime[]数组中的素数是递增的,当i能整除prime[j]，那么i*prime[j+1]这个合数 肯定被prime[j]乘以某个数筛掉。
}
}
return;
}
试除求约数
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);//x!=i*i
}
sort(res.begin(), res.end());//保持有序性
return res;
}
快速幂
int qui(long long a,int b,int p)//a^b=a^2^0+a^2^1+...+a^2^logb
{
long long res=1;
while(b)
{
if(b&1)res=res*a%p;//如果b的二进制表示的第0位为1,则乘上当前的a
b=b>>1;////b右移一位
a=a*a%p;//更新a
}
return res;
}
KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )////j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始
{
while (j && p[i] != p[j + 1]) j = ne[j];////如果不行可以换到next数组
if (p[i] == p[j + 1]) j ++ ;////成功了就加1
ne[i] = j;////对应其下标
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )////j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度为0
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)////如果长度等于n了,说明已经完全匹配上去了
{
j = ne[j];// //为了观察其后续是否还能跟S数组后面的数配对成功
//匹配成功后...
}
}
Tire树
int son[N][26],cnt[N],n,idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的数量
char m;
string x;
void insert(string str)
{
int p = 0; //从根结点开始遍历
for (int i = 0; str[i]; i ++ )
{
int u =str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx; //没有该子结点就创建一个
p = son[p][u]; //走到p的子结点
}
cnt[p] ++; // cnt相当于链表中的e[idx]
}
int find(string str)
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(!son[p][u])return 0; //该节点不存在，即该字符串不存在
p=son[p][u];
}
return cnt[p]; //返回字符串出现的次数
}
并查集
int p[N]; //存储每个点的祖宗节点
for (int i = 1; i <= n; i ++ ) p[i] = i;//初始化
int find(int x)// 返回x的祖宗节点
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
DP
具体做法:
1.定义数组，明确数组意义
2.找到状态转移方程(注意:从前往后找）
3.定义初始值
一.序列DP
最长上升/下降子序列
for(int i=1;i<=n;i++)//下降则从n至1
{
a[i]=1;
for(int j=1;j<i;j++)//下降则从n至i+1,j--
{
if(A[i]>A[j]&&(a[j]+1>a[i]))
a[i]=a[j]+1;//数结尾的子序列加上自己
}
ans=max(a[i],ans);//下降用min
}
二.背包问题
(1).01背包问题
for(int i=1;i<=m;i++)
for(int j=n;j>=v[i];j--)
dp[j]=max(dp[j-v[i]]+v[i]*w[i],dp[j]);
（2）.完全背包问题
for(int i=1;i<=m;i++)
for(int j=v[i];j<=n;j++)
dp[j]=max(dp[j-v[i]]+v[i]*w[i],dp[j]);
三.区间DP
合并问题
for(int len=2;len<=n;len++)
for(int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]- s[i-1]);
}
STL
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
CSP前必须记住的30句话
1.比赛前一天晚上请准备好你的各种证件，事先查好去往考场的路线
2.比赛之前请先调整你的屏幕分辨率到你喜欢的大小
3.比赛之前请把编译器的字体调为你平时惯用的字体，尤其是注意这种字体中的逗号，点，1，l这种易混淆的字是不是区分明显
4.在不影响视野的情况下，请将字号尽可能调大，方便查错
5.请将题目通读完以后，再开始深入思考你认为最容易的一道题
6.即使这道题再容易，也不要着急写代码，请先明确自己每一步要干什么后，再开始写，轻敌会是你最大的错误
7.即使这道题看起来再没法做，也不要提早放弃，这个时候纸和笔会是你最好的朋友，自己尝试几个例子，也许你就会找到答案
8.请一定先明确自己要干什么之后再写程序，不要走一步想一步
9.如果这是一道动态规划题，请先把转移方程写在纸上再编程
10.涉及到边界处理、加一减一之类的问题，请在纸上举个例子，标上下标以后，在编程时参照纸上的下标写
11.如果思考30分钟仍一头雾水，没有可以实现的算法，请你果断屏蔽掉100%的那一栏数据，开始写60%，50%乃至30%的算法——在CSP里面，30分绝不是小数目
12.几个常用的复杂度参考：100以下——可能是搜索；100~500——N^3，1000~5000——N^2，100000~500000——NlogN，500000以上——N或1
13.如果你发现你旁边的人写得很快，请你放心，他的算法十有八九是错的， 调整好自己的心态很重要
14.虽然1s+128MB内存 (这是以前的了，现在应该是 1s + 256MB)
是标准配置，不过也不是每道题都是这样的，还是请认真阅读试卷首页的试题说明
15.计算内存的方法：数组大小*类型长度/1000 / 1000=所占内存MB数，int(Pascal:longint)类型长度是4, long long (Pascal: int64) =8
16.记不住的话，记住int (Pascal: longint) 型数组在128MB内存下最大开到2500 0000是比较保险的（占100MB内存）
17.写完程序之后，请一定不要忙着编译，请一定要将你的代码从头到尾通读一遍，也就是静态查错，这是整个编程过程中最重要的步骤，有的变量重复调用问题调试的话，一个小时也看不出来，静态查错可以一下指出错误
18.静态查错请注意以下方面：
（1）是否写上了using namespace std？ (这是C++的，Pascal就不用了)
（2）数组开得是否够大？
（3）变量类型是否正确？
（4）memset时，所填的sizeof（XX）的XX是不是匹配？大小是不是正确？ (Pascal 是 fillchar)
（5）外层循环与内层循环的i，j是不是混用了？
（6）循环之前，i，j是否定义了？
（7）输入数据都输入了吗？
（8）这个程序是在执行你想让它执行的步骤吗？
19.通过样例后，请你一定不要放松警惕，因为样例并不能覆盖所有的情况，请自己设计几组数据，争取卡死你的程序
20.如果出现问题，请你调试你的程序，请一定要分模块调试，不要从头跟到尾
21.如果你已经设计不出能卡住你的程序的数据，恭喜你可以做下一题了
22.如果你用的是windows，请你注意把system（“pause”）注释掉 ( 针对C/C++，Pascal 不存在 )
23.为了万无一失，请你用return 0结束你的程序 ( 同样 ， 针对 C/C++ ，建议是必须加上 )
24.在内存允许的情况下，能开普通队列就不要用循环队列，能开下普通数组就不要用滚动数组
25.在时间允许的情况下，能暴力就暴力，高精度能不压位就不压位，优化不需要的就不要
26.总之，在不超限制的前提下，能不优化就不优化，以减少代码量和出错概率为第一原则
27.当比赛还剩下5~15分钟的时候，请不要再改动你的程序，即使你怀疑它对你的一个输入给出了错误答案，因为你自己算出的结果也有可能是错的
28.这个时候请你检查是否注释掉了该注释掉的东西，文件名是否写对，文件夹是否建对，请一定反复检查！
29.今年的更改，没有人知道究竟会变成什么样，所以，与其瞻前顾后，不如集中精力做出你眼前的题目来的实际
30.请记住，CSP不怕暴力，怕瞎算，不怕不会，怕不敢
很全面！