1.区间选点/最大不相交区间数量。https://www.acwing.com/problem/content/907/https://www.acwing.com/activity/content/problem/content/1112/思路即按右区间端点大小对所有区间进行排序，然后找到最多相交的区间然后化为一组。代码： 1234567891011121314151617181920

欧几里得算法欧几里得算法,也即辗转相除法，可以用来求最大公约数，即gcd(a,b) = gcd(b,a%b)。代码： 1234int gcd(int a,int b){ return b? gcd(b,a%b):a;} 拓展欧几里得算法定理：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，

线段树是算法竞赛中常用的用来维护区间信息的数据结构。线段树可以在O(logn)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 线段树的基本结构与建树线段树将每个长度不为1的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。上图即为将[1,13]区间划分出

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。经典例题：没有上司的舞会。https://www.acwing.com/activity/content/problem/content/1012/状态设定：dp[u][2]//0表示不选该点，1表示选该节点的快乐指数。代码： 12345678910111213141516171819202

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 例题：快速排序：https://www.acwing.com/problem/content/787/快速排序的思想就是基于分治。1.首先设定一个分界值，通过该分界值将数组分成左右两部分。2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中

lambda函数的语法基本形式 1[capture](parameters)->return-type {body} []叫做捕获说明符，表示一个lambda表达式的开始。接下来是参数列表，即这个匿名的lambda函数的参数。 parameters，普通参数列表 ->return-type表示返回类型，如果没有返回类型，则可以省略这部分。这涉及到c++11的另一特

单调队列，用来维护给定大小区间的最值。并且队列中元素之间的关系具有单调性，而且，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。可以用来维护给定区间的最大（最小值）（滑动窗口） 单调栈，用来维护最近的大于/小于关系，可以维护偏向全局的大小关系。 单调队列实现去尾操作用来维护队列的单调性，当有新元素需要入队时，从队尾向前依次移除影响单调性的元素。操作结束后，进行入队。 删头操作用来

map:map内部实现是红黑树，红黑树是非严格平衡二叉搜索树，而AVL是严格的平衡二叉搜索树，红黑树有自动排序的功能，因此map内部的元素都是有序的，操作时间复杂度为O（logn）。unordered_map:内部是哈希表，在没有冲突的情况下访问速度为O（1）。但在最坏的情况下可达到O（n）效率不稳定，而且不有序。例题：https://codeforces.com/problemset/probl

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。并查集通常包含两种操作，查找，合并。模板代码：朴素并查集+路径压缩优化: 1234567891011int find(int x){ if(p[x]!=x) p[x]= find(p[x]); return p[x];}//p[x]存储每个点的祖宗节点。//find(x

prim算法从已知的某个定点向外扩散，寻找最小的邻边，将顶点加入集合，如果顶点已经加入，则跳过（防止成环），直到所有顶点都加入到集合中，构成mst。适合稠密图 kruskal算法从整个图的最小的一条边开始贪心，在不成环的情况下，不断和并最后构成最小生成树。适合稀疏图。