2026春note

1.问题意识->抓主要矛盾
2.Dp（1）状态（I）阶段 （II）可求（III）可转移（2）转移
3.Dp优化（1）复杂度 状态*转移->区分空间复杂度&状态复杂度
（2）优化 （I）利用状态间的关系（II）预处理前后无关的转移
2026.2.8课堂总结
一，DP相关
1.DP必备条件：
（1）最优子结构：即由A状态的最优解可推到B状态的最优解
若不满足，Solve：（I） 重设状态（II）讨论不满足情况的性质
（2）重叠子问题：即某层状态可被分为性质相似，结构几乎相同的子问题
2.（求最优解）DP可看作以状态为点，转移为边的图并在其上求最短路
3.有环DP可使用SPFA求解，相对于Dijkstra，优点在无需建图，可以直接松弛
4.状态：I类：转移，可求，阶段；II类：重叠子问题
5.后效性：定义：不在状态中的信息对后面产生效用
DP要求无后效性，
若有后效性 Solve：（1）重设状态（2）细分方案，扩充状态（3）费用提前计算
二，从答案出发考虑问题
1.从\(答案\)的形式出发
（1）考虑最后形式（由过程推的），进行求解（大概率与过程无关）
（2）考虑最后一步进行前的形式
2.对答案进行调整：先构造满足一部分条件的答案，再依据其他条件对答案进行调整
三，从\(限制\)的角度考虑问题
1.去掉限制：即通过某种算法去除限制
2.满足限制：即构造答案满足所有限制
3.限制的存在：某些限制其实并不成立，可以不做考虑
补注：排序贪心需要具有传递性（模拟sort的比较cmp）
四，从\(边界\)的角度考虑问题
1.树上问题：优先考虑\(根节点\)和\(叶子节点\)
2.权值有关问题：优先考虑\(a_{max},a_{min}\)
\(tip:当边界状态被解决时可能会有新的边界状况产生\)
3.考虑\(n=1，n=2\)时，推广从\(n=k\)到\(n=k+1(归纳)\)
补注:最小增量
1.核心原理：不一次性全局重算、不改到底，只做最小必要的变化 / 最小代价的更新 / 最小步长的逼近，逐步逼近最优或目标状态。
2.性质：(1):变化最少 (2):代价最小 (3): 逐步收敛
3.思想内核：(1):局部最优累积成全局最优 (2): 复用历史、拒绝重复计算
4.应用：（1）：\(A*/Dijkstra\) 算法 (2)：最小生成树\((kruskal/prim)\)
五，从反方向考虑问题（正难则反）
1.添加->删除 例如
2.从前到后->从后到前在这道题中，若为静态，考虑对顶堆，但为动态，从前至后不好做，考虑从后到前
3.考虑计数->考虑性质
在这道题中，它具有的性质就是\(1<=a_i<=9 \rightarrow {2,4,6,8},{3,6,9}相对位置不变\)
4.在图论中：建边\(\rightarrow\)删边
六，从建模的角度考虑问题
1.基本步骤：寻找问题\(\rightarrow\)转化问题\(\rightarrow\)识别新问题\(...\)直到新问题可以被解决
2.序列问题\(\rightarrow\)图论问题
即将\(i\)与\(p[i]\)连边，易得性质：该图由若干个环构成，然后识别新问题
Tip：球盒问题
球盒问题是组合数学中的经典模型，其解法取决于三个核心条件：
球是否相同
盒子是否相同
是否允许空盒
假设我们有 n 个球和 m 个盒子，以下是这八种情况的详细分类和对应公式。
📌 球不同，盒子不同
这是最直观的情况，每个球都可以独立地选择放入任何一个盒子。
允许空盒
每个球都有 m 种选择，总共有 n 个球，因此方案数为：
mⁿ
不允许空盒
这种情况要求每个盒子至少有一个球。可以通过第二类斯特林数 S(n, m) 来解决。S(n, m) 表示将 n 个不同元素划分为 m 个非空、不可区分的集合的方案数。由于盒子是可区分的，我们需要对这 m 个集合进行全排列，因此方案数为：
m! ⋅ S(n, m)
这个值也可以通过容斥原理直接计算：
∑ᵢ₌₀ᵐ (-1)ⁱ ⋅ C(m, i) ⋅ (m-i)ⁿ
📌 球不同，盒子相同
此时盒子是不可区分的，我们只关心球是如何被分组的。
允许空盒
这等价于将 n 个不同的球划分成 k 个非空集合，其中 k 可以是 0 到 m 之间的任意整数。总方案数是所有可能 k 值的第二类斯特林数之和：
∑ₖ₌₀ᵐ S(n, k)
（当 k > n 时，S(n, k) = 0）
不允许空盒
这正是第二类斯特林数 S(n, m) 的定义：将 n 个不同元素划分为 m 个非空、不可区分的集合的方案数。
它满足递推关系：S(n, m) = S(n-1, m-1) + m ⋅ S(n-1, m)
📌 球相同，盒子不同
因为球是相同的，我们只关心每个盒子中球的数量。
允许空盒
这个问题等价于求不定方程 x₁ + x₂ + ... + xₘ = n 的非负整数解的个数。可以使用隔板法（也称插板法）的变形，通过引入 m 个“虚拟球”来解决，方案数为：
C(n + m - 1, m - 1)
不允许空盒
这等价于求不定方程 x₁ + x₂ + ... + xₘ = n 的正整数解的个数（即每个 xᵢ ≥ 1）。使用标准的隔板法，在 n 个球形成的 n-1 个空隙中插入 m-1 个隔板，方案数为：
C(n - 1, m - 1)
（此公式在 n ≥ m 时有效，若 n < m 则方案数为 0）
📌 球相同，盒子相同
这是最复杂的情况，通常没有简单的闭式公式，而是通过递推关系求解。我们用 p(n, m) 表示将整数 n 划分为 m 个正整数之和的方案数（即整数划分）。
允许空盒
允许空盒意味着实际使用的盒子数量可以是 1 到 m 中的任意值。这等价于将 n 划分为不超过 m 个正整数之和的方案数。它可以通过递推求解，递推关系为：
p(n, m) = p(n, m-1) + p(n-m, m)
其中 p(n, m-1) 代表至少有一个空盒的情况，p(n-m, m) 代表没有空盒的情况（先从每个盒子中拿出一个球）。
不允许空盒
这正是整数划分问题 p(n, m) 的定义：将 n 划分为恰好 m 个正整数之和的方案数。它同样可以使用上述递推关系进行计算。
七，从性质的角度考虑问题
1.从题目的性质：特殊的数字，计算方式或数据范围
2.找规律&打表
3.同构变换
补注：01分数规划：
01分数规划是一类求解分式最优化问题的模型
目标是在若干元素中选出一个子集，使得所选元素的“权值之和”与“成本之和”的比值最大（或最小）。
求解方式：二分答案
我们二分一个答案\(t\)
那问题转化为\(\frac{\sum a_i}{\sum b_i}\ge t\) 移项
\(\sum a_i\ge t\sum b_i\rightarrow \sum (a_i-tb_i)\ge 0\)
注：可将数据结构封装，有利于提升码风

欧拉序

1. 基本定义
   对一棵树进行 DFS（深度优先搜索）：
   进入节点时记录（节点第一次出现）
   离开节点时也记录（通常再次记录父节点）
   得到的序列称为欧拉序。序列长度为 2N - 1（N 为节点数），因为每条边会被来回经过两次，根节点只记录一次。
   2.应用：欧拉序求LCA
   原理：在欧拉序中，u，v的连续区间内一定包含LCA（u，v)且为深度最小的

求法：将LCA转化为区间最小值，使用ST表/树状数组/线段树维护

1.数学期望的定义

如果离散型随机变量\(X\)的所有可能取值为\(x_1,x_2...x_n\)其出现的概率分别为\(p_1,p_2,...p_n\)那定义\(X\)的数学期望\(E(X)=\sum_i^n{x_ip_i}\)
注：如果一个随机变量的全部可能取值是有限个或可数无限个，那么这个随机变量就被称为离散型随机变量，上述的可数可理解为构造一个关于集合\(P\)和整数集\(N_*\)之间的双射\((Bijection)\),即一一映射

2.数学期望的性质

\((1).\) 常数的数学期望：\(\forall c \in R ,E(c)=c\)
\((2).\) 线性性
即\(E(\sum_i^n a_iX_i+c)=\sum_i^n a_iE(X_i)+c\)
注：该式实际表达了数学期望\(E(X)\)是一个线性函数
\((3).\) 独立变量的可乘性
对于两个独立变量\(X,Y\),有 \(E(XY)=E(X)E(Y)\)
\((4).\) 函数的数学期望
\(E(f(X))=\sum E(f(x_i))p_i\)

3.数学期望的意义

\((1).\)数学期望描述了随机变量的集中趋势
\((2).\)数学期望本质上是概率为权重的加权平均值，出现概率越高的结果，对期望值的影响（权重）就越大
例如：你参加一个游戏，\(50%\)概率赢\(100\)元，\(50%\)概率输\(50\)元。
\(E(X)=0.5×100+0.5×(−50)=25\) 元。
这并不意味着你玩一次能赢25元，而是如果你玩很多次，平均每次大约赚25元
\((3).\)数学期望代表在测试样本足够大时，你的平均结果趋近于期望值

换根DP

\((1)\) 定义：换根DP，又称二次扫描法，是树形动态规划中的一种高阶技巧
\((2)\) 流程：Step1：第一遍DFS，求出子树内外的值，任选一个节点（如1号）作为初始根，计算子树内的局部信息（如子树大小 size、子树内距离和等）
Step2：进行换根，利用状态转移方程进行计算

树上背包

\((1)\) 定义：在物品之间存在“树形依赖关系”（即选择子节点必须先选择父节点）的约束下，求解在有限容量内能获得的最大价值
\((2)\) 过程：Step1：第一遍DFS，先解决子树问题，在合并到父节点后在父节点DP

考试时需要做到

1.先看完考试的四道题，然后做第二/三道题（有把握的题的下一道题）
2.做大概1h后，回去做T1，T2
3.最后1h打T3，T4的暴力
4.最后15min，检查freopen，文件名，删调试输出

常用数学式的变形方法

\(1.\)交换"\(\sum\)"
\(eg1:\sum_{i=1}^n\sum_{j=1}^kf(i)\phi(j)=\sum_{i=1}^nf(i)\sum_{j=1}^k\phi(j)\)
\(2.\)利用常见恒等式进行变换
\(eg2:\sum_{i=0}^nC_n^ix^i=(x+1)^n\)\((\)二项式定理\()\)
\(3.\)利用某些项的特殊性质求解
\(4.\)在信息学中，不必将式子一直化，化到可以降低时间复杂度，或可以进行预处理即可

树上旅行：重复执行一个相同的操作，可以考虑倍增
上学：多元到单元的图上问题，可以考虑反建边并转化为单元到多元
割裂：考虑每个点是否在一组好点对的路径上，然后树上差分
公倍数问题：将枚举倍数的因数转为枚举的倍数

快读

int read(){
	int x=0,f=1;char ch=getchar_unlocked();
	while(ch!='-'&&(ch<'0'||ch>'9')){ch=getchar_unlocked();}
	if(ch=='-'){f=-1;ch=getchar_unlocked();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar_unlocked();}
	return x*f;
}

基数排序

\((1).\)算法原理：
选定基数\(p\)按基数进制下的第\(k\)位排序
正确性：在正在排的这一位时，前几位小的会先被放入