单调队列

单调队列相比于一般的队列来说，多了一个队尾出队。
一般的队列是秉持先进先出的原则，所以是队尾入队，对头出队。

单调队列中的元素相比于一般队列来说，多了单调性。队列内的元素始终保持单调，即单调递减或者单调递增。

队尾出对的条件：队列不空（应对第一个加入的元素）且有新元素加入时，新元素更优。
这个新元素更优分两种情况。如果是单调递增的一组元素来说。队尾进入的元素是越小越优，也就是越小越可以排到前面。所以当元素入队之后可以使用while循环对从队尾开始的每一个元素进行判断，如果比它大就踢出队列，直到队列为空或者遇到第一个比新元素小于或者等于的元素。然后将新元素加入队列。对于单调递减的一组元素来说，这个更优的情况就是元素越大越优，越可以排到前面。

队头出队的条件是队头元素滑出窗口
例程：

#include <bits/stdc++.h>

using namespace std;
int q[1000]; 
int a[1000];
int k, n;

int main()
{
    int h = 1, t = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i <= n; i ++)
    {
        while (t >= h && a[q[t]] >= a[i]) t --;
        q[++t] = i;
        if (q[h] < i - k + 1) h ++;
        if (i >= k) printf("%d ", a[q[h]]);
    }
    return 0;
} 

单调队列是用来维护一个滑动的定长窗口内的单调序列，从队头取最值，进行计算或者转移。

单调栈是维护一个固定的变长窗口[1, i]内的单调序列，从栈顶取最值，进行计算或转移。
每个元素从栈顶入栈，淘汰元素从栈顶出栈。

淘汰的机制是和单调队列相似的，也是如果要维护一个单调递减的序列，从栈顶取的是最大值，则越大越优，维护一个单调递增的序列，从栈顶取最小值，越小越优

例程：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int a[N];
int q[N];
int ans[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    int top = 0;
    for (int i = 1; i <= n; i ++)
    {
        while (top > 0 && a[q[top]] < a[i])
        {
            ans[q[top]] = i;
            top --;
        }
        q[++top] = i;
    }
    
    for (int i = 1; i <= n; i ++)
        cout << ans[i] << ' ' ;
    return 0;
}

#include <iostream>
#include <set>
using namespace std;
int main()
{
    int n;
    cin >> n;
    set<int> s;
    s.insert(0);
    for (int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        if (a < (*s.rbegin()))
        {
            s.erase(s.upper_bound(a));
        }
        s.insert(a);
    }
    cout << s.size() - 1 << endl;
    return 0;
}

启示：

用到了set的特性。除了去重之外，还有一个自动按照从小到大排序，和map一样，因为底层是红黑树，一种平衡二叉搜索树。所以可以有rbegin()取最后一个元素，就是最大元素。这里的逻辑就是让每一个轨道都保持一个单调上升的排序，这样再出去的时候就可以按照从大到小排序的出去（从右往左看）。所以对于每一个数来说如果比最大的还要大就单独开一个序列，如果小于最大的，说明可以找到一个序列使得放进去之后组成的排列时单调上升的，为了可以用最少的轨道，这个放进去的序列最好是最后一个数刚好大于要放进去的数，这里使用到了贪心的思想。为了维护每一个单调上升的序列，只要维护一个序列的最后一个值就好，因为前面的值一定比他大，而且不会拿来做比较，所以可以不看，因此set中实际上是维护了一个所有存在的轨道的序列中的最小值的一个不重复集合。而对于要放入的数来说，可以用upper_bound来找到第一个大于他的数，这个数就是要放入的轨道的最后一个值，将当前数放进去，本质上就是在set中将这个最后的值替换。而因为set中没有索引，但是可以自动排序，根据这一特性，为了完成替换这个操作，我们可以将这个最后一个值在set中删去，最后再将a放去set即可，这就在形式上和另外一种情况保持了统一。最后为了保证形式上的统一，不对第一个数特判，即set为空的情况，可以单独放入一个元素0，因为0一定比所有1到n的数小，所以不会被替换，就不会影响答案。最后的答案要求输出轨道的数量，其实就是set中元素的数量，因为有0的存在，所以实际上的答案是s.size() - 1.

题目：

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：

输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：

9
8 4 2 5 3 9 1 6 7

输出样例：

4

什么是树形 DP？

树形 DP（Dynamic Programming on Trees）是一种在 树结构 上使用 动态规划 解决问题的方法。它的核心思想是 自底向上 递归计算，每个节点的状态依赖于它的子节点的计算结果。

如果你熟悉普通的 动态规划（DP），你可以把树形 DP 理解为：

• 普通 DP 在一维或二维数组上进行（如最长子序列、背包问题）。
• 树形 DP 在树的节点之间进行（如子树计算、路径问题）。

树形 DP 的应用场景

树形 DP 主要用于 涉及树结构的最优决策问题，常见的题目类型包括：

1. 树的最小覆盖问题

题目： 选最少的节点，使得树中的所有边至少有一个端点被选。 解法： 定义 dp[u][0] 表示 u 不选，dp[u][1] 表示 u 选，递归计算。

2. 树的最大权路径和

题目： 给定一棵树，每条边上有权重，求从某个节点出发的最长路径。 解法： dp[u] 代表以 u 为根的子树的最长路径，递归求解。

3. 树的直径（最长路径）

题目： 求一棵树中两点之间的最长路径。 解法： 两次 DFS 或树形 DP 计算最长路径。

4. 树的最小删除代价

题目： 删除最少的节点，使得树变成某种结构（如二叉树）。 解法： dp[u] 表示删掉 u 的最小代价。

5. 祖先/子孙信息计算

题目： 计算树上每个节点的子孙数量、深度等信息。 解法： dp[u] 递归计算 u 的子树大小。

树形 DP 的基本步骤

1. 建树（用邻接表存储）。
2. 定义 DP 状态（每个节点可能有多种状态，如放置与不放置士兵）。
3. 递归计算 DP（从叶子节点开始往上计算）。
4. 返回根节点的最优解（一般是 min(dp[root][0], dp[root][1])）。

总结

树形 DP 是在树上进行的动态规划，通常用于计算子树信息、自底向上的最优决策，在树的路径问题、覆盖问题、删除问题、优化问题等场景中非常常见。它的核心是 递归计算每个节点的状态，并将结果传递给父节点。

树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
n：点数，m：边数
稀疏图:如果m和n是一个级别的，用邻接表。
稠密图:如果m和n^2是一个级别的，用邻接矩阵。

(1) 邻接矩阵：g[a][b] 存储边 a->b，先初始化g位正无穷

memset(g,0x3f,sizeof g);
g[a][b]=c;

(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx; 
// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
} 
// 初始化
idx = 0;
memset(h, -1, sizeof h);//初始化表头

(1) 深度优先遍历

时间复杂度 O(n+m) ，n表示点数，m表示边数.

int dfs(int u)
{    
    st[u] = true; // st[u] 表示点u已经被遍历过    
    
    for (int i = h[u]; i != -1; i = ne[i])    
    {        
        int j = e[i];        
        if (!st[j]) dfs(j);    
    }
}

(2) 宽度优先遍历

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1); 

while (q.size())
{    
    int t = q.front();    
    q.pop();  
       
    for (int i = h[t]; i != -1; i = ne[i])    
    {        
        int j = e[i];        
        if (!st[j])        
        {            
            st[j] = true; // 表示点j已经被遍历过            
            q.push(j);       
        }    
    }
}

树的深度优先遍历

树和图的深度优先遍历的模板：

// 需要标记数组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);        
        }    
    }
}

转自acwing 基础课题解

二分图 当且仅当图中不含奇数环。
二分图就是将图中的点分成左右两个集合，每条边都在两个集合之间
染色法判断是不是二分图
思路：利用dfs将每个点进行染色，将某个点染成白色，则以这个点为中心的其他点染成黑色，用1表示白色，用2表示黑色，0表示没有染过色，可以建立一个数组color[]，来存储染色情况，每次dfs先判断是否染色，如果没有就染成和上一个点不一样的颜色，可以用3去减，表示相反的颜色，如果有则判断是不是和上一点的颜色一样，如果一样就是有矛盾，表示出现了奇数环，则返回false，否则返回true。（给dfs传入的参数有两个一个是点，一个是染的颜色，可以设置一个默认值，默认传1）数据结构用邻接表来存图。因为每个点可能不会都是连通的，所以要遍历每一个点，判断是否染色，如果染过则跳过，如果没有则进行一遍dfs。为了判断最后的结构，我们需要一个判断的表示，所以可以新建一个布尔变量，一开始设置为true，之后如果某一次dfs返回值为false则将其设置为false，然后跳出循环。当循环结束之后只要判断这个布尔变量是否为true，为true则说明染色过程很顺利，该图是二分图，否则就不是二分图。
例题：

染色法判定二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。
数据范围1≤n,m≤1e5
输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

需要注意的是因为存的是无向图，所以边的数量应该是两倍于给的数量（相当于存两个方向相反的有向边）

匈牙利算法求二分图中最大的匹配数
思路：题目会给出一个二分图，先是遍历左边的点，每次遍历都遍历一遍那个点所连的边，让其和右边的点看能不能匹配，如果能那就匹配，如果不能就看一下那个被匹配的点于其匹配的那个点还有没有其他边的点可以与之匹配，如果可以，那就让那个点去匹配其他点，然后让现在这个点和被匹配的点匹配。去匹配其他点的过程是一个迭代的过程。数据结构是用的邻接表来存。对于手写邻接表中e[] , ne[] 的大小，应该是边的大小，因为每一个h都可以引出至多m（边数）条边，就是至多存有m个相连的点。定义一个bool st[]，表示被考虑过，每次遍历都要清空一下，表示在后面的迭代过程不会出现重复考虑的情况。定义一个int match[] , 用来存的是被匹配的点去匹配他的点。每次匹配成功就往答案中+1，当循环遍历完之后得到的就是最大匹配数。

例题：

二分图的最大匹配

给定一个二分图，其中左半部包含 n1 个点（编号1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1、 n2和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围 1≤n1 , n2≤500 , 1≤u≤n1 1≤v≤n2 , 1≤m≤1e5
输入样例：

2 2 4
1 1
1 2
2 1
2 2

输出样例：

2

思路：虽然没有说是有向图还是无向图，但是根据匈牙利算法的实现方式，可以当作单向图去存，且必须是去匹配的集合作为去指向的一方。

//find()函数
bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}